Binary-Indexed-Tree(BIT)
(structure/others/binary-indexed-tree.hpp)

• View this file on GitHub
• Last update: 2022-09-11 00:53:50+09:00
• Include: #include "structure/others/binary-indexed-tree.hpp"

概要

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

使い方

• BinaryIndexedTree(sz): 長さ sz の $0$ で初期化された配列で構築する.
• BinaryIndexedTree(vs): 配列 vs で構築する.
• apply(k, x): 要素 k に値 x を加える.
• prod(r): 区間 $[0,r)$ の総和を求める.
• prod(l, r): 区間 $[l, r)$ の総和を求める.
• lower_bound(x): 区間 $[0,k]$ の総和が x 以上となる最小の $k$ を返す. 数列が単調増加であることを要求する.
• upper_bound(x): 区間 $[0,k]$ の総和が x を上回る最小の $k$ を返す. 数列>が単調増加であることを要求する.

計算量

• 構築: $O(N)$
• クエリ: $O(\log N)$

Required by

• Dynamic Point Add Rectangle Sum (other/dynamic-point-add-rectangle-sum.hpp)
• Static Point Add Rectangle Sum (other/static-point-add-rectangle-sum.hpp)
• Static Rectangle Add Rectangle Sum (other/static-rectangle-add-rectangle-sum.hpp)
• Wavelet Matrix Point Add Rectangle Sum (structure/wavelet/wavelet-matrix-point-add-rectangle-sum.hpp)

Verified with

• test/verify/aoj-2270.test.cpp
• test/verify/aoj-dsl-2-b.test.cpp
• test/verify/yosupo-point-add-rectangle-sum-3.test.cpp
• test/verify/yosupo-point-add-rectangle-sum.test.cpp
• test/verify/yosupo-rectangle-sum-2.test.cpp
• test/verify/yosupo-static-range-inversions-query.test.cpp

Code

/**
 * @brief Binary-Indexed-Tree(BIT)
 * @docs docs/binary-indexed-tree.md
 */
template< typename T >
struct BinaryIndexedTree {
private:
  int n;
  vector< T > data;

public:
  BinaryIndexedTree() = default;

  explicit BinaryIndexedTree(int n) : n(n) {
    data.assign(n + 1, T());
  }

  explicit BinaryIndexedTree(const vector< T > &v) :
      BinaryIndexedTree((int) v.size()) {
    build(v);
  }

  void build(const vector< T > &v) {
    assert(n == (int) v.size());
    for(int i = 1; i <= n; i++) data[i] = v[i - 1];
    for(int i = 1; i <= n; i++) {
      int j = i + (i & -i);
      if(j <= n) data[j] += data[i];
    }
  }

  void apply(int k, const T &x) {
    for(++k; k <= n; k += k & -k) data[k] += x;
  }

  T prod(int r) const {
    T ret = T();
    for(; r > 0; r -= r & -r) ret += data[r];
    return ret;
  }

  T prod(int l, int r) const {
    return prod(r) - prod(l);
  }

  int lower_bound(T x) const {
    int i = 0;
    for(int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) {
      if(i + k <= n && data[i + k] < x) {
        x -= data[i + k];
        i += k;
      }
    }
    return i;
  }

  int upper_bound(T x) const {
    int i = 0;
    for(int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) {
      if(i + k <= n && data[i + k] <= x) {
        x -= data[i + k];
        i += k;
      }
    }
    return i;
  }
};

#line 1 "structure/others/binary-indexed-tree.hpp"
/**
 * @brief Binary-Indexed-Tree(BIT)
 * @docs docs/binary-indexed-tree.md
 */
template< typename T >
struct BinaryIndexedTree {
private:
  int n;
  vector< T > data;

public:
  BinaryIndexedTree() = default;

  explicit BinaryIndexedTree(int n) : n(n) {
    data.assign(n + 1, T());
  }

  explicit BinaryIndexedTree(const vector< T > &v) :
      BinaryIndexedTree((int) v.size()) {
    build(v);
  }

  void build(const vector< T > &v) {
    assert(n == (int) v.size());
    for(int i = 1; i <= n; i++) data[i] = v[i - 1];
    for(int i = 1; i <= n; i++) {
      int j = i + (i & -i);
      if(j <= n) data[j] += data[i];
    }
  }

  void apply(int k, const T &x) {
    for(++k; k <= n; k += k & -k) data[k] += x;
  }

  T prod(int r) const {
    T ret = T();
    for(; r > 0; r -= r & -r) ret += data[r];
    return ret;
  }

  T prod(int l, int r) const {
    return prod(r) - prod(l);
  }

  int lower_bound(T x) const {
    int i = 0;
    for(int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) {
      if(i + k <= n && data[i + k] < x) {
        x -= data[i + k];
        i += k;
      }
    }
    return i;
  }

  int upper_bound(T x) const {
    int i = 0;
    for(int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) {
      if(i + k <= n && data[i + k] <= x) {
        x -= data[i + k];
        i += k;
      }
    }
    return i;
  }
};

Back to top page