ei1333's page

ホーム > Wiki

BIT(Binary-Indexed-Tree)

説明

Fenwick Tree とも呼ばれる。数列に対し, ある要素に値を加える操作と, 区間和を求める操作をそれぞれ対数時間で行うことが出来るデータ構造。セグメント木や平衡二分探索木に比べ実装が非常に単純で, 定数倍も軽い。

使い方

計算量

$O(\log N)$

実装例

template< class T >
struct BinaryIndexedTree
{
  vector< T > data;

  BinaryIndexedTree(int sz)
  {
    data.assign(++sz, 0);
  }

  T sum(int k)
  {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, T x)
  {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};

応用: BIT上の二分探索

$\sum_{i=0}^{k} a_k \ge w$ となる最小の $k$ を求めたい(std::lower_bound()のイメージ)とき, BIT上を二分探索することで $O(\log N)$ 時間で行うことができる。

template< class T >
struct AdditionalBIT : BinaryIndexedTree< T >
{
  int curr;

  AdditionalBIT(int sz) : BinaryIndexedTree< T >(sz)
  {
    curr = 1;
    while(curr <= sz) curr <<= 1;
  }

  int lower_bound(T w)
  {
    if(w <= 0) return (0);
    int i = 0;
    for(int k = curr; k > 0; k >>= 1) {
      if(i + k < BinaryIndexedTree< T >::data.size() && BinaryIndexedTree< T >::data[i + k] < w) {
        w -= BinaryIndexedTree< T >::data[i + k];
        i += k;
      }
    }
    return (i);
  }
};

問題例

参考資料