Binary Indexed Tree(Fenwick Tree)

区間の和に対するクエリ(Range Sum Query)を効率的に処理するデータ構造。1)

Binary Indexed Tree、BIT、発案者の名前からFenwick Treeともいう。

概要

Binary Indexed Tree のはなし - hos.ac[pdf]

  • 数列 $a_1,a_2,...,a_N$ がある
  • 以下の2つのクエリを処理する
    • add i x」: $a_i$ に $x$ を加算($1 \le i \le N$)
    • sum i」: $a_1~a_i$ の合計を得る($1 \le i \le N$)

Binary Indexed Treeは、この2つを高速に行える。

合計が $a_1$ からしか得られない制約があるが、$sum(a_s~a_t) = sum(a_1~a_t) - sum(a_1~a_{s-1})$ なので、2回やれば任意区間の合計が得られる。

実装

詳しい説明は上のpdfで懇切丁寧に行われているので、Pythonコードだけメモ。

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

# 使用例
bit = Bit(10)     # 要素数を与えてインスタンス化
bit.add(2, 10)    # a2に10を加える
bit.add(5, 5)     # a5に 5を加える
print(bit.sum(3)) # a1~a3の合計を返す => 10
print(bit.sum(6)) # a1~a6の合計を返す => 15
bit.add(3, -6)    # a3に-6を加える
print(bit.sum(6)) # a1~a6の合計を返す => 9
print(bit.sum(6) - bit.sum(3))  # a4~a6の合計 => 5

BITは、1つの配列として保持できる。

ただし、一般的な配列のindexと異なり、添え字は1から始まる。その方が効率的に上下の要素を特定できるため。
(実装上は、0 の部分は使わないで1つ長めに作っておくのがよい)

⇤←←←←←←8
⇤←←4
⇤2    ⇤6    ⇤10
1  3  5  7  9   ...

index   記録する値
1      a1
2      a1+a2
3      a3
4      a1+a2+a3+a4
5      a5
6      a5+a6
7      a7
8      a1+a2+a3+a4+a5+a6+a7+a8
:      :

添え字を2進数にしたもの。

⇤─←─←─←─←─←─←─1000
⇤─←─←─0100
⇤─0010        ⇤─0110        ⇤─1010
0001    0011    0101    0111    1001     ...

ここから「$a_1 ~ a_7$ の和」を求めるときに参照される箇所。
$7$ を表す 0111 から始めて、“1” が立っている箇所を下から1つずつ “0” にした添え字を辿っていき、その和を取る。

  ⇤─←─←─←─←─←─←─1000
【⇤─←─←─0100】
  ⇤─0010      【⇤─0110】      ⇤─1010
  0001    0011    0101  【0111】  1001     ...

「$a_5$ に $x$ を足す」処理をするときに参照される箇所。
$5$ を表す 0101 自身と、その頭上に「←─」がある箇所のそれぞれに $x$ を加算する。
辿り方としては、0101 から始めて、一番下の “1” が立っている箇所に “1” を足したものが次の添え字となる。

【⇤─←─←─←─←─←─←─1000】
  ⇤─←─←─0100
  ⇤─0010      【⇤─0110】      ⇤─1010
  0001    0011  【0101】  0111    1001     ...

0101  +  一番下の1:0001  = 0110
0110  +  一番下の1:0010  = 1000

扱える演算

Fenwick木に載せられるのは足し算だけでなく、XORやかけ算、また(わりと致命的な制約はあるが一応は)minやmaxも載せられる。

数学的にはアーベル群であれば、任意の区間和を求められる。
セグメント木は「モノイド」であればよかったが、それに可換であることと、逆元が存在することが条件として加わる。

常に1からの区間和だけでよいのであれば、逆元の存在は無くてもよく、可換モノイドであればよい。

それぞれが成り立たない場合

より柔軟な実装

必要に応じて和,積,MINなど演算を様々に変えても対応できる実装にしておくと便利である。

「初期値」と「演算する関数」さえ決めればよいので、これを外部注入できるようにすると、柔軟な実装になる。

ただし、Python(などインタプリタ言語)では一般的に「a = add(a, x)」より「a += x」とした方が速い。
柔軟性のために演算を関数で与える関係上、前者の実装となるので、ギリギリまで高速化を行いたい場合には向かない。

Python3

区間に対する更新

上記のBit.add()は、点に対する更新しか行えない。では「$a_3~a_7$ に一律に5を加算」などが必要な場合にどうするか。

区間の和が必要ない場合

区間の和は必要なく、ある指定した位置の値だけわかれば良い場合。つまり、

  • $a_s$ から $a_t$ までに一律 $x$ を加算($1 \le s \le t \le n$)
  • $a_i$ の値を得る($1 \le i \le n$)

この場合は、差分に着目することで、BITをそのまま利用できる。

  • $a_s~a_t$ に一律 $x$ を加算→「$s$ に $x$、$t+1$ に $-x$ を加算」
  • $a_i$ の値を取得→「$1~i$ の合計を取得」

