📚

Fenwick Tree (BIT)を図解でわかりやすく解説

に公開
C#
AtCoder
アルゴリズム
datastructure
tech

はじめに

Fenwick Tree は、配列の値を更新しながら区間和を高速に求めるためのデータ構造です。

Binary Indexed Tree を略して BIT と呼ばれることも多いです。競技プログラミングでは、単に「BIT」と書かれていることもあります。

累積和は、値が変わらない配列の区間和を O(1) で求められる便利な方法です。一方で、途中で A[i] の値が変わると、累積和を作り直す必要があります。

Fenwick Tree は、ここをうまく補います。

  • 1点の値を増やす
  • 先頭からある位置までの和を求める
  • その差から区間和を求める

この3つを O(log N) で処理できます。

Fenwick Tree (BIT)とは？

Fenwick Tree は、配列の部分的な合計を別の配列に持っておくデータ構造です。

元の配列を A、Fenwick Tree の内部配列を tree とすると、tree[i] には「ある長さの区間の合計」が入ります。

大事なのは、各 tree[i] が担当する区間の長さが、2進数の性質で決まることです。

たとえば、内部では 1-indexed として次のように考えます。

i 2進数 i & -i tree[i] が持つ範囲
1 001 1 A[1]
2 010 2 A[1] + A[2]
3 011 1 A[3]
4 100 4 A[1] + A[2] + A[3] + A[4]
5 101 1 A[5]
6 110 2 A[5] + A[6]

i & -i は、i の一番下に立っているビットだけを取り出す式です。これを lowbit と呼ぶことがあります。

最初はこの式が急に見えるかもしれません。まずは「その場所が、どれくらい左までの合計を担当するかを決める値」くらいに覚えると追いやすいです。

図解

配列 A[1] から A[8] までを Fenwick Tree で持つと、内部配列の担当範囲は次のようになります。

たとえば、A[1] から A[6] までの合計を求めるときは、次のように分解できます。

A[1] + ... + A[6]
= tree[6] + tree[4]

tree[6] は A[5] + A[6]、tree[4] は A[1] + A[2] + A[3] + A[4] を持っているからです。

このように、いくつかの担当区間を足し合わせて prefix sum を作るのが Fenwick Tree の基本です。

どんなときに使うか

Fenwick Tree は、次のような問題で使いやすいです。

  • 配列の値が途中で変わる
  • 区間和を何度も聞かれる
  • 更新もクエリも高速に処理したい
  • セグメント木ほど多機能でなくてもよい

たとえば、次のような操作がたくさん来る場合です。

1 i x : A[i] に x を足す
2 l r : A[l] + A[l + 1] + ... + A[r - 1] を求める

累積和だけだと、更新のたびに後ろの値を直す必要があります。Fenwick Tree なら、更新も区間和も O(log N) です。

考え方

Fenwick Tree では、区間和を直接全部持つのではなく、prefix sum を作りやすい部品を持ちます。

主な操作は2つです。

操作 内容
Add(index, value) A[index] に value を足す
SumPrefix(count) 先頭から count 個の合計を求める

区間 [left, right) の和は、累積和と同じように差で求めます。

SumRange(left, right) = SumPrefix(right) - SumPrefix(left)

ここで right は含まない形です。C# の配列や Substring などでもよく出てくる [left, right) の考え方に合わせています。

アルゴリズムの流れ

内部では 1-indexed にすると実装しやすくなります。

0-indexed の index を受け取ったら、内部では index + 1 に変換します。

値を足すとき

Add(index, value) では、その位置を含む担当区間を持つ tree に値を足していきます。

i = index + 1
while i <= N:
    tree[i] += value
    i += i & -i

i += i & -i と進むことで、「この位置を含む、より大きな担当区間」へ移動できます。

先頭からの和を求めるとき

SumPrefix(count) では、A[0] から A[count - 1] までの合計を求めます。

i = count
sum = 0
while i > 0:
    sum += tree[i]
    i -= i & -i

i -= i & -i と戻ることで、重ならない担当区間を順番に集められます。

C#での実装

