差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:binary_indexed_tree [2020/06/04] – ikatakos | programming_algorithm:data_structure:binary_indexed_tree [2020/06/04] – [概要] ikatakos | ||
---|---|---|---|
行 9: | 行 9: | ||
* 数列 $a_1, | * 数列 $a_1, | ||
* 以下の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_s~a_t$ の合計を得る($1 \le s \le t \le N$) |
Binary Indexed Treeは、この2つを高速に行える。 | Binary Indexed Treeは、この2つを高速に行える。 |