莫欺少年穷，修魔之旅在这开始—>算法提高课题解

线段树思路：

1. 先初始化线段树
2. pushdown 需要懒标记，pushdown 完后将懒标记清零
3. 修改的时候需要记录懒标记
4. 修改和查询操作的时候都需要 pushdown
5. 建立和修改操作的时候都需要 pushup

可参考： 树状数组方法

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010;

int n,m;
int a[N];
struct Node
{
    int l,r;
    LL sum,add;
}tr[N*4]; //开四倍空间

//由子节点求父节点
void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

//需要懒标记来计算后面的所有节点
void pushdown(int u)
{
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];

    if(root.add)
    {
        left.add+=root.add,left.sum+=(left.r-left.l+1)*root.add;
        right.add+=root.add,right.sum+=(right.r-right.l+1)*root.add;

        //懒标记清零
        root.add=0;
    }
}

//初始化线段树
void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,a[l],0};
    else 
    {
        tr[u]={l,r};

        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);

        //不要忘了回溯更新
        pushup(u);
    }
}

//区间修改
void modify(int u,int l,int r,int d)
{
    if(tr[u].l>=l&&tr[u].r<=r) 
    {
        tr[u].sum+=(tr[u].r-tr[u].l+1)*d;

        //记录懒标记
        tr[u].add+=d;
    }
    else 
    {
        //修改需要pushdown
        pushdown(u);

        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,d);
        if(r>mid) modify(u<<1|1,l,r,d);

        //不要忘了回溯更新
        pushup(u);
    }
}

//区间查询
LL query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;

    //查询需要pushdown
    pushdown(u);

    int mid=tr[u].l+tr[u].r>>1;
    LL sum=0;
    if(l<=mid) sum=query(u<<1,l,r);
    if(r>mid) sum+=query(u<<1|1,l,r);

    return sum;
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>a[i];

    build(1,1,n);

    char op;
    int l,r,d;
    while(m--)
    {
        cin>>op>>l>>r;

        //区间修改
        if(op=='C')
        {
            cin>>d;
            modify(1,l,r,d);
        }
        //区间查询
        else cout<<query(1,l,r)<<endl;
    }

    return 0;
}