Fenwick木

説明

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

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

• z[k] = z[k] + a と更新する．
• z[i] + z[i+1] + ... + z[j] を計算する．

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

計算量

• add: O(log n)．
• sum: O(log n)，

使い方

• add(k, a) == v[k] = v[k] + a
• sum(i, j) == v[i] + ... + v[j] (両端を含む)

ソースコード

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