线段树模板

修改点、区间求和、区间查询

#include<cstdio>
using namespace std;
const int MAXN=12345678;
int Sum[MAXN<<2],A[MAXN],n,Add[MAXN<<2];//Sum存储求和，开4倍空间；A为原数组，最多存MAXN个数；总共输入n个数；Add为懒标记
inline void PushUp(int rt){
    Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];
}//求和。父节点存储的区间和是左儿子和右儿子存储的区间和
inline void Build(int l,int r,int rt){
    if(l==r){Sum[rt]=A[l];return;}//l==r说明已经到达叶节点，叶节点存储的区间和就是自己实际在A中存储的值 
    int m=(l+r)>>1;//如果不在叶节点，对区间继续划分（一分为二）【直到划分到叶节点】 
    Build(l,m,rt<<1),Build(m+1,r,rt<<1|1);//左右递归 
    PushUp(rt);//更新当前节点存储的区间和 
}//建树（第一次初始化线段树，最先完成树的最底层【函数执行第一行】）。[l,r]表示当前节点存储区间，rt表示当前节点在A中的实际存储位置
inline void Update_1(int L,int v,int l,int r,int rt){
    if(l==r){Sum[rt]+=v;return;}
    int m=(l+r)>>1;
    if(L<=m) Update_1(L,v,l,m,rt<<1);//根据条件判断往左子树调用还是往右子树调用
    else Update_1(L,v,m+1,r,rt<<1|1);
    PushUp(rt);//子节点信息更新了，所以本节点也要更新信息 
}//点修改。A[p]+=v。l、r意义同上
inline void Update_2(int L,int R,int v,int l,int r,int rt){
    if(L<=l&&r<=R){Sum[rt]+=v*(r-l+1);Add[rt]+=v;return;}//如果本区间完全在操作区间[L,R]以内//更新数字和，向上保持正确//增加Add标记，表示本区间的Sum正确，子区间的Sum仍需要根据Add的值来调整
    int m=(l+r)>>1;
    PushDown(rt,m-l+1,r-m);//下推标记
    if(L<=m) Update(L,R,v,l,m,rt<<1);
    if(R>m) Update(L,R,v,m+1,r,rt<<1|1);//这里判断左右子树跟[L,R]有无交集，有交集才递归
    PushUp(rt);//更新本节点信息
}//区间修改
inline PushDown(int rt,int ln,int rn){
    if(Add[rt]){//下推标记
        Add[rt<<1]+=Add[rt];Add[rt<<1|1]+=Add[rt];Sum[rt<<1]+=Add[rt]*ln;Sum[rt<<1|1]+=Add[rt]*rn;Add[rt]=0;//修改子节点的Sum使之与对应的Add相对应//清除本节点标记
    }
}//ln,rn为左子树，右子树的数字数量
inline Query(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R) return Sum[rt];//在区间内直接返回 
    int m=(l+r)>>1;//左子区间：[l,m] 右子区间：[m+1,r] 求和区间：[L,R] 
    PushDown(rt,m-l+1,r-m);//下推标记，否则Sum可能不正确
    int ANS=0;//累计答案
    if(L<=m) ANS+=Query(L,R,l,m,rt<<1);//左子区间与[L,R]有重叠，递归 
    if(R>m) ANS+=Query(L,R,m+1,r,rt<<1|1);//右子区间与[L,R]有重叠，递归 
    return ANS;
}//区间查询。[L,R]表示操作区间，[l,r]表示当前区间 ，rt表示当前节点编号
int main(){
    //建树 
    Build(1,n,1); 
    //点修改
    Update(L,C,1,n,1);
    //区间修改 
    Update(L,R,C,1,n,1);
    //区间查询 
    int ANS=Query(L,R,1,n,1);
    return 0;
}

