> #include<cstdio>
> #include<iostream>
> 
> using namespace std;
> const int maxn=1e5+1;
> typedef long long ll;
> 
> ll N,Q;
> ll sum1[maxn],sum2[maxn];
> ll a[maxn];
> char c;
> 
> ll lowbit(ll x){return x&-x;}
> 
> void add(ll *arr,ll x,ll c)
> {
>     while(x<=N)
>     {
>         arr[x]+=c;
>         x+=lowbit(x);
>     }
> }
> ll query(ll *arr,ll x)
> {
>     ll ans=0;
>     while(x)
>     {
>         ans+=arr[x];
>         x-=lowbit(x);
>     }
>     return ans;
> }
> 
> int main()
> {
>     cin>>N>>Q;
>     ll x;
>     for(int i=1;i<=N;i++)
>     {
>         scanf("%d",&a[i]);
>         //a[i]+=a[i-1];
>         add(sum1,i,a[i]-a[i-1]);
>         add(sum2,i,i*(a[i]-a[i-1]));
>     }
>     for(int i=1;i<=Q;i++)
>     {
>         cin>>c;
>         if(c=='Q')
>         {
>             ll cur=0;
>             ll x,y;
>             cin>>y>>x;
>             //cur=a[y]-a[x-1];
>             //cur+=query(b,)
>             cur+=(x+1)*query(sum1,x)+query(sum2,y-1);
>             cur-=y*query(sum1,y-1)+query(sum2,x);
>             cout<<cur<<endl;
>         }
>         else{
>                 ll a,b,c;
>                 cin>>a>>b>>c;
>                 add(sum1,a,c),add(sum1,b+1,-c);
>                 add(sum2,a,a*c),add(sum2,b+1,-(b+1)*c);
>         }
>     }
>     return 0;
> }

• Re:WA用树状数组 qwq 有大佬帮忙看一下吗 (101) 1769157748 2020-03-31 15:53:06