线段树

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

const int MAXN=(int)1e5+10;

struct Segtree{
  int l,r;
  ll sum,add;
} t[MAXN*4];

int a[MAXN];

void build(int p,int L,int R);
void spread(int p);
void update(int p,int L,int R,int d);
ll query(int p,int L,int R);

int main()
{
  int n,m;
  cin>>n>>m;
  for (int i=1;i<=n;i++) {
    scanf("%d",a+i);
  }
  build(1,1,n);
  for (int i=0;i<m;i++) {
    char ord[4];
    int l,r;
    scanf("%s%d%d",ord,&l,&r);
    if (ord[0]=='C') {
      int d;
      scanf("%d",&d);
      update(1,l,r,d);
    } else {
      ll ans=query(1,l,r);
      printf("%lld\n",ans);
    }
  }
  return 0;
}

void build(int p,int L,int R)
{
  t[p].l=L,t[p].r=R;
  if (L==R) {
    t[p].sum=a[L];
    return;
  }
  
  int mid=(L+R)/2,ls=p*2,rs=ls+1;
  build(ls,L,mid);
  build(rs,mid+1,R);
  t[p].sum=t[ls].sum+t[rs].sum;
}

void spread(int p)
{
  ll &add=t[p].add;
  if (add!=0) {
    int ls=p*2,rs=ls+1;
    t[ls].sum+=add*(t[ls].r-t[ls].l+1);
    t[rs].sum+=add*(t[rs].r-t[rs].l+1);
    t[ls].add+=add;
    t[rs].add+=add;
    add=0;
  }
}
  
void update(int p,int L,int R,int d)
{
  if (L<=t[p].l && t[p].r<=R) {
    t[p].sum+=(ll)(t[p].r-t[p].l+1)*d;
    t[p].add+=d;
    return;
  }
  
  spread(p);
  int mid=(t[p].l+t[p].r)/2,ls=p*2,rs=ls+1;
  if (L<=mid) {
    update(ls,L,R,d);
  }
  if (R>mid) {
    update(rs,L,R,d);
  }
  t[p].sum=t[ls].sum+t[rs].sum;
}
  
ll query(int p,int L,int R)
{
  if (L<=t[p].l && t[p].r<=R) {
    return t[p].sum;
  }
  
  spread(p);
  int mid=(t[p].l+t[p].r)/2,ls=p*2,rs=ls+1;
  ll ans=0;
  if (L<=mid) {
    ans+=query(ls,L,R);
  }
  if (R>mid) {
    ans+=query(rs,L,R);
  }
  return ans;
}