线段树的模板
线段树讲解

#include <bits/stdc++.h>
#define fill(arr,val) memset(arr,var,sizeof(arr)
using namespace std;
const int maxn=1e5+50;
const int mod=1e9+7;
typedef long long ll;
struct node
{
    int l,r;
    ll sum,lazy;
    void update(ll x)
    {
        sum+=(r-l+1)*x;
        lazy+=x;
    }
}node[4*maxn];
int n,q,a[maxn];
void pushdown(int root)
{
    if(node[root].lazy)
    {
        node[root*2].update(node[root].lazy);
        node[root*2+1].update(node[root].lazy);
        node[root].lazy=0;
    }
}
void pushup(int root)
{
    node[root].sum=node[root*2].sum+node[root*2+1].sum;
}
void build(int root,int l,int r)
{
    node[root].l=l;
    node[root].r=r;
    node[root].lazy=0;
    node[root].sum=0;
    if(l==r)node[root].sum=a[l];
    else
    {
        int mid=l+(r-l)/2;
        build(root*2,l,mid);
        build(root*2+1,mid+1,r);
        pushup(root);
    }
}
void update(int root,int st,int ed,int val)
{
    int l=node[root].l;
    int r=node[root].r;
    if(st>r||ed<l)return;
    if(st<=l&&ed>=r)
    {
        node[root].update(val);
    }
    else
    {
        pushdown(root);
        update(root*2,st,ed,val);
        update(root*2+1,st,ed,val);
        pushup(root);
    }
}
ll query(int root,int st,int ed)
{
    int l=node[root].l;
    int r=node[root].r;
    if(st>r||ed<l)return 0;
    if(st<=l&&ed>=r)return node[root].sum;
    else
    {
        ll ans=0;
        pushdown(root);
        ans+=query(root*2,st,ed);
        ans+=query(root*2+1,st,ed);
        pushup(root);
        return ans;
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        char ch;
        cin>>ch;
        int x,y,z;
        if(ch=='Q')
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,x,y));
        }
        if(ch=='C')
        {
            scanf("%d%d%d",&x,&y,&z);
            update(1,x,y,z);
        }
    }
    return 0;
}