[LOJ132] 树状数组 3 ：区间修改，区间查询

维护序列，支持区间加、区间求和。(n leq 10^6)

Solution

由于数据较大，不得不使用二次差分 BIT

设原数列为 (a_i)，令 (a_i = sum_{j=1}^i d_i)，则

[sum_{i=1}^k a_i = (k+1) sum_{i=1}^k d_i-sum_{i=1}^k id_i ]

于是我们先对原始 (a_i) 求出 (d_i)，然后用两个 BIT 来维护即可

修改时只需要将 (d_l+x)，将 (d_{r+1}-x)（idx 也对应修改）

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2000005;
#define lowbit(x) ((x)&(-(x)))

void add(int *ar, int i, int v) {
	for (; i < N; ar[i] += v, i += lowbit(i));
}
int sum(int *ar, int i) {
	int s = 0;
	for (; i > 0; s += ar[i], i -= lowbit(i));
	return s;
}

int a[N],d[N],id[N],t1,t2,t3,t4,n,m;

int getans(int k) {
    return (k)*sum(d,k)-sum(id,k);
}

signed main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i], add(d,i,a[i]-a[i-1]), add(id,i,(i-1)*(a[i]-a[i-1]));
    for(int i=1;i<=m;i++) {
        cin>>t1>>t2>>t3;
        if(t1==1) {
            cin>>t4;
            add(d,t2,t4);
            add(d,t3+1,-t4);
            add(id,t2,(t2-1)*t4);
            add(id,t3+1,-(t3)*t4);
        }
        else {
            cout<<getans(t3)-getans(t2-1)<<endl;
        }
    }
}