C++ – 树状数组 Fenwick Tree

struct fenwick_tree_t {
    lli n;
    vector<lli> tre;

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

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

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

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

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

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

发表回复