树状数组 $O(logn)$

解题思路

对于区间修改这个还是用的是差分思想来处理，那么既然这样那就需要对第一次前缀和再求前缀和，会出现一个三角形的数值相加，通过将这个三角形补全可得一个计算公式
$(n+1)*(t_1 + t_2 + t_3 +…+ t_n)-(1t_1 + 2t_2 + 3t_3 +…+ nt_n)$
$\sum_{i=1}^n t_i*(n+1) - \sum_{i=1}^n i*t_i$
这时候只需要维护 $t_i$ 和 $i*t_i$ 这两个树状数组即可。

C++ 代码

#include <iostream>

using namespace std;

typedef long long ll;
const int N = 100010;
int a[N],n,m;
ll t[N],ti[N];

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

void add(ll t[],int x,ll c){
    for(int i = x;i <= N;i += lowbit(i)) {
        t[i] += c;
    }
}

ll sum (ll t[],int x) {
    ll res = 0;
    for(int i = x;i;i-=lowbit(i)) {
        res += t[i];
    }
    return res;
}

ll prefix_sum(int x) {
    return sum(t,x)*(x+1)-sum(ti,x);
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]);

    for(int i = 1;i <= n;i++) {
        int y = a[i]-a[i-1];
        add(t,i,y);
        add(ti,i,(ll)y*i);
    }
    char op[2];
    int l,r,d;
    while(m--) {
        scanf("%s%d%d",op,&l,&r);
        if(*op == 'Q') {
            printf("%lld\n",prefix_sum(r)-prefix_sum(l-1));
        } else {
            scanf("%d",&d);
            add(t,l,d);
            add(t,r+1,-d);
            add(ti,l,l*d);
            add(ti,r+1,(r+1)*-d);
        }
    }
    return 0;
}