HDU 1166 황소가 쓴 세그먼트 트리 모방

1733 단어 querybufferBuild
누드 문제 단점 업데이트: 가장 기초적인 라인 트리로 잎 노드만 업데이트한 다음PushUP (int r) 함수로 정보를 업데이트합니다
HDU 1166
매우 아름답다.
코드를 올린 후에 많이 기억해라
#include<stdio.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 55555
char buffer[10];
int sum[maxn<<2];
int PushUp(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int build(int l,int r,int rt)
{
    if(l==r) {scanf("%d",&sum[rt]);return 0;}
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    PushUp(rt);
}
int updata(int p,int k,int l,int r,int rt)
{
    int m;
    if(l==r) {sum[rt]+=k;return 0;}
    m=(l+r)>>1;
    if(p<=m) updata(p,k,lson);
    else updata(p,k,rson);
    PushUp(rt);
}
int query(int L,int R,int l,int r,int rt)
{
    int temp=0,m;
    if(L<=l&&r<=R) return sum[rt];
    m=(l+r)>>1;
    if(L<=m) temp=temp+query(L,R,lson);
    if(R>m) temp=temp+query(L,R,rson);
    return temp;
}
int main()
{
    freopen("hdu1166.in","r",stdin);
    freopen("hdu1166.out","w",stdout);
    int T,i,N,a,b;
    scanf("%d",&T);
    for(i=1;i<=T;i++)
        {
            scanf("%d",&N);
            build(1,N,1);
            printf("Case %d:
",i); while(scanf("%s",buffer)) { if(buffer[0]=='E') break; scanf("%d%d",&a,&b); if(buffer[0]=='A') updata(a,b,1,N,1); else if(buffer[0]=='S') updata(a,-b,1,N,1); else if(buffer[0]=='Q') printf("%d
",query(a,b,1,N,1)); } } }

좋은 웹페이지 즐겨찾기