差分

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

--- programming:algorithm:data_structure:binary_indexed_tree [2017/06/12] – ikatakos
+++ programming_algorithm:data_structure:binary_indexed_tree [2019/11/07] – ikatakos
@@ 行 1: / 行 1: @@
 ======Binary Indexed Tree======
+=====概要=====
 [[http://hos.ac/slides/20140319_bit.pdf|Binary Indexed Tree のはなし - hos.ac]][pdf]
@@ 行 5: / 行 7: @@
 Range Sum Query（区間の和）に対する効率的なデータ構造
-  * 数列$a_1,a_2,...,a_n$について、「$a_1$から$a_x$までの合計」を高速に求められる。（$1 \le x \le n$）
+  * 数列$a_1,a_2,...,a_n$がある
-  * 任意の箇所の値が変わっても、更新も高速に行える
+  * 以下の2つの要求を処理する
+    * $a_i$に$x$を加算（$1 \le i \le n$）
+    * $a_s$から$a_t$までの合計を得る（$1 \le s \le t \le n$）
+Binary Indexed Treeは、この2つを高速に行える。
+これだけ見ると「そんなのが何の役に立つの？」って感じだが、頭のいい人だと全然関係ないように見える問題を変換して効率的に解いたりしちゃうらしい。
-これだけ見ると「そんなシチュエーションあるの？」って感じだが、頭のいい人だと全然関係ないように見える問題をこれ使って効率的に解いたりしちゃうらしい。
+=====実装=====
 詳しい説明は上のpdfで懇切丁寧に行われているので、Pythonコードだけメモ。
@@ 行 40: / 行 48: @@
 print(bit.sum(6) - bit.sum(3))  # a4～a6の合計 => 5
 </sxh>
+注意点として、配列のindex等と異なり、添え字は1から始まる。そうしないと効率的に上下の要素を特定できないため。
+                ８
+        ４
+    ２      ６
+  １  ３  ５  ７  ９ ...
 =====区間に対する更新=====
@@ 行 47: / 行 63: @@
 ====区間の和が必要ない場合====
-区間の和は必要なく、ある指定した位置の値だけわかれば良い場合。
+区間の和は必要なく、ある指定した位置の値だけわかれば良い場合。つまり、
+  * $a_s$から$a_t$までに一律$x$を加算（$1 \le s \le t \le n$）
+  * $a_i$の値を得る（$1 \le i \le n$）
 この場合は、差分に着目することで、BITをそのまま利用できる。（上記pdf参照）
-  * 「$s$～$t$の区間に一律$x$を加算」→「$s$に$x$、$t+1$に$-x$を加算」
+  * $s$～$t$に一律$x$を加算→「$s$に$x$、$t+1$に$-x$を加算」
-  * 「位置$i$の値を取得」→「$a_1$～$a_i$の合計を取得」
+  * 位置$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$までの合計を得る（$1 \le s \le t \le n$）
 <del>よくわからんけど、</del>上記の応用で、BITを2個使うことでできる。
@@ 行 80: / 行 102: @@
+=====区間の最大値・最小値=====
+Segment Treeほどの柔軟性は無いが、いくらかの制約された条件下で、区間最大値・最小値の管理にも使える（以下は最大値の例）
+  * $update(i, x)$: $a_i$ を $x$ で更新する。この際、$x$ は必ず元の $a_i$ 以上でなければならない
+  * $getmax(i)$: $a_1～a_i$ の最大値を取得する。必ず1からの最大値であり、途中からの $a_s～a_t$ は取得できない。
+単純に、上記のコードの加算を、MAXを取る操作に置きかえればよい。
+<sxh python>
+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
+</sxh>
+少し理解は難しくなるが、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]]
+====累積和のlower bound====
+累積和が $x$ のindexや、$x$ を越えない最大のindexとその時の累積和を得ることができる。
+  * [[https://codeforces.com/blog/entry/61364|[Tutorial] Searching Binary Indexed Tree in O(log(N)) using Binary Lifting - Codeforces]]
+<sxh python>
+class Bit:
+    def __init__(self, n): (略)
+    def sum(self, i): (略)
+    def add(self, i, x): (略)
+    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
+</sxh>