Binary Indexed Tree (BIT) in C++

C++: BITの実装

BITは、数列においてある区間の合計値を効率良く求めたい場合などに使われるデータ構造である。
計算量は、値の加算、合計値の取得ともにO(log n)。

0-indexed にて実装してみる。

//------------------------------------------------------------------------------
// Binary Indexed Tree (BIT)
//------------------------------------------------------------------------------
template <typename T>
class BinaryIndexedTree {
 public:
  BinaryIndexedTree(int size) : size_(size) {
    data_.resize(size + 1);
  }
  void Add(int index, T value) {
    if (index < 0 || index >= size_) return;
    ++index;
    while (index <= size_) {
      data_[index] += value;
      index += index & -index;
    }
  }
  T Sum(int index) {
    if (index < 0 || index >= size_) return 0;
    ++index;
    T ret = 0;
    while (index > 0) {
      ret += data_[index];
      index -= index & -index;
    }
    return ret;
  }
 private:
  std::vector<T> data_;
  int size_;
};