なお、見ての通り添え字が $n+1$ まで参照される可能性があるので、便宜上、BITのサイズは1大きい値で作っておく

区間の和も欲しい場合

  • $a_s~a_t$ に一律 $x$ を加算($1 \le s \le t \le n$)
  • $a_s~a_t$ の合計を得る($1 \le s \le t \le n$)

よくわからんけど、上記の応用で、BITを2個使うことでできる。

だが、これに関しては遅延評価セグメント木などを使った方が、汎用性が高いかもしれない。

class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)
    
    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)
    
    def sum(self, s, t)
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - \
               self.p.sum(s) - self.q.sum(s) * s

区間の最大値・最小値

Segment Treeほどの柔軟性は無いが、いくらかの制約下で、区間最大値・最小値の管理にも使える(以下は最大値の例)

  • $update(i, x)$: $a_i$ を $x$ で更新する。
    • この更新とは「上書き」でなくて「作用」でなくてはならない。
    • つまり、$a_i←x$ は不可で、$a_i←\max(a_i,x)$ のように、現在より小さい値にすることはできない。
  • $getmax(i)$: $a_1~a_i$ の最大値を取得する。
    • 必ず1からの最大値であり、途中からの区間 $a_s~a_t$ は取得できない。

単純に、上記のコードの加算を、MAXを取る操作に置きかえればよい。

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = -(10 ** 18)  # -INF
        while i > 0:
            s = max(s, self.tree[i])
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = max(x, self.tree[i])
            i += i & -i

少し理解は難しくなるが、BITを2本使って管理することで、制約をなくした区間最大値・最小値を取得する実装もできる。

ただし使い方がややトリッキーだし、このために実装すべき処理も多いため、 より柔軟性高く区間取得が可能なSegment Treeを使った方が簡単かもしれない。

少し詳細

累積和の二分探索

二分探索により、累積和が $x$ のindexや、$x$ を越えない最大のindexとその時の累積和などを得ることができる。

(※以下、sum, add は既述のコードと共通。init内でdepthを定義しておき、lower_boundで探索する)

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

Injectable版

添え字の範囲が大きい場合

BITは通常の配列で管理できると言ったが、取り得る添え字の上限が $N=10^{18}$ とかだと そもそもそれだけの配列をメモリ上に確保できない。

だが、

  • はじめ、全ての $a_i=0$ である
  • 実際に飛んでくるクエリの個数は $Q=10^5$ 回など高が知れている

という場合は工夫次第で処理できる。

座標圧縮

飛んでくるクエリを全て先読みできる場合に使える。

BITでは添え字の大小関係だけが意味を持つので、 クエリを先読みして、加算または取得クエリで登場する添え字を大小関係を保ったまま $1~Q$ に振り直してやればよい。

これで計算量は $Q$ クエリ通して $O(Q\log{Q})$ で済む。

動的木

データを配列でなく辞書型で持ち、必要な(0でない)部分だけ値を記録するようにする。

⇤←←←←←←8
⇤←←4
⇤2    ⇤6    ⇤10
1  3  5  7  9   ...

データを持つ辞書を data とする。
初期状態から 5 に x 加算する場合、data[5], data[6], data[8] それぞれに x が加算されるが、
逆に言うと他は 0 のままなので、明示的にデータを持たなくていい。

クエリが先読みできない場合にも使える。

計算量は $O(Q \log{N})$ だし、辞書で添え字から値を参照するコストも一般的に配列より重いので、若干、座標圧縮より計算は重くなる。

2次元木

以下のクエリを処理できる。

  • $H \times W$ の2次元グリッドがあり、各マスに整数が記録される
  • add i j x」: $(i, j)$ に $x$ を加算する
  • sum i j」: $(1,1)~(i, j)$ を対角線とする矩形の総和を取得する

実装としては、BITの各ノードに整数でなく、2次元目のBITを持たせる感じ。

⇤←←←←←←8
⇤←←4
⇤2    ⇤6    ⇤10
1  3  5  7  9   ...

(5, 3) に add クエリが来た場合、
まず1次元目の 5 に関して、data[5], data[6], data[8] が参照される。

このそれぞれのノードが持つ BIT について、
2次元目の 3 に関しては 3, 4, 8 を参照すれば良いので、

data[5][3], data[5][4], data[5][8],
data[6][3], data[6][4], data[6][8],
data[8][3], data[8][4], data[8][8],

以上のノードに加算してやればよい。

データの持たせ方は動的木で実装した方がよい。

配列で持つ方針だと $O(HW)$ の記録容量が必要になる。
クエリが少なくて座標圧縮しても、$O(Q^2)$ 以下にはならない。
もちろん、それで間に合うような制約であれば配列で実装してもよい。

$HW$ も $Q^2$ も大きすぎる場合は、動的木で実装すればメモリを抑えられる。
必要空間量は $O(Q (\log{Q})^2)$ となり、$Q=10^5$ 弱くらいなら問題なくなる。

Python による Injectable版の実装

1)
和以外にも使える。後述
programming_algorithm/data_structure/binary_indexed_tree.txt · 最終更新: 2023/02/08 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0