差分

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

--- programming_algorithm:data_structure:binary_indexed_tree [2020/02/26] – [累積和の二分探索] ikatakos
+++ programming_algorithm:data_structure:binary_indexed_tree [2020/06/04] – [概要] ikatakos
@@ 行 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     ...
 =====区間に対する更新=====
-上記のBit.add()は、点に対する更新しか行えない。では「a3～a7に一律に5を加算」などが必要な場合にどうするか。
+上記のBit.add()は、点に対する更新しか行えない。では「$a_3～a_7$ に一律に5を加算」などが必要な場合にどうするか。
 ====区間の和が必要ない場合====
@@ 行 65: / 行 80: @@
 区間の和は必要なく、ある指定した位置の値だけわかれば良い場合。つまり、
-  *  $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個使うことでできる。