时间复杂度
mlog(n) + nlog(n)
C++ 代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5+10;
int n,m;
int a[N],tr1[N],tr2[N];
int lowbit(int x)
{
return x & - x;
}
int add(int tr[],int x,int c)
{
for(int i=x;i<=n;i += lowbit(i)) tr[i] += c;
}
int sum(int tr[],int x)
{
int res = 0;
for(int i=x;i;i -= lowbit(i)) res += tr[i];
return res;
}
int special_sum(int lim)
{
return (lim + 1) * sum(tr1,lim) - sum(tr2,lim);
}
void zxy()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i = 1;i<=n;i++)
{
int x = a[i] - a[i-1];
add(tr1,i,x);
add(tr2,i,i*x);
}
while(m--)
{
char op;int x = 0, y=0, z=0;
cin>>op;
if(op == 'C')
{
cin>>x>>y>>z;
add(tr1,x,z); add(tr2,x,x * z);
add(tr1,y+1,-z); add(tr2,y+1,(y+1) * (-z));
}
if(op == 'Q')
{
cin>>x>>y;
cout<<special_sum(y) - special_sum(x-1)<<endl;
}
}
}
signed main()
{
int t = 1; //cin>>t;
while(t--) zxy();
return 0;
}