原题链接

终极版树状数组(差分思想)

支持操作：
1. 区间求和 Sum: a[L~R]
2. 区间更新 a[L~R] += c

分析：
- 因为要对一段区间快速进行修改，所以我们还是要用到差分的思想。a[L ~ R] + c，即b[L] += c, b[R + 1] -= c
其中 b[i] = a[i] - a[i - 1], i = 1,2,…n
- 我们可以快速求出a[x]，即求b[1~x]的前缀和（树状数组logn可以实现）比较难的是，如何快速以logn复杂度求出a[1~x]。
这里其实要用两重循环即a[1~x] = $\sum^x_{i=1} \sum^i _{j = 1} b_j$，通过化简我们可以得到以下公式：
$$(b_1 + \cdots+b_n) * (x + 1) - (b_1 + 2 *b_2 + \cdots + x * b_x)$$
所以原来我们只维护一个前缀和，现在维护两个前缀和即可

知识点
1：你更新了$b_i$后，相应的tr1数组和tr2数组都要进行add更新
2：这个题很多地方要用long long，因为你要求区间和a[l~r]这个值会超过int

评论区

问答

C++代码：

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 1e5 + 7;
int n, m;
LL a[N];
LL tr1[N]; // 维护b[i]的前缀和
LL tr2[N]; // 维护b[i] * i的前缀和


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

// 树状数组的tr1维护的底部数组：b[1], b[2], b[3], ... , b[n]
// 树状数组的tr2维护的底部数组：1*b[1], 2*b[2], 3*b[3], ... , n*b[n]
LL query(LL tr[], int x) {
    LL res = 0;
    for (int i = x; i >= 1; i -= lowbit(i)) res += tr[i];
    return res;
}

void add(LL tr[], int x, LL c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c; 
}

LL prefix_sum(int x) {
    return query(tr1, x) * 1ll * (x + 1) - query(tr2, x); // 以logn求a[1~x]的前缀和
}

int main() {
    cin >> n >> m;

    // 差分：插入初始元素值
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        add(tr1, i, a[i]); add(tr1, i + 1, -a[i]);
        add(tr2, i, i * a[i]); add(tr2, i + 1, -a[i] * (i + 1));
    }

    for (int i = 1; i <= m; i ++) {
        string s;
        int l, r, c;
        cin >> s >> l >> r;
        if (s == "Q") {
            // 以logn复杂度求动态的区间和a[l~r]
            cout << prefix_sum(r) - prefix_sum(l - 1) << endl;
        } else {
            cin >> c;
            add(tr1, l, c); add(tr1, r + 1, -c);
            add(tr2, l, c * l); add(tr2, r + 1, -c * (r + 1));
        }
    }

    return 0;
}