← all categories

Fenwick 2d 4d1b64cb

2D Fenwick tree. Point update, rectangle sum query, 1-indexed interface. T needs operator+, operator-, and a default-constructed zero.

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

content/data-structures/fenwick-2d.h

template <typename T>
struct Fenwick2D {
    int n, m;
    vector<vector<T>> tree;

    Fenwick2D(int n, int m) : n(n), m(m), tree(n + 1, vector<T>(m + 1, T())) {}

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

    T sum(int r, int c) {
        T res = T();
        for (; r; r -= r & -r)
            for (int x = c; x; x -= x & -x) res += tree[r][x];
        return res;
    }

    T sum(int r1, int c1, int r2, int c2) {
        return sum(r2, c2) - sum(r1 - 1, c2) - sum(r2, c1 - 1) + sum(r1 - 1, c1 - 1);
    }
};