DataStructure/BinaryIndexedTree.cpp

Back to top page

• category: DataStructure
• View this file on GitHub
  • Last commit date: 2020-04-26 13:55:32+09:00

Description

数列 A を管理する。全て 0-indexed。
add(k,x) : A_k に x を加算する。 O(log N)
get(k) : A の [0,k] における和を返す。 O(log N)
get(l,r) : A の [l,r) における和を返す。 O(log N)

Verified with

• Test/BinaryIndexedTree.test.cpp
• Test/HLDpath.test.cpp
• Test/HLDsubtree.test.cpp

Code

//@docs Docs/BinaryIndexedTree.md
template <class T>
struct BinaryIndexedTree {
    int n;
    vector<T> dat;
    BinaryIndexedTree(const int &n) : n(n + 1), dat(n + 1) {}
    void add(int k, const T &x) {
        for (++k; k < n; k += k & -k) dat[k] += x;
    }
    T get(int k) {
        T res = 0;
        for (++k; k > 0; k -= k & -k) res += dat[k];
        return res;
    }
    inline T get(const int &l, const int &r) { //0-indexed [l,r)
        return get(r - 1) - get(l - 1);
    }
};

#line 1 "DataStructure/BinaryIndexedTree.cpp"
//@docs Docs/BinaryIndexedTree.md
template <class T>
struct BinaryIndexedTree {
    int n;
    vector<T> dat;
    BinaryIndexedTree(const int &n) : n(n + 1), dat(n + 1) {}
    void add(int k, const T &x) {
        for (++k; k < n; k += k & -k) dat[k] += x;
    }
    T get(int k) {
        T res = 0;
        for (++k; k > 0; k -= k & -k) res += dat[k];
        return res;
    }
    inline T get(const int &l, const int &r) { //0-indexed [l,r)
        return get(r - 1) - get(l - 1);
    }
};

Back to top page