差分

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

--- programming_algorithm:data_structure:binary_indexed_tree [2020/02/26] – [累積和の二分探索] ikatakos
+++ programming_algorithm:data_structure:binary_indexed_tree [2020/12/13] – [実装] ikatakos
@@ 行 1: / 行 1: @@
-======Binary Indexed Tree======
+======Binary Indexed Tree（Fenwick Tree）======
 =====概要=====
@@ 行 5: / 行 5: @@
 [[http://hos.ac/slides/20140319_bit.pdf|Binary Indexed Tree のはなし - hos.ac]][pdf]
-Range Sum Query（区間の和）に対する効率的なデータ構造
+Range Sum Query（区間の和）に対する効率的なデータ構造。
-  * 数列$a_1,a_2,...,a_n$がある
+  * 数列 $a_1,a_2,...,a_N$ がある
   * 以下の2つの要求を処理する
-    * $a_i$に$x$を加算（$1 \le i \le n$）
+    * $a_i$ に $x$ を加算（$1 \le i \le N$）
-    * $a_s$から$a_t$までの合計を得る（$1 \le s \le t \le n$）
+    * $a_s～a_t$ の合計を得る（$1 \le s \le t \le N$）
 Binary Indexed Treeは、この2つを高速に行える。
@@ 行 49: / 行 49: @@
 </sxh>
-注意点として、配列のindex等と異なり、添え字は1から始まる。そうしないと効率的に上下の要素を特定できないため。
+注意点として、配列のindex等と異なり、添え字は1から始まる。その方が効率的に上下の要素を特定できるため。
   ⇤←←←←←←８
@@ 行 55: / 行 55: @@
   ⇤２    ⇤６    ⇤10
   １  ３  ５  ７  ９   ...
+添え字を2進数にしたもの。
+  ⇤─←─←─←─←─←─←─1000
+  ⇤─←─←─0100
+  ⇤─0010        ⇤─0110        ⇤─1010
+    0011    0101    0111    1001     ...
+「$a_1 ～ a_7$ の和」を求めるときに足される箇所。7を表す "0111" から始めて、"1" が立っている箇所を下から1つずつ "0" にした添え字を辿っていく。
+  ⇤─←─←─←─←─←─←─1000
+  ⇤─←─←【0100】
+  ⇤─0010        ⇤【0110】      ⇤─1010
+    0011    0101  【0111】  1001     ...
+==== より柔軟な実装 ====
+Fenwick木に載せられるのは足し算だけでなく、XORやかけ算、また（わりと致命的な制約はあるが一応は）minやmaxも載せられる。
+「初期値」と「演算する関数」さえ決めればよいので、これを外部注入できるようにすると、柔軟な実装になる。
+ただし、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>
+listやdictなどのオブジェクトを載せることもできる。\\
+Pythonでは、オブジェクトを特に工夫無くコピーするとインスタンス自体が同じとなる。つまりどれか1つへの反映が他の全てに反映されてしまう。
+それを防ぐため、''identity_factory'' には「引数無しで呼ぶと初期値を生成して返す関数」を与える。これなら毎回別のものが生成される。
+<sxh python>
+# だめな例
+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>
+++++
 =====区間に対する更新=====
-上記のBit.add()は、点に対する更新しか行えない。では「a3～a7に一律に5を加算」などが必要な場合にどうするか。
+上記のBit.add()は、点に対する更新しか行えない。では「$a_3～a_7$ に一律に5を加算」などが必要な場合にどうするか。
 ====区間の和が必要ない場合====
@@ 行 65: / 行 145: @@
 区間の和は必要なく、ある指定した位置の値だけわかれば良い場合。つまり、
-  * $a_s$から$a_t$までに一律$x$を加算（$1 \le s \le t \le n$）
+  * $a_s$ から $a_t$ までに一律 $x$ を加算（$1 \le s \le t \le n$）
-  * $a_i$の値を得る（$1 \le i \le n$）
+  * $a_i$ の値を得る（$1 \le i \le n$）
 この場合は、差分に着目することで、BITをそのまま利用できる。（上記pdf参照）
-  * $s$～$t$に一律$x$を加算→「$s$に$x$、$t+1$に$-x$を加算」
+  * $a_s～a_t$ に一律 $x$ を加算→「$s$ に $x$、$t+1$ に $-x$ を加算」
-  * 位置$i$の値を取得→「$1$～$i$の合計を取得」
+  * $a_i$ の値を取得→「$1～i$ の合計を取得」
-なお、見ての通り添え字が$n+1$まで参照される可能性があるので、便宜上、Bitのサイズは1大きい値で作っておく
+なお、見ての通り添え字が $n+1$ まで参照される可能性があるので、便宜上、BITのサイズは1大きい値で作っておく
 ====区間の和も欲しい場合====
-  * $a_s$から$a_t$までに一律$x$を加算（$1 \le s \le t \le n$）
+  * $a_s～a_t$ に一律 $x$ を加算（$1 \le s \le t \le n$）
-  * $a_s$から$a_t$までの合計を得る（$1 \le s \le t \le n$）
+  * $a_s～a_t$ の合計を得る（$1 \le s \le t \le n$）
 <del>よくわからんけど、</del>上記の応用で、BITを2個使うことでできる。