세그먼트 트리 전체 템플릿

꼭 해야 할 라인 트리 연습문제 총집합
템플릿

#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;
}