概要

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)\)

using ll = long long;
#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)

戻る