线段树模板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10,inf = 0x3f3f3f3f;
int n,m,a[N],add[N * 4];
ll sum[N * 4];
void build(int k,int l,int r) //建树 
{
    if(l == r)
    {
        sum[k] = a[l];return ;
    }
    int mid = (l + r) / 2;
    build(k * 2,l,mid);
    build(k * 2 + 1,mid + 1,r);
    sum[k] = sum[k * 2] + sum[k * 2 + 1];
}
void Add(int k,int l,int r,int v) //区间加并更新
{
    add[k] += v;
    sum[k] += ll(v) * (r - l + 1); 
} 
void pushdown(int k,int l,int r,int mid) //标记下传 
{
    if(add[k] == 0)return;
    Add(k * 2,l,mid,add[k]);
    Add(k * 2 + 1,mid + 1,r,add[k]);
    add[k] = 0;
}
ll query(int k,int l,int r,int x,int y) //查询x到y区间的和 
{
    if(l >= x && r <= y)return sum[k];
    int mid = (l + r) / 2;
    ll res = 0;
    pushdown(k,l,r,mid);
    if(x <= mid)res += query(k * 2,l,mid,x,y);
    if(mid < y)res += query(k * 2 + 1,mid+1,r,x,y);
    return res; 
}
void modify(int k,int l,int r,int x,int y,int v) //x到y的区间加v 
{
    if(l >= x && r <= y)return Add(k,l,r,v);
    int mid = (l + r) / 2;
    pushdown(k,l,r,mid);
    if(x <= mid)modify(k * 2,l,mid,x,y,v);
    if(mid < y)modify(k * 2 + 1,mid + 1,r,x,y,v);
    sum[k] = sum[k * 2] + sum[k * 2 + 1]; 
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--)
    {
        char op;int x,y,z;
        while((op=getchar())!='Q'&&op!='C');
        scanf("%d %d",&x,&y);
        if(op=='Q')
        {
            printf("%lld\n",query(1,1,n,x,y));
        }
        else
        {
            scanf("%d",&z);
            modify(1,1,n,x,y,z);
        }
    }
     return 0;
}