セグメントツリーまとめ(単点更新、区間更新、区間和、区間最値)

注意:各機能はコードに注釈があり、具体的な詳細は自分でテストを出力できます.
1:区間更新と区間加算

#include
#include
#include
using namespace std;
#define N 400010
#define LL long long
LL sum[N],lazy[N];
/// 
void pushUp(int root){
    sum[root]=sum[root<<1] + sum[(root<<1)+1];
}
/// 
void pushDown(int root,int len){
    lazy[root<<1]+=lazy[root];
    lazy[(root<<1)+1]+=lazy[root];
    sum[root<<1]+=(len-(len>>1))*lazy[root];
    sum[(root<<1)+1]+=(len>>1)*lazy[root];
    lazy[root]=0;
}
/// 
void build(int l,int r,int root){
    lazy[root]=0;
    if(l==r){
        scanf("%I64d",&sum[root]);
        return;
    }
    int m = (l+r)>>1;
    build(l,m,root<<1);
    build(m+1,r,(root<<1)+1);
    pushUp(root);
}
/// （l,r） ， root， （L,R）  +c
void update(int L,int R,long long c,int l,int r,int root){
   if(L<=l&&R>=r){
        lazy[root]+=c;
        sum[root]+=c*(r-l+1);
        return;
    }
    if(lazy[root]) pushDown(root,r-l+1);
    int m = (l+r)>>1;
    if(L<=m) update(L,R,c,l,m,root<<1);
    if(R>m) update(L,R,c,m+1,r,(root<<1)+1);
    pushUp(root);
}
/// （l,r） ， root， （L,R） 
LL query(int L,int R,int l,int r,int root){
    if(L<=l&&R>=r) return sum[root];
    if(lazy[root]){
        pushDown(root,r-l+1);
    }
    int m=(l+r)>>1;
    LL ans=0;
    if(L<=m) ans+=query(L,R,l,m,root<<1);
    if(R>m) ans+=query(L,R,m+1,r,(root<<1)+1);
    return ans;
}
int main(){
    int n,q,a,b;
    long long c;
    char ch;
    scanf("%d%d",&n,&q);
        build(1,n,1);
        while(q--){
            getchar();
            scanf("%c",&ch);
            if(ch=='Q'){
                scanf("%d%d",&a,&b);
                printf("%I64d
",query(a,b,1,n,1));
            }else{
                scanf("%d%d%I64d",&a,&b,&c);
                update(a,b,c,1,n,1);
            }

        }
    return 0;
}

2:区間更新と区間最小値を求める
注意:最大値と最小値の関数はテストしても実行可能性があり、自分でテストすることができます.

#include
#include
#include
#include
#include
#include
using namespace std;
#define N 4000001
#define INF 0x3f3f3f3f
int Min[N];
int Max[N];
int lazy[N];
bool vis[N];
/// 
void PushUp(int root){
    Min[root]=min(Min[root<<1],Min[(root<<1)+1]);
    Max[root]=max(Max[root<<1],Max[(root<<1)+1]);
}
/// 
void PushDown(int root,int c){
    Min[root<<1]=Min[(root<<1)+1]=lazy[root];
    Max[root<<1]=Max[(root<<1)+1]=lazy[root];
    vis[root<<1]=vis[(root<<1)+1]=true;
    lazy[root<<1]=lazy[(root<<1)+1]=lazy[root];
    vis[root]=false;
}
/// ， root， （l,r）
void build(int l,int r,int root){
    if(l==r){
        scanf("%d",&Min[root]);
        Max[root]=Min[root];
        return;
    }
    int m = (l+r)>>1;
    build(l,m,root<<1);
    build(m+1,r,(root<<1)+1);
    PushUp(root);
}
/// （l,r） ， root， （L,R） 
int getMin(int L,int R,int l,int r,int root){
  //  if(vis[root]) return Min[root];
    if(L<=l&&R>=r) return Min[root];
    if(vis[root]) PushDown(root,lazy[root]);
    int m = (l+r)>>1,ret=INF;
    if(L<=m) ret = min(ret,getMin(L,R,l,m,root<<1));
    if(R>m) ret = min(ret,getMin(L,R,m+1,r,(root<<1)+1));
    return ret;
}
/// （l,r） ， root， （L,R） 
int getMax(int L,int R,int l,int r,int root){
    //if(vis[root]) return Max[root];
    if(L<=l&&R>=r) return Max[root];
    if(vis[root]) PushDown(root,lazy[root]);
    int m = (l+r)>>1,ret=0;
    if(L<=m) ret = max(ret,getMax(L,R,l,m,root<<1));
    if(R>m) ret = max(ret,getMax(L,R,m+1,r,(root<<1)+1));
    return ret;
}
/// （l,r） ， root， （L,R）  c
void update(int L,int R,int c,int l,int r,int root){
    if(L<=l&&R>=r){
        Min[root]=Max[root]=c;
        lazy[root]=c;
        vis[root]=true;
        return ;
    }
    if(vis[root]) PushDown(root,c);
    int m = (l+r)>>1;
    if(L<=m) update(L,R,c,l,m,root<<1);
    if(R>m) update(L,R,c,m+1,r,(root<<1)+1);
    PushUp(root);
}
int main(){
    int n,m,a,b,c,t;
    while(scanf("%d",&n)!=EOF){
        memset(vis,false,sizeof(vis));
        build(1,n,1);
        scanf("%d
",&m);
        while(m--){
            scanf("%d",&t);
            if(t==0){
                scanf("%d%d%d",&a,&b,&c);
                update(a,b,c,1,n,1);
            }else{
                scanf("%d%d",&a,&b);
                printf("%d
",getMin(a,b,1,n,1));
            }
        }
    }
    return 0;
}

#include
#include
#include
#include
#include
#include
using namespace std;
#define N 4000001
#define INF 0x3f3f3f3f
int Min[N];
int Max[N];
int lazy[N];
bool vis[N];
/// 
void PushUp(int root){
    Min[root]=min(Min[root<<1],Min[(root<<1)+1]);
    Max[root]=max(Max[root<<1],Max[(root<<1)+1]);
}
/// 
void PushDown(int root,int c){
    Min[root<<1]=Min[(root<<1)+1]=lazy[root];
    Max[root<<1]=Max[(root<<1)+1]=lazy[root];
    vis[root<<1]=vis[(root<<1)+1]=true;
    lazy[root<<1]=lazy[(root<<1)+1]=lazy[root];
    vis[root]=false;
}
/// ， root， （l,r）
void build(int l,int r,int root){
    if(l==r){
        scanf("%d",&Min[root]);
        Max[root]=Min[root];
        return;
    }
    int m = (l+r)>>1;
    build(l,m,root<<1);
    build(m+1,r,(root<<1)+1);
    PushUp(root);
}
/// （l,r） ， root， （L,R） 
int getMin(int L,int R,int l,int r,int root){
  //  if(vis[root]) return Min[root];
    if(L<=l&&R>=r) return Min[root];
    if(vis[root]) PushDown(root,lazy[root]);
    int m = (l+r)>>1,ret=INF;
    if(L<=m) ret = min(ret,getMin(L,R,l,m,root<<1));
    if(R>m) ret = min(ret,getMin(L,R,m+1,r,(root<<1)+1));
    return ret;
}
/// （l,r） ， root， （L,R） 
int getMax(int L,int R,int l,int r,int root){
    //if(vis[root]) return Max[root];
    if(L<=l&&R>=r) return Max[root];
    if(vis[root]) PushDown(root,lazy[root]);
    int m = (l+r)>>1,ret=0;
    if(L<=m) ret = max(ret,getMax(L,R,l,m,root<<1));
    if(R>m) ret = max(ret,getMax(L,R,m+1,r,(root<<1)+1));
    return ret;
}
/// （l,r） ， root， （L,R）  c
void update(int L,int R,int c,int l,int r,int root){
    if(L<=l&&R>=r){
        Min[root]=Max[root]=c;
        lazy[root]=c;
        vis[root]=true;
        return ;
    }
    if(vis[root]) PushDown(root,c);
    int m = (l+r)>>1;
    if(L<=m) update(L,R,c,l,m,root<<1);
    if(R>m) update(L,R,c,m+1,r,(root<<1)+1);
    PushUp(root);
}
int main(){
    int n,m,a,b,t;
    char c;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(vis,false,sizeof(vis));
        build(1,n,1);
        while(m--){
            getchar();
            scanf("%c%d%d",&c,&a,&b);
            if(c=='U'){
                update(a,a,b,1,n,1);
            }else{
                printf("%d
",getMax(a,b,1,n,1));
            }
        }
    }
    return 0;
}