Binary Indexed Tree
(DataStructure/BinaryIndexedTree.cpp)

• View this file on GitHub
• Last update: 2021-04-21 14:12:23+09:00

説明

別名 Fenwick Tree 。配列に対する1点更新クエリと区間和を求めるクエリを Segment Tree より高速に処理出来る。

• BinaryIndexedTree<T> bit(int n) : 長さ $n$ の配列 A[0], A[1], A[2], … , A[n - 1] を構築する。計算量 $O(n)$
• void bit.add(int i,T x) : A[i] += x を行う。計算量 $O(\log n)$
• T bit.sum(int l,int r) : A[l] + A[l + 1] + … + A[r - 1] を求める。計算量 $O(\log n)$

Verified with

• Test/yosupo-judge/BinaryIndexedTree.test.cpp

Code

template <typename T>
class BinaryIndexedTree {
    int N;
    vector<T> bit;

    T sum_sub(int a) {
        a++;
        T ret = 0;
        if(a == 0) return ret;
        while(a > 0) {
            ret += bit[a];
            a -= a & -a;
        }
        return ret;
    }

public:

    BinaryIndexedTree(int n): N(n) {
        bit.assign(++n,0);
    }

    void add(int i,T x) {
        i++;
        if(i == 0) return;
        while(i < bit.size()) {
            bit[i] += x;
            i += i & -i;
        }
    }

    T sum(int l,int r) {
        return sum_sub(r - 1) - sum_sub(l - 1);
    }
};

#line 1 "DataStructure/BinaryIndexedTree.cpp"
template <typename T>
class BinaryIndexedTree {
    int N;
    vector<T> bit;

    T sum_sub(int a) {
        a++;
        T ret = 0;
        if(a == 0) return ret;
        while(a > 0) {
            ret += bit[a];
            a -= a & -a;
        }
        return ret;
    }

public:

    BinaryIndexedTree(int n): N(n) {
        bit.assign(++n,0);
    }

    void add(int i,T x) {
        i++;
        if(i == 0) return;
        while(i < bit.size()) {
            bit[i] += x;
            i += i & -i;
        }
    }

    T sum(int l,int r) {
        return sum_sub(r - 1) - sum_sub(l - 1);
    }
};

Back to top page