セグメントツリーまとめ(単点更新、区間更新、区間和、区間最値)
注意:各機能はコードに注釈があり、具体的な詳細は自分でテストを出力できます.
1:区間更新と区間加算
2:区間更新と区間最小値を求める
注意:最大値と最小値の関数はテストしても実行可能性があり、自分でテストすることができます.
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;
}