线段树模板新

直接先上代码，然后来个例题

#include<bits/stdc++.h>
using namespace std;
void pushup(int rt)
{
    //父节点的信息由左子节点2*rt 和右子节点2*rt+1转移得来 
};
int  init(int n)
{
    int n_=1;
    while(n_<n)
    n_*=2;
    return n_;
}
void build(int l,int r,int rt)
{
    if (l==r-1)
    {
        //更新当前长度为1的区间 
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid,r,rt<<1|1);
    pushup(rt);
}
void pushdown(int rt)
{
    if (lazy[rt])
    {
        //同时更新左右节点的标记以及要维护的信息 
    }
}
void update(int L,int R,int l,int r,int rt)
{
    if (L<=l&&r<=R)
    {
        //当前终止 
        return;
    }
    int mid=(l+r)>>1;
    pushdown(rt);
    if (L<mid) update(L,R,C,l,mid,rt<<1);
    if (R>mid) update(L,R,C,mid,r,rt<<1|1);
    pushup(rt);
}//更新pushup pushdown都需要 
void update(int v,int rt)//rt为数组中位置+n-1 
{
    //rt当前改值
    while(rt>1)
    {
        rt/=2;
        //修改rt维护的值 
        }    
}//单点修改 
int query(int L,int R,int l,int r,int rt)
{
    if (L<=l&&r<=R)
        {//返回当前区间维护的答案 
        return;}
    int mid=(l+r)>>1;
    pushdown(rt);//若更新只有点更新，不需要这句
    int ans=0
    if (L<mid) ans+=query(L,R,l,mid,rt<<1);
    if (R>mid) ans+=query(L,R,mid,r,rt<<1|1);
    return ans;
}//查询只需要pushdown
//建树得把n变成2的幂

洛谷P3372

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=1<<30;
const int maxn=1e5+7;
const double pi=acos(-1);
const int mod=100;
#define meminf(a) memset(a,0x3f,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define ls rt<<1
#define rs rt<<1|1
#define mid (l+r)>>1
ll dat[maxn<<2],lazy[maxn<<2],a[maxn<<2];
void pushup(int rt){
    dat[rt]=dat[ls]+dat[rs];
}

void pushdown(int rt,int l,int r){
    if(lazy[rt]!=0){
        lazy[ls]+=lazy[rt];
        lazy[rs]+=lazy[rt];
        dat[ls]+=lazy[rt]*(r-l)/2;
        dat[rs]+=lazy[rt]*(r-l)/2;
        lazy[rt]=0;
    }
}

void build(int l,int r,int rt){
    if(l==r-1){
        dat[rt]=a[l];
        return;
    }
    build(l,mid,ls);
    build(mid,r,rs);
    pushup(rt);
}

void update(int l,int r,int s,int t,int rt,ll c){
    if(s<=l&&r<=t){
        dat[rt]+=c*(r-l);
        lazy[rt]+=c;
        return;//这里是关键 
    }
    pushdown(rt,l,r);//递归到子节点前先标记下传 
    if(s<mid) update(l,mid,s,t,ls,c);
    if(t>mid) update(mid,r,s,t,rs,c);
    pushup(rt);
}
ll query(int l,int r,int s,int t,int rt){
    ll ans=0;
    if(s<=l&&r<=t){
        return dat[rt];
    }
    pushdown(rt,l,r);
    if(s<mid) ans+=query(l,mid,s,t,ls);
    if(t>mid) ans+=query(mid,r,s,t,rs);
    return ans;
}
int main(){
      int n_,m;scanf("%d%d",&n_,&m);
      int n=1;
      for(int i=1;i<=n_;i++)scanf("%lld",&a[i]);
      while(n<n_)n<<=1;
      build(1,n+1,1);
      for(int i=1;i<=m;i++){
          int opt,x,y;ll k;
          scanf("%d%d%d",&opt,&x,&y);
          if(opt==1){
              scanf("%lld",&k);
              update(1,n+1,x,y+1,1,k);
              //cout<<233<<endl;
          }
        else if(opt==2){
            printf("%lld
",query(1,n+1,x,y+1,1));
        }  
      }
    return 0;
}