概要

Binary Indexed Tree (BIT, Fenwick Tree) は、部分和と要素の更新のクエリを行う木構造である。

配列 \(a_1, a_2, ..., a_N\)を管理するBITは以下のクエリを1回\(O(\log N)\)で処理できる。

  • 部分和 \(a_1 + a_2 + ... + a_i\) を求める

  • \(a_i\)に\(x\)を加える

このBITは、以下の操作が行えるデータ構造とも見なすこともできる

  • \(a_i\) の値を求める

  • \(a_i, a_{i+1}, ..., a_{N}\) に\(x\)を加える

実装(1次元BIT)

\(Q\)個のクエリを処理する場合の計算量は\(O(Q \log N)\)

/* Binary Indexed Tree */
#define N 100008

class BIT {
  int n;
  ll data[N];

public:
  BIT(int n) : n(n) {
    for(int i = 0; i < n+2; ++i) data[i] = 0;
  }
  void add(int k, ll x) {
    while(k <= n) {
      data[k] += x;
      k += k & -k;
    }
  }

  ll get(int k) {
    ll s = 0;
    while(k) {
      s += data[k];
      k -= k & -k;
    }
    return s;
  }
};

Verified

  • AOJ: "DSL_2_E: Range Query - Range Add Query (RAQ)": source (C++11, 0.11sec)