できること、したいこと、うれしいこと、など

  • 累積和(累積度数表)を効率的に計算、更新できる。
  • 競技プログラミングでは区間の和を求めるのに使われることがある。
  • 実装が簡単
  • 累積頻度表の更新、参照に$O(lg\ n)$、空間計算量に$O(n)$を必要とする。
  • BITまたはFenwick Treeと呼ばれている
  • 1994年(結構最近!?)にFenwickさんによって作られた。 ("A New Data Structure for Cumulative Frequency Tables")

実装

1d.

template <class T>
struct BIT {
    int N;
    std::vector<T> bit;
    BIT(int N) : N(N) {
        bit.resize(N + 1);
        fill_n(begin(bit), N + 1, 0);
    }
    void add(int i, T x) {
        i++;
        while (i <= N) {
            bit[i] += x;
            i += i & -i; // i & (-i) は最下位ビットを求めている。
    }
    T sum(int i) {
        T s{0};
        while (i > 0) {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    T sum(int a, int b) { return sum(b) - sum(a); }
};

2d. サイズがN*MのBITはサイズがNのBITをM個持てば良い。

template <class T>
struct BIT2d {
    int N, M;
    std::vector<vector<T> > bit;
    BIT2d(int N, int M) : N(N), M(M) {
        bit.resize(N + 1, vector<T>(M + 1));
        // fill_n(begin(bit), N + 1, 0);
    }
    void add(int x, int y, T v) {
        for (int i = x; i <= N; i += i & (-i))
            for (int j = y; j <= M; j += j & (-j)) bit[i][j] += v;
    }
    T sum(int x, int y) {
        T s{0};
        for (int i = x; i > 0; i -= i & (-i))
            for (int j = y; j > 0; j -= j & (-j)) s += bit[i][j];
        return s;
    }
    T sum(int x1, int y1, int x2, int y2) {
        return sum(x2, y2) - sum(x1, y1) - sum(x2, y1) + sum(x1, y1);
    }
};