← all categories

Fenwick 7c9ea88d

Fenwick tree (BIT). Point update, prefix/range sum, 0-indexed interface. T needs operator+, operator-, and a default-constructed zero.

Time: O(\log n) per operation. tested

content/data-structures/fenwick.h

template <typename T>
struct Fenwick {
    int n;
    vector<T> tree;

    Fenwick(int n) : n(n), tree(n + 1, T()) {}

    void add(int i, T v) {
        for (i++; i <= n; i += i & -i) tree[i] += v;
    }

    T sum(int i) {
        T res = T();
        for (i++; i; i -= i & -i) res += tree[i];
        return res;
    }

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