【模板】树状数组 3(Fenwick Tree 3) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
using namespace std;

struct BIT {
    int n;
    vector<long long> b1, b2;
    BIT(int n) : n(n), b1(n + 1, 0), b2(n + 1, 0) {}
    void add(int idx, long long v) {
        long long v2 = v * idx;
        for (int i = idx; i <= n; i += i & -i) {
            b1[i] += v;
            b2[i] += v2;
        }
    }
    void range_add(int l, int r, long long v) {
        add(l, v);
        if (r + 1 <= n) add(r + 1, -v);
    }
    long long prefix_sum(int idx) {
        long long s1 = 0, s2 = 0;
        for (int i = idx; i > 0; i -= i & -i) {
            s1 += b1[i];
            s2 += b2[i];
        }
        return (idx + 1) * s1 - s2;
    }
    long long range_sum(int l, int r) {
        return prefix_sum(r) - prefix_sum(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    BIT bit(n);
    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        bit.range_add(i, i, x);
    }
    for (int i = 0; i < q; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            long long x;
            cin >> l >> r >> x;
            bit.range_add(l, r, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << bit.range_sum(l, r) << "\n";
        }
    }
    return 0;
}