BIT（Binary Index Tree）の実装

他ライブラリ（転倒数等）で活用されることがあるので置いておく。

前提

• Fenwick Treeとも
• 競プロにおいては、BITでできることは以下の2点であると抑えておこう。
  • 累積和テーブルの更新: add
  • 指定した区間の累積和の計算: sum
• 機能を限定することで扱いやすくしたセグメント木ととも捉えられる。（BITでできることは基本セグ木でもできる）
• BITの実装の特性から、データ構造の開始の添え字は1になっている。（詳しくは下の解説PDFを参照）

BITのわかりやすい解説

http://hos.ac/slides/20140319_bit.pdf

実装

/**
 * Binary Index Tree
 * パラメータの添え字は全て1-indexである点に注意する
 */
template<typename T>
class BIT {
  private:
  int n;
  vector<T> d;
  
  public:
  BIT(int n=0):n(n),d(n+1) {}
  
  /// i以降の累積和にxを加算
  void add(int i, T x=1) {
    for (; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  
  /// 閉区間[1,i]の累積和を求める
  T sum(int i) {
    T x = 0;
    for (; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  
  /// 閉区間[l,r]の累積和を求める
  T sum(int l, int r) {
    return sum(r) - sum(l-1);
  }
};

検証用問題

onlinejudge.u-aizu.ac.jp

余談

  BIT(int n=0):n(n),d(n+1) {}

完全に余談ですが、上記の様なコンストラクタの初期化形式をメンバイニシャライザと呼びます。（度々通称を忘れてしまうのでメモ）