세그먼트 트리 전체 템플릿
6023 단어 [ACM의 길 Bryce 템플릿]
템플릿
#include
#include
#include
using namespace std;
#define MAXN 200010
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
int sum[MAXN<<2];
void pushUp(int p)
{
sum[p]=max(sum[p<<1],sum[p<<1|1]);
}
void build(int l,int r,int p)
{
if(l==r){
scanf("%d",&sum[p]);
return ;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
pushUp(p);
}
int query(int l,int r,int p,int a,int b)
{
if(l>=a&&b>=r) //
return sum[p];
int ans=0;
int mid=(l+r)>>1;
if(mid>=a)
ans=max(ans,query(lson,a,b)); //
if(mid
//
sum[p]=b; return ; } int mid=(l+r)>>1; if(a<=mid) update(lson,a,b); else update(rson,a,b); pushUp(p);}int main(){ int n,m; char ch[5];//freopen("in.txt","r",stdin); while(~scanf("%d%d",&n,&m)) { int a,b; build(1,n,1); while(m--) { scanf("%s%d%d",ch,&a,&b); if(ch[0]=='Q') printf("%d",query(1,n,1,a,b)); else update(1,n,1,a,b); } } return 0;} 二、区间查询,无单点更新
#include
#include #include #include using namespace std; const int maxn=200010; int sum[maxn<<2];// int h,w,n; //p void pushUp(int p) { //p , sum[p]=max(sum[p<<1],sum[p<<1|1]); } // void build(int l,int r,int p) { if(l==r)// 0 { sum[p]=w; return ; } // , int mid=(r+l)>>1; build(l,mid,p<<1); build(mid+1,r,p<<1|1); pushUp(p); } // // int query(int l,int r,int p,int num) { if(l==r)// { sum[p]-=num;// return l; } int ans; int mid=(r+l)>>1;// , ans, if(sum[p<<1]>=num) { ans=query(l,mid,p<<1,num); } else { ans=query(mid+1,r,p<<1|1,num); } pushUp(p); return ans; } int main() { while(scanf("%d%d%d",&h,&w,&n)!=EOF) { memset(sum,0,sizeof(sum)); if(h>n)h=n; int temp; build(1,h,1);// [1,h], 1 for(int i=0;i
3. 단일 업데이트 + 구간 구화#include
#include #include using namespace std; #define MAXN 50010 #define lson l,mid,p<<1 #define rson mid+1,r,p<<1|1 #define mem(a) memset(a,0,sizeof(a[0])) int sum[MAXN<<2]; void pushUp(int p) { sum[p]=sum[p<<1]+sum[p<<1|1]; } void build(int l,int r,int p) { if(l==r){ scanf("%d",&sum[p]); return; } int mid=(l+r)>>1; build(lson); build(rson); pushUp(p); } int query(int l,int r,int p,int i,int j) { if(l>=i&&r<=j){ return sum[p]; } int ans=0; int mid=(l+r)>>1; if(mid =i) ans+=query(lson,i,j); return ans; } void update(int l,int r,int p,int i,int j) { if(l==r){ sum[p]+=j; return ; } int mid=(l+r)>>1; if(mid>=i) update(lson,i,j); else update(rson,i,j); pushUp(p); } int main() { int n,T; int cases=1; char str[10]; //freopen("in.txt","r",stdin); scanf("%d",&T); while(T--) { mem(sum); scanf("%d",&n); printf("Case %d:
",cases++); int i,j; build(1,n,1); while(scanf("%s",str)&&strcmp(str,"End")) { scanf("%d%d",&i,&j); if(strcmp(str,"Query")==0) printf("%d
",query(1,n,1,i,j)); else if(strcmp(str,"Add")==0) update(1,n,1,i,j); else if(strcmp(str,"Sub")==0) update(1,n,1,i,-j); } } return 0; }
4. 구간 조회 최고치 + 단일 업데이트#include
#include #include using namespace std; #define MAXN 200010 #define lson l,mid,p<<1 #define rson mid+1,r,p<<1|1 int sum[MAXN<<2]; void pushUp(int p) { sum[p]=max(sum[p<<1],sum[p<<1|1]); } void build(int l,int r,int p) { if(l==r){ scanf("%d",&sum[p]); return ; } int mid=(l+r)>>1; build(lson); build(rson); pushUp(p); } int query(int l,int r,int p,int a,int b) { if(l>=a&&b>=r) return sum[p]; int ans=0; int mid=(l+r)>>1; if(mid>=a) ans=max(ans,query(lson,a,b)); if(mid>1; if(a<=mid) update(lson,a,b); else update(rson,a,b); pushUp(p); } int main() { int n,m; char ch[5]; //freopen("in.txt","r",stdin); while(~scanf("%d%d",&n,&m)) { int a,b; build(1,n,1); while(m--) { scanf("%s%d%d",ch,&a,&b); if(ch[0]=='Q') printf("%d
",query(1,n,1,a,b)); else update(1,n,1,a,b); } } return 0; }