Spaghetti Source logo

Fenwick木

説明

Fenwick木は,累積値を計算するためのデータ構造である.扱える代数構造を制限することにより,Range Minimum Query の記憶容量を節約したものと見なすこともできる.

Fenwick 木は次の操作を許すデータ構造である.

取り扱える演算子 + には結合性,可換性,可逆性を要求する.すなわち加群である必要がある.

計算量

使い方

ソースコード

template <class T>
struct fenwick_tree {
  vector<T> x;
  fenwick_tree(int n) : x(n, 0) { }
  T sum(int i, int j) {
    if (i == 0) {
      T S = 0;
      for (j; j >= 0; j = (j & (j + 1)) - 1) S += x[j];
      return S;
    } else return sum(0, j) - sum(0, i-1);
  }
  void add(int k, T a) {
    for (; k < x.size(); k |= k+1) x[k] += a;
  }
};

Verified

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.08.09 22:38:37.