差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:data_structure:binary_indexed_tree [2020/06/04] – [概要] ikatakos
+++ programming_algorithm:data_structure:binary_indexed_tree [2023/02/08] (現在) – [扱える演算] ikatakos
@@ 行 1: / 行 1: @@
-======Binary Indexed Tree======
+======Binary Indexed Tree（Fenwick Tree）======
+区間の和に対するクエリ（Range Sum Query）を効率的に処理するデータ構造。((和以外にも使える。後述))
+Binary Indexed Tree、BIT、発案者の名前からFenwick Treeともいう。
 =====概要=====
 [[http://hos.ac/slides/20140319_bit.pdf|Binary Indexed Tree のはなし - hos.ac]][pdf]
-Range Sum Query（区間の和）に対する効率的なデータ構造。
   * 数列 $a_1,a_2,...,a_N$ がある
-  * 以下の2つの要求を処理する
+  * 以下の2つのクエリを処理する
-    * $a_i$ に $x$ を加算（$1 \le i \le N$）
+    * 「''add i x''」: $a_i$ に $x$ を加算（$1 \le i \le N$）
-    * $a_s～a_t$ の合計を得る（$1 \le s \le t \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回やれば任意区間の合計が得られる。
 =====実装=====
@@ 行 49: / 行 51: @@
 </sxh>
-注意点として、配列のindex等と異なり、添え字は1から始まる。その方が効率的に上下の要素を特定できるため。
+BITは、1つの配列として保持できる。
+ただし、一般的な配列のindexと異なり、添え字は1から始まる。その方が効率的に上下の要素を特定できるため。\\
+（実装上は、0 の部分は使わないで1つ長めに作っておくのがよい）
   ⇤←←←←←←８
@@ 行 55: / 行 60: @@
   ⇤２    ⇤６    ⇤10
   １  ３  ５  ７  ９   ...
+  index   記録する値
+  １      a1
+  ２      a1+a2
+  ３      a3
+  ４      a1+a2+a3+a4
+  ５      a5
+  ６      a5+a6
+  ７      a7
+  ８      a1+a2+a3+a4+a5+a6+a7+a8
+  ：      ：
 添え字を2進数にしたもの。
@@ 行 63: / 行 79: @@
     0011    0101    0111    1001     ...
-「$a_1 ～ a_7$ の和」を求めるときに足される箇所。7を表す "0111" から始めて、"1" が立っている箇所を下から1つずつ "0" にした添え字を辿っていく。
+ここから「$a_1 ～ a_7$ の和」を求めるときに参照される箇所。\\
+$7$ を表す ''0111'' から始めて、"1" が立っている箇所を下から1つずつ "0" にした添え字を辿っていき、その和を取る。
-  ⇤─←─←─←─←─←─←─1000
+    ⇤─←─←─←─←─←─←─1000
-  ⇤─←─←【0100】
+  【⇤─←─←─0100】
-  ⇤─0010        ⇤【0110】      ⇤─1010
+    ⇤─0010      【⇤─0110】      ⇤─1010
     0011    0101  【0111】  1001     ...
+「$a_5$ に $x$ を足す」処理をするときに参照される箇所。\\
+$5$ を表す ''0101'' 自身と、その頭上に「←─」がある箇所のそれぞれに $x$ を加算する。\\
+辿り方としては、''0101'' から始めて、一番下の "1" が立っている箇所に "1" を足したものが次の添え字となる。
+  【⇤─←─←─←─←─←─←─1000】
+    ⇤─←─←─0100
+    ⇤─0010      【⇤─0110】      ⇤─1010
+    0011  【0101】  0111    1001     ...
+  +  一番下の1:0001  = 0110
+  +  一番下の1:0010  = 1000
+==== 扱える演算 ====
+Fenwick木に載せられるのは足し算だけでなく、XORやかけ算、また（わりと致命的な制約はあるが一応は）minやmaxも載せられる。
+  * [[https://qiita.com/sysdev/items/30aa7d5e9ac4ea871bd3#%E4%BB%98%E9%8C%B2%E6%89%B1%E3%81%88%E3%82%8B%E8%A8%88%E7%AE%97|AtCoder Library を読んでアルゴリズムを勉強：フェニック木（BIT） - Qiita]]
+数学的にはアーベル群であれば、任意の区間和を求められる。\\
+セグメント木は「モノイド」であればよかったが、それに可換であることと、逆元が存在することが条件として加わる。
+常に1からの区間和だけでよいのであれば、逆元の存在は無くてもよく、可換モノイドであればよい。
+++++ それぞれが成り立たない場合 |
+=== 可換でない場合 ===
+可換とは、$a+b$ と $b+a$ の結果が同じになると言うこと。
+例えば文字列の連結は可換でなく、順番に繋げていかないといけない。
+  i   1   2   3   4     [1,4] → abcdefg
+  S  ab  cd   e  fg     [2,3] → cde
+これをFenwick木に載せたと仮定すると、こんな状態になっている。
+    2    3     4
+                abcdefg
+      abcd
+  ab         e
+ここで、$i=3$ の末尾に 'h' をつなげまーす、といっても、3自体の更新はそれでよいが、$i=4$ の更新は、切って割り込ませてまた繋げるという操作が必要になる。
+    2    3     4
+                abcde h fg  ←途中に割り込ませないといけない
+      abcd
+  ab         eh
+これは効率的に扱えない。セグメント木で実装した方がよい。
+=== 逆元が無い場合 ===
+逆元とは、足し算なら正負逆転させた数、かけ算なら逆数 $\frac{1}{a}$ など、その演算を打ち消すような存在のこと。
+minやmaxは、一度小さい値で更新されてしまったら、その前の値は復元できない。
+BITで、「1～10 の最小値は 5 でした」「1～4 の最小値も 5 でした」といわれても、5～10 の最小値は何なのか分からない。\\
+よって逆元を持たない場合は、1からの累積結果しか得られない。
+かけ算も、値として'0'があり得る場合は逆元が無いことに注意。
+++++
+==== より柔軟な実装 ====
+必要に応じて和,積,MINなど演算を様々に変えても対応できる実装にしておくと便利である。
+「初期値」と「演算する関数」さえ決めればよいので、これを外部注入できるようにすると、柔軟な実装になる。
+ただし、Python（などインタプリタ言語）では一般的に「''a = add(a, x)''」より「''a += x''」とした方が速い。\\
+柔軟性のために演算を関数で与える関係上、前者の実装となるので、ギリギリまで高速化を行いたい場合には向かない。
+++++ Python3 |
+<sxh python>
+class FenwickTreeInjectable:
+    def __init__(self, n, identity_factory, func):
+        self.size = n
+        self.tree = [identity_factory() for _ in range(n + 1)]
+        self.func = func
+        self.idf = identity_factory
+    def add(self, i, x):
+        tree = self.tree
+        func = self.func
+        while i <= self.size:
+            tree[i] = func(tree[i], x)
+            i += i & -i
+    def sum(self, i):
+        s = self.idf()
+        tree = self.tree
+        func = self.func
+        while i > 0:
+            s = func(s, tree[i])
+            i -= i & -i
+        return s
+</sxh>
+実装について補足。
+Fenwick木では、listやdictなどのオブジェクトを載せることもできる。\\
+その場合の注意点として、Pythonでは、オブジェクトを特に工夫無くコピーするとインスタンス自体が同じとなる。
+つまりどれか1つへの反映が他の全てに反映されてしまう。
+それを防ぐため、''identity_factory'' には「引数無しで呼ぶと初期値を生成して返す関数」を与える。
+これなら毎回別のものが生成される。
+<sxh python;title: だめな例>
+a = [0, 0]
+aaa = [a] * 3
+print(aaa)  # => [[0, 0], [0, 0], [0, 0]]
+aaa[0][0] = 5
+print(aaa)  # => [[5, 0], [5, 0], [5, 0]]
+# 以下の実装だと、上のようなことが発生する
+class FenwickTreeInjectable:
+    def __init__(self, n, identity_element, func):
+        self.size = n
+        self.tree = [identity_element] * (n + 1)  # ←ここがまずい
+        self.func = func
+    ...略
+</sxh>
+++++
@@ 行 83: / 行 233: @@
   * $a_i$ の値を得る（$1 \le i \le n$）
-この場合は、差分に着目することで、BITをそのまま利用できる。（上記pdf参照）
+この場合は、差分に着目することで、BITをそのまま利用できる。
   * $a_s～a_t$ に一律 $x$ を加算→「$s$ に $x$、$t+1$ に $-x$ を加算」
   * $a_i$ の値を取得→「$1～i$ の合計を取得」
+  * [[http://hos.ac/slides/20140319_bit.pdf|Binary Indexed Tree のはなし - hos.ac]][pdf]
 なお、見ての通り添え字が $n+1$ まで参照される可能性があるので、便宜上、BITのサイズは1大きい値で作っておく
@@ 行 96: / 行 248: @@
 <del>よくわからんけど、</del>上記の応用で、BITを2個使うことでできる。
+だが、これに関しては遅延評価セグメント木などを使った方が、汎用性が高いかもしれない。
 <sxh python>
@@ 行 119: / 行 273: @@
 =====区間の最大値・最小値=====
-Segment Treeほどの柔軟性は無いが、いくらかの制約された条件下で、区間最大値・最小値の管理にも使える（以下は最大値の例）
+Segment Treeほどの柔軟性は無いが、いくらかの制約下で、区間最大値・最小値の管理にも使える（以下は最大値の例）
-  * $update(i, x)$: $a_i$ を $x$ で更新する。この際、$x$ は必ず元の $a_i$ 以上でなければならない
+  * $update(i, x)$: $a_i$ を $x$ で更新する。
-  * $getmax(i)$: $a_1～a_i$ の最大値を取得する。必ず1からの最大値であり、途中からの $a_s～a_t$ は取得できない。
+    * この更新とは「上書き」でなくて「作用」でなくてはならない。
+    * つまり、$a_i←x$ は不可で、$a_i←\max(a_i,x)$ のように、現在より小さい値にすることはできない。
+  * $getmax(i)$: $a_1～a_i$ の最大値を取得する。
+    * 必ず1からの最大値であり、途中からの区間 $a_s～a_t$ は取得できない。
 単純に、上記のコードの加算を、MAXを取る操作に置きかえればよい。
@@ 行 146: / 行 303: @@
 </sxh>
-少し理解は難しくなるが、BITを2本使って管理することで、上記の制約を無くした区間最大値・最小値も得られる。
+少し理解は難しくなるが、BITを2本使って管理することで、制約をなくした区間最大値・最小値を取得する実装もできる。
   * [[https://ioinformatics.org/journal/v9_2015_39_44.pdf]]
   * [[https://freestylewiki.xyz/fswiki/wiki.cgi?page=%E3%83%95%E3%82%A7%E3%83%8B%E3%83%83%E3%82%AF%E6%9C%A8%28Binary+Indexed+Tree%29#p12|フェニック木(Binary Indexed Tree) - FreeStyleWiki]]
+ただし使い方がややトリッキーだし、このために実装すべき処理も多いため、
+より柔軟性高く区間取得が可能なSegment Treeを使った方が簡単かもしれない。
+++++ 少し詳細 |
+BITの配列 $data[i]$ は、$(i-LSB(i), i]$ の区間の情報を持たせている、ということができる。\\
+$LSB(i)$ は、$i$ の最下位ビットを指す。
+  BIT1
+  ⇤─←─←─←─←─←─←─1000
+  ⇤─←─←─0100                ⇤─←─←─1100
+  ⇤─0010        ⇤─0110        ⇤─1010        ⇤─1110
+    0011    0101    0111    1001    1011    1101    1111
+  i=1100 のLSBは 0100  →  1100 - 0100 = 1000  →  1001～1100 の情報を持っている
+これと同様にもう1つ、$[i, i+LSB(i))$ の情報を持たせたBITも作る。
+  BIT2
+─⇥─⇥─⇥─⇥─⇥─⇥─⇥
+─⇥─⇥─⇥                1100─⇥─⇥─⇥
+─⇥        0110─⇥        1010─⇥        1110─⇥
+    0011    0101    0111    1001    1011    1101    1111
+$[5,13]$ の範囲（2進数では[0101,1101]）の最大値を知りたいとき、
+  * ①5から、13を超える直前まで、BIT1上の親を辿る（$i$ に $LSB(i)$ を足していく）
+    * → 5, 6, 8
+  * ②13から、5未満になる直前まで、BIT2上の親を辿る（$i$ の $LSB(i)$ を0にしていく）
+    * → 13, 12, 8
+  * ③このとき、必ず同じindex(8)で終了する
+  * ④終了したindexを除き、①で辿ったindexを、BIT2上で参照する（BIT2[5], BIT2[6]）
+  * ⑤終了したindexを除き、②で辿ったindexを、BIT1上で参照する（BIT1[12], BIT1[13]）
+  * ⑥ ④,⑤で参照した値に加え、元の配列の終了したindexの値 $a_8$ を参照し、これらのMAXが答えとなる
+上書き更新も一応できるらしいが、
+たとえば [1,4] のどこかが更新され、それを元に [1,8] を更新するときは、[5,8] の最大値を取得しなければならない。\\
+セグメント木なら兄弟ノードを参照すればすぐ取得できるのだが、BITでの実装の場合は毎回取得が必要になり、$O(\log^2{N})$ かかる？
+（なんか上手いこと $O(\log{N})$ でやる方法が論文で説明されているっぽいが、よくわからない）
+++++
 =====累積和の二分探索=====
@@ 行 190: / 行 390: @@
 </sxh>
+++++ Injectable版 |
+<sxh python>
+class FenwickTreeInjectable:
+    def __init__(self, n, identity_factory, func):
+        self.size = n
+        self.tree = [identity_factory() for _ in range(n + 1)]
+        self.func = func
+        self.idf = identity_factory
+        self.depth = n.bit_length()
+    def add(self, i, x):
+        tree = self.tree
+        func = self.func
+        while i <= self.size:
+            tree[i] = func(tree[i], x)
+            i += i & -i
+    def sum(self, i):
+        s = self.idf()
+        tree = self.tree
+        func = self.func
+        while i > 0:
+            s = func(s, tree[i])
+            i -= i & -i
+        return s
+    def lower_bound(self, x, lt):
+        """
+        累積和がx以上になる最小のindexと、その直前までの累積和（未検証）
+        :param lt: lt(a, b) で a < b ならTrueを返す関数
+        """
+        total = self.idf()
+        pos = 0
+        tree = self.tree
+        func = self.func
+        for i in range(self.depth, -1, -1):
+            k = pos + (1 << i)
+            new_total = func(total, tree[k])
+            if k <= self.size and lt(new_total, x):
+                total = new_total
+                pos += 1 << i
+        return pos + 1, total
+</sxh>
+++++
+===== 添え字の範囲が大きい場合 =====
+BITは通常の配列で管理できると言ったが、取り得る添え字の上限が $N=10^{18}$ とかだと
+そもそもそれだけの配列をメモリ上に確保できない。
+だが、
+  * はじめ、全ての $a_i=0$ である
+  * 実際に飛んでくるクエリの個数は $Q=10^5$ 回など高が知れている
+という場合は工夫次第で処理できる。
+==== 座標圧縮 ====
+飛んでくるクエリを全て先読みできる場合に使える。
+  * [[https://drken1215.hatenablog.com/entry/2021/08/09/235400|座標圧縮 (座圧) - けんちょんの競プロ精進記録]]
+BITでは添え字の大小関係だけが意味を持つので、
+クエリを先読みして、加算または取得クエリで登場する添え字を大小関係を保ったまま $1～Q$ に振り直してやればよい。
+これで計算量は $Q$ クエリ通して $O(Q\log{Q})$ で済む。
+==== 動的木 ====
+データを配列でなく辞書型で持ち、必要な（0でない）部分だけ値を記録するようにする。
+  ⇤←←←←←←８
+  ⇤←←４
+  ⇤２    ⇤６    ⇤10
+  １  ３  ５  ７  ９   ...
+  データを持つ辞書を 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を持たせる感じ。
+  ⇤←←←←←←８
+  ⇤←←４
+  ⇤２    ⇤６    ⇤10
+  １  ３  ５  ７  ９   ...
+  (5, 3) に add クエリが来た場合、
+  まず1次元目の 5 に関して、data[5], data[6], data[8] が参照される。
+  このそれぞれのノードが持つ BIT について、
+次元目の 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版の実装 |
+<sxh python>
+from collections import defaultdict
+from typing import TypeVar, Callable, Generic
+T = TypeVar('T')
+class Dynamic2dFenwickTree(Generic[T]):
+    """
+    (T, func): 可換モノイド
+    factory: 単位元の生成関数
+    """
+    def __init__(self, h: int, w: int, factory: Callable[[], T], func: Callable[[T, T], T]):
+        self.data = defaultdict(lambda: defaultdict(factory))
+        self.h = h
+        self.w = w
+        self.func = func
+        self.factory = factory
+    def add_point(self, i: int, j: int, x: T):
+        """ (i, j) に x を加える（現状の値に追加で作用させる） """
+        data = self.data
+        func = self.func
+        i += 1
+        j += 1
+        while i <= self.h:
+            node = data[i]
+            k = j
+            while k <= self.w:
+                node[k] = func(node[k], x)
+                k += k & -k
+            i += i & -i
+    def get_range(self, i: int, j: int):
+        data = self.data
+        func = self.func
+        result = self.factory()
+        i = min(i + 1, self.h)
+        j = min(j + 1, self.w)
+        while i > 0:
+            if i in data:
+                node = data[i]
+                k = j
+                while k > 0:
+                    if k in node:
+                        result = func(result, node[k])
+                    k -= k & -k
+            i -= i & -i
+        return result
+</sxh>
+++++