【数据结构】线段树的几种用法

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 100007
#define ll long long
ll sum[maxn<<2],add[maxn<<2],a[maxn],n,m;
void build(ll l,ll r,ll k)//建树 [l,r]中 编号为k的区间 
{
    if(l==r)//叶子节点 
    {
        sum[k]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(l,mid,k<<1);//左子树 
    build(mid+1,r,k<<1|1);//右子树 
    sum[k]=sum[k<<1]+sum[k<<1|1];//更新区间和 
}
void Add(ll l,ll r,ll v,ll k)//给定区间[l,r]中所有的数加上v 
{
    add[k]+=v;//打标记 
    sum[k]+=(r-l+1)*v;//维护对应区间和 
    return;
}
void pushdown(ll l,ll r,ll mid,ll k)//标记下传 
{
    if(add[k]==0) return;//如果没有标记 就退出 
    Add(l,mid,add[k],k<<1);//传给左子树 
    Add(mid+1,r,add[k],k<<1|1);//传给右子树 
    add[k]=0;//传完之后清楚标记 
}
void update(ll x,ll y,ll v,ll l,ll r,ll k)//更新定区间[x,y]中 区间[l,r]第k个区间 
{
    if(l>=x&&r<=y) return Add(l,r,v,k);//当这个定区间包含区间[l,r] 则更新区间[l,r]的值 
    ll mid=(l+r)>>1;
    pushdown(l,r,mid,k);//标记下传 
    if(x<=mid) update(x,y,v,l,mid,k<<1);//更新左子树 
    if(mid<y) update(x,y,v,mid+1,r,k<<1|1);//更新右子树 
    sum[k]=sum[k<<1]+sum[k<<1|1];//更新下传后当前正确的sum值 
}
ll query(ll x,ll y,ll l,ll r,ll k)//查询定区间[x,y]中 区间[l,r]第k个区间 
{   
    if(l>=x&&r<=y) return sum[k];//当这个定区间包含区间[l,r] 返回区间[l,r]的值 
    ll mid=(l+r)>>1;
    ll res=0;
    pushdown(l,r,mid,k);//标记下传 
    if(x<=mid) res+=query(x,y,l,mid,k<<1);//如果左子树还有值 就加上左子树 
    if(y>mid) res+=query(x,y,mid+1,r,k<<1|1);//同上右子树 
    return res;//返回值 
}
int main()
{
    cin>>n>>m;
    for(ll i=1;i<=n;i++) cin>>a[i];
    build(1,n,1);//建原树 
    for(ll i=1;i<=m;i++)
    {
        ll x,y,z;
        cin>>x;
        if(x==1)
        {
            cin>>x>>y>>z;
            update(x,y,z,1,n,1);//更新值 
        }
        else
        {   
            cin>>x>>y;
            cout<<query(x,y,1,n,1)<<endl;//查询区间 
        }
    }
}