差分

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

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:data_structure:binary_indexed_tree [2020/02/26] – [累積和の二分探索] ikatakosprogramming_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] [[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つの要求を処理する   * 以下の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_sa_t$ の合計を得る($1 \le s \le t \le N$)
  
 Binary Indexed Treeは、この2つを高速に行える。 Binary Indexed Treeは、この2つを高速に行える。
行 49: 行 49:
 </sxh> </sxh>
  
-注意点として、配列のindex等と異なり、添え字は1から始まる。そうしないと効率的に上下の要素を特定できないため。+注意点として、配列のindex等と異なり、添え字は1から始まる。その方が効率的に上下の要素を特定できため。
  
   ⇤←←←←←←8   ⇤←←←←←←8
行 55: 行 55:
   ⇤2    ⇤6    ⇤10   ⇤2    ⇤6    ⇤10
   1  3  5  7  9   ...   1  3  5  7  9   ...
 +
 +添え字を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     ...
 +
  
  
 =====区間に対する更新===== =====区間に対する更新=====
  
-上記のBit.add()は、点に対する更新しか行えない。では「a3a7に一律に5を加算」などが必要な場合にどうするか。+上記のBit.add()は、点に対する更新しか行えない。では「$a_3a_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参照) この場合は、差分に着目することで、BITをそのまま利用できる。(上記pdf参照)
  
-  * $s$$t$に一律$x$を加算→「$s$に$x$、$t+1$に$-x$を加算」 +  * $a_sa_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_sa_t$ に一律 $x$ を加算($1 \le s \le t \le n$) 
-  * $a_s$から$a_t$までの合計を得る($1 \le s \le t \le n$)+  * $a_sa_t$ の合計を得る($1 \le s \le t \le n$)
  
 <del>よくわからんけど、</del>上記の応用で、BITを2個使うことでできる。 <del>よくわからんけど、</del>上記の応用で、BITを2個使うことでできる。
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