线段树模板

#include<bits/stdc++.h>
using namespace std; 
struct tree{
    //每个节点的基本信息存储 
    int ls,rs;
    //左右儿子节点 
    long long pre,lzy;
    //当前值和懒标记 
}t[400003];
int n,m,a[100003];
void build(int p,int l,int r){
    t[p].ls=l;t[p].rs=r;
    //记录左儿子和右儿子 
    if (l==r){
        t[p].pre=a[l];
        return;
    }
    //递归到了树底，递归终止 
    int mid=(l+r)/2;
    build(2*p,l,mid);
    //递归左儿子 
    build(2*p+1,mid+1,r);
    //递归右儿子 
    t[p].pre=t[2*p].pre+t[2*p+1].pre;
}//建树
void push_down(int p){
    if (t[p].lzy){
        t[p*2].pre+=t[p].lzy*(t[p*2].rs-t[p*2].ls+1);
        //下传需要修改的左儿子的值
        t[p*2+1].pre+=t[p].lzy*(t[p*2+1].rs-t[p*2+1].ls+1);
        //下传需要修改的右儿子的值
        t[p*2].lzy+=t[p].lzy; 
        t[p*2+1].lzy+=t[p].lzy;
        //加上父亲节点的下传值准备再下传给左右儿子 
        t[p].lzy=0;
        //下传完毕，该节点懒标记变为0 
    }
}//进行本质修改和查询 
void change(int p,int x,int y,int z){
    if (x<=t[p].ls && y>=t[p].rs){
        t[p].pre+=z*(t[p].rs-t[p].ls+1);
        t[p].lzy+=z;
        return; 
    }
    //如果当前节点所代表的区间被要求修改的区间覆盖，则直接修改 
    push_down(p);
    //寻找在这个节点下面符合条件的儿子节点 
    int mid=(t[p].rs+t[p].ls)/2;
    if (x<=mid) change(2*p,x,y,z);
    //mid这个点属于左儿子，是左儿子的最后一个点！ 
    if (y>mid) change(2*p+1,x,y,z);
    //mid不属于右儿子，所以要写成y>mid 
    t[p].pre=t[2*p].pre+t[2*p+1].pre;
}//区间修改 
int answer(int p,int x,int y){
    if (x<=t[p].ls && y>=t[p].rs) return t[p].pre;
    //这个节点刚刚好被覆盖在这个区间内，返回这个节点的值 
    push_down(p);
    //寻找在这个节点下面符合条件的儿子节点
    int mid=(t[p].rs+t[p].ls)/2,ans=0;
    if (x<=mid) ans+=answer(2*p,x,y);
    //左区间被完全或部分包含在询问区间内，答案去左儿子寻找 
    if (y>mid) ans+=answer(2*p+1,x,y);
    //右区间被完全或部分包含在询问区间内，答案去右儿子寻找
    return ans;
    //返回答案ans 
}//区间查询 
int main(){
    scanf("%d%d",&n,&m);
    for (register int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    //对a[1]到a[n]建树 
    for (register int i=1;i<=m;i++){
        int x,y,z,t;
        scanf("%d",&t);
        if (t==1){
            //修改操作 
            scanf("%d%d%d",&x,&y,&z);
            change(1,x,y,z);
            //从根节点开始修改 
        }
        if (t==2){
            //询问操作 
            scanf("%d%d",&x,&y);
            printf("%d\n",answer(1,x,y));
            //从根节点开始向下收集答案 
        }
    }
    return 0;
}

线段树模板