洛谷模板(线段树1)

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const long long MAXN=19260817;
long long Sum[MAXN<<2],A[MAXN],n,m,Add[MAXN<<2];//Sum存储求和，开4倍空间；A为原数组，最多存MAXN个数
void PushUp(long long rt);
void Build(long long l,long long r,long long rt);
void Update_1(long long L,long long v,long long l,long long r,long long rt);
void Update_2(long long L,long long R,long long v,long long l,long long r,long long rt);
void PushDown(long long rt,long long ln,long long rn);
long long Query(long long L,long long R,long long l,long long r,long long rt);
int main(){
    long long x,y,k,cz;
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=n;++i) scanf("%lld",&A[i]);
    Build(1,n,1);
    for(long long i=1;i<=m;++i){
        scanf("%lld%lld%lld",&cz,&x,&y);
        if(cz==1) {scanf("%lld",&k);Update_2(x,y,k,1,n,1);}
        else printf("%lld\n",Query(x,y,1,n,1));
    }
/*    //建树 
    Build(1,n,1); 
    //点修改
    Update_1(L,C,1,n,1);
    //区间修改 
    Update_2(L,R,C,1,n,1);
    //区间查询 
    long long ANS=Query(L,R,1,n,1);
*/    
    return 0;
}
void PushUp(long long rt){
    Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];
}//求和。父节点存储的区间和是左儿子和右儿子存储的区间和
void Build(long long l,long long r,long long rt){
    if(l==r){Sum[rt]=A[l];return;}//l==r说明已经到达叶节点，叶节点存储的区间和就是自己实际在A中存储的值 
    long long m=(l+r)>>1;//如果不在叶节点，对区间继续划分（一分为二）【直到划分到叶节点】 
    Build(l,m,rt<<1),Build(m+1,r,rt<<1|1);//左右递归 
    PushUp(rt);//更新当前节点存储的区间和 
}//建树（第一次初始化线段树，最先完成树的最底层【函数执行第一行】）。[l,r]表示当前节点存储区间，rt表示当前节点在A中的实际存储位置
void Update_1(long long L,long long v,long long l,long long r,long long rt){
    if(l==r){Sum[rt]+=v;return;}
    long long m=(l+r)>>1;
    if(L<=m) Update_1(L,v,l,m,rt<<1);//根据条件判断往左子树调用还是往右子树调用
    else Update_1(L,v,m+1,r,rt<<1|1);
    PushUp(rt);//子节点信息更新了，所以本节点也要更新信息 
}//点修改。A[p]+=v。l、r意义同上
void Update_2(long long L,long long R,long long v,long long l,long long r,long long rt){
    if(L<=l&&r<=R){Sum[rt]+=v*(r-l+1);Add[rt]+=v;return;}//如果本区间完全在操作区间[L,R]以内//更新数字和，向上保持正确//增加Add标记，表示本区间的Sum正确，子区间的Sum仍需要根据Add的值来调整
    long long m=(l+r)>>1;
    PushDown(rt,m-l+1,r-m);//下推标记
    if(L<=m) Update_2(L,R,v,l,m,rt<<1);
    if(R>m) Update_2(L,R,v,m+1,r,rt<<1|1);//这里判断左右子树跟[L,R]有无交集，有交集才递归
    PushUp(rt);//更新本节点信息
}//区间修改
void PushDown(long long rt,long long ln,long long rn){
    if(Add[rt]){//下推标记
        Add[rt<<1]+=Add[rt];Add[rt<<1|1]+=Add[rt];Sum[rt<<1]+=Add[rt]*ln;Sum[rt<<1|1]+=Add[rt]*rn;Add[rt]=0;//修改子节点的Sum使之与对应的Add相对应//清除本节点标记
    }
}//ln,rn为左子树，右子树的数字数量
long long Query(long long L,long long R,long long l,long long r,long long rt){
    if(L<=l&&r<=R) return Sum[rt];//在区间内直接返回 
    long long m=(l+r)>>1;//左子区间：[l,m] 右子区间：[m+1,r] 求和区间：[L,R] 
    PushDown(rt,m-l+1,r-m);//下推标记，否则Sum可能不正确
    long long ANS=0;//累计答案
    if(L<=m) ANS+=Query(L,R,l,m,rt<<1);//左子区间与[L,R]有重叠，递归 
    if(R>m) ANS+=Query(L,R,m+1,r,rt<<1|1);//右子区间与[L,R]有重叠，递归 
    return ANS;
}//区间查询。[L,R]表示操作区间，[l,r]表示当前区间 ，rt表示当前节点编号