区間和は大きくなりやすいので、ここでは long で実装します。

using System;

public sealed class FenwickTree
{
    private readonly long[] _tree;

    public FenwickTree(int length)
    {
        Length = length;
        _tree = new long[length + 1];
    }

    public int Length { get; }

    public void Add(int index, long value)
    {
        if ((uint)index >= (uint)Length)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }

        for (int i = index + 1; i <= Length; i += i & -i)
        {
            _tree[i] += value;
        }
    }

    public long SumPrefix(int count)
    {
        if ((uint)count > (uint)Length)
        {
            throw new ArgumentOutOfRangeException(nameof(count));
        }

        long sum = 0;

        for (int i = count; i > 0; i -= i & -i)
        {
            sum += _tree[i];
        }

        return sum;
    }

    public long SumRange(int left, int right)
    {
        if (left < 0 || right < left || Length < right)
        {
            throw new ArgumentOutOfRangeException();
        }

        return SumPrefix(right) - SumPrefix(left);
    }
}

class Program
{
    static void Main()
    {
        long[] a = { 2, 4, 5, 7, 1, 3 };
        var bit = new FenwickTree(a.Length);

        for (int i = 0; i < a.Length; i++)
        {
            bit.Add(i, a[i]);
        }

        Console.WriteLine(bit.SumRange(1, 4));

        bit.Add(3, 6);
        Console.WriteLine(bit.SumRange(1, 4));

        Console.WriteLine(bit.SumPrefix(5));
    }
}

実行例

16
22
25

最初の配列は次の通りです。

A = [2, 4, 5, 7, 1, 3]

SumRange(1, 4) は [1, 4) なので、4 + 5 + 7 = 16 です。

その後、Add(3, 6) によって A[3] が 7 から 13 になります。

A = [2, 4, 5, 13, 1, 3]

もう一度 SumRange(1, 4) を計算すると、4 + 5 + 13 = 22 です。

SumPrefix(5) は先頭から5個の合計なので、2 + 4 + 5 + 13 + 1 = 25 になります。

計算量

Fenwick Tree の計算量は次の通りです。

処理 計算量
初期化 O(N)
Add O(log N)
SumPrefix O(log N)
SumRange O(log N)
使用メモリ O(N)

上の実装では、初期配列から作るときに Add を N 回呼んでいるので、構築は O(N log N) です。

競技プログラミングではこのままでも十分なことが多いです。より高速に作りたい場合は、Fenwick Tree を O(N) で構築する方法もあります。

つまずきやすいポイント

1-indexed と 0-indexed が混ざりやすい

Fenwick Tree の説明では、内部を 1-indexed で扱うことが多いです。

一方で、C# の配列は 0-indexed です。外から受け取る index は 0-indexed、内部の tree は index + 1 と決めておくと混乱しにくいです。

SumPrefix(count) は count 個の合計

SumPrefix(5) は A[5] までではなく、先頭から5個の合計です。

つまり、対象は A[0] から A[4] までです。

この形にしておくと、区間 [left, right) の和を SumPrefix(right) - SumPrefix(left) と自然に書けます。

できることは主に「足し算」と「差分」

Fenwick Tree は、区間和や頻度の合計のように、足して差し引けるものが得意です。

区間の最小値や最大値を更新込みで扱いたい場合は、セグメント木の方が向いていることが多いです。

まとめ

Fenwick Tree は、更新される配列の区間和を高速に扱うためのデータ構造です。

  • 内部では 1-indexed で持つと実装しやすい
  • Add で1点に値を足す
  • SumPrefix で先頭からの合計を求める
  • 区間和は prefix sum の差で求める
  • 更新もクエリも O(log N) で処理できる

累積和では更新がつらいと感じたら、次の候補として Fenwick Tree を思い出すと使いどころを見つけやすいです。

参考

  • Peter M. Fenwick, "A New Data Structure for Cumulative Frequency Tables"
  • AtCoder Library Practice Contest の Fenwick Tree 関連問題
  • 『問題解決力を鍛える！アルゴリズムとデータ構造』

Discussion