説明

Fenwick Tree とも呼ばれる。数列に対し, ある要素に値を加える操作と, 区間和を求める操作をそれぞれ対数時間で行うことが出来るデータ構造。セグメント木や平衡二分探索木の機能を制限したものであるが, 実装が非常に単純で定数倍も軽いなどの利点がある。

計算量

  • クエリ $O(\log N)$

実装例

  • BinaryIndexedTree($sz$): 長さ $sz$ で初期化する。
  • sum($k$): 区間 $[0,k]$ の合計を求める(閉区間なので注意)。
  • add($k$, $x$): 要素 $k$ に値 $x$ を加える。
template< typename T >
struct BinaryIndexedTree {
  vector< T > data;

  BinaryIndexedTree(int sz) {
    data.assign(++sz, 0);
  }

  T sum(int k) {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, T x) {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};

検証

AOJ DSL_2_B Range Sum Query

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"

#include "../../template/template.cpp"

#include "../binary-indexed-tree.cpp"

int main() {
  int N, Q;
  scanf("%d %d", &N, &Q);
  BinaryIndexedTree< int > bit(N);
  while(Q--) {
    int T, X, Y;
    scanf("%d %d %d", &T, &X, &Y);
    if(T == 0) bit.add(X - 1, Y);
    else printf("%d\n", bit.sum(Y - 1) - bit.sum(X - 2));
  }
}