题目描述
区间加:原数组变差分
区间求和:差分数组求前缀和,采用矩阵补全的思想
a[x]的值为b1+..+bx;那么a[1]+…+a[x]的值应该为b的两重循环,采用补全矩阵的方法可以转化为:
(b1+…+bx)(x+1) - Σ(ibi)
其中前者为大矩阵的和,后者为补全部分
因此需要维护两个前缀和数组:tr1:bi的差分。tr2:i*bi差分
每次修改操作修改这两个差分的值
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=100010;
int a[N];
int n;
//分别维护b[i],b[i]*i的差分数组
ll tr1[N],tr2[N];
int lowbit(int x)
{
return x&-x;
}
void add(ll tr[],int x,ll c)
{
for(int i=x;i<=n;i+=lowbit(i))
tr[i] += c;
}
ll sum(ll tr[],int x)
{
ll res=0;
for(int i=x;i;i-=lowbit(i))
res+=tr[i];
return res;
}
int main()
{
int m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
//直接将差分数组保存至线段树
for(int i=1;i<=n;i++)
{
ll b=a[i]-a[i-1];
add(tr1,i,b);
add(tr2,i,(ll)b*i);
}
while(m--)
{
char op;
cin>>op;
if(op=='C')
{
int l,r,d;
cin>>l>>r>>d;
add(tr1,l,d);
add(tr1,r+1,-d);
add(tr2,l,d*l);
add(tr2,r+1,-d*(r+1));
//tr[l]+=d;
//tr[r+1]-=d;
}
else
{
int l,r;
cin>>l>>r;
ll sum1=sum(tr1,r)*(r+1)-sum(tr2,r);
ll sum2=sum(tr1,l-1)*l-sum(tr2,l-1);
cout<<sum1-sum2<<endl;
}
}
return 0;
}