数据结构模板

1.线段树模板

模板

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
ll a[maxn];//数组值
ll d[maxn];//线段树节点
ll tag[maxn];//标记
void build(ll s,ll t,ll p){//对[s,t]区间建立节点,p记录节点编号 
    if(s==t){//叶子节点
        d[p]=a[s];
        return;
    }
    ll mid=(s+t)>>1;
    build(s,mid,p<<1);
    build(mid+1,t,(p<<1)|1);
    d[p]=d[p<<1]+d[(p<<1)|1];//求和
}
void update(ll l,ll r,ll c,ll s,ll t,ll p){
    if(l<=s&&t<=r){//查到子区间，修改并返回
        d[p]+=c*(t-s+1);
        tag[p]+=c;//标记+c 
        return;
    }
    ll mid=(s+t)>>1;
    if(tag[p]&&s!=t){//有标记且不是叶子
        d[p<<1]+=(mid-s+1)*tag[p];
        d[(p<<1)|1]+=(t-mid)*tag[p];
        tag[p<<1]+=tag[p];
        tag[(p<<1)|1]+=tag[p];
        tag[p]=0;
    }

    if(l<=mid)update(l,r,c,s,mid,p<<1);//与左孩子有交集
    if(r>mid)update(l,r,c,mid+1,t,(p<<1)|1);//与右孩子有交集
    d[p]=d[p<<1]+d[(p<<1)|1];
}
ll get(ll l,ll r,ll s,ll t,ll p){//查询[l,r] 若[s,t]为当前节点包含区间，p为节点编号
    if(l<=s&&t<=r)//查到子区间，返回
        return d[p];
    ll mid=(s+t)>>1,sum=0;

    if(tag[p]&&s!=t){//有标记且不是叶子
        d[p<<1]+=(mid-s+1)*tag[p];
        d[(p<<1)|1]+=(t-mid)*tag[p];
        tag[p<<1]+=tag[p];
        tag[(p<<1)|1]+=tag[p];
        tag[p]=0;
    }

    if(l<=mid)sum+=get(l,r,s,mid,p<<1);//与左孩子有交集
    if(r>mid)sum+=get(l,r,mid+1,t,(p<<1)|1);//与右孩子有交集
    return sum;
}
void solve(){
    ll n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    build(1,n,1);
    while(m--){
        int a;
        cin>>a;
        if(a==1){
            int x,y,k;
            cin>>x>>y>>k;
            update(x,y,k,1,n,1);
        }
        else{
            int x,y;
            cin>>x>>y;
            cout<<get(x,y,1,n,1)<<'\n';
        }

    }
}