C++ – 二维树状数组

struct fenwick_tree_2d_t {
    lli n, m;
    array2d_t<lli> tre;

    fenwick_tree_2d_t(lli n, lli m) : n(n), m(m), tre(n + 1, m + 1, 0) { }

    lli lowbit(lli x) { return x & -x; }

    void build(lli** arr) {
        for (lli i = 1; i <= n; ++i)
            for (lli j = 1; j <= m; ++j)
                upd(i, j, arr[i][j]);
    }

    void upd(lli t, lli q, lli x) {
        for (lli i = t; i <= n; i += lowbit(i))
            for (lli j = q; j <= m; j += lowbit(j))
                tre[{ i, j }] += x;
    }

    lli ask(lli t, lli q) {
        lli res = 0;
        for (lli i = t; i > 0; i -= lowbit(i))
            for (lli j = q; j > 0; j -= lowbit(j))
                res += tre[{ i, j }];
        return res;
    }

    lli ask(lli tl, lli ql, lli tr, lli qr) {
        if (tl > tr || ql > qr) return 0;
        return ask(tr, qr) - ask(tr, ql - 1) - ask(tl - 1, qr) + ask(tl - 1, ql - 1);
    }
};