【学习可以网上搜索ZKW统计的力量】

【HDU 1166 敌兵布阵】

#include <bits/stdc++.h>
using namespace std;
const int maxn=500010;
int T[maxn*4];
int M;
void pushup(int rt)
{
    T[rt]=T[rt*2]+T[rt*2+1];
}
void Build(int n)
{
    for(M=1; M<=n+1; M<<=1);
    for(int i=M+1; i<=M+n; i++) scanf("%d",&T[i]);
    for(int i=M-1; i>0; i--) pushup(i);
}
void Add(int n,int v)
{
    for(T[n+=M]+=v,n>>=1; n; n>>=1)
        pushup(n);
}

int Query(int s,int t)
{
    int ans=0;
    for(s=s+M-1,t=t+M+1; s^t^1; s>>=1,t>>=1)
    {
        if(~s&1) ans+=T[s^1];
        if(t&1)  ans+=T[t^1];
    }
    return ans;
}
int main()
{
    char str[15];
    int n,t,a,b,k=1;
    scanf("%d",&t);
    while(t--)
    {
        printf("Case %d:\n",k++);
        memset(T,0,sizeof(T));
        scanf("%d",&n);
        Build(n);
        while(1)
        {
            scanf("%s",str);
            if(str[0]=='E') break;
            scanf("%d%d",&a,&b);
            if(str[0]=='A')      Add(a,b);
            else if(str[0]=='S') Add(a,-b);
            else                 printf("%d\n",Query(a,b));
        }
    }
    return 0;
}

【HDU.1754 I hate it】 
    #include <iostream>  
    #include <string.h>  
    #include <stdio.h>  
      
    using namespace std;  
    const int N=200005;  
      
    int M;  
    int T[4*N];  
      
    void PushUP(int rt)  
    {  
        T[rt]=max(T[rt<<1],T[rt<<1|1]);  
    }  
      
    void Build(int n)  
    {  
        for(M=1; M<=n+1; M<<=1);  
        for(int i=M+1; i<=M+n; i++)  
            scanf("%d",&T[i]);  
        for(int i=M-1; i>0; i--)  
            PushUP(i);  
    }  
      
    void Update(int n,int v)  
    {  
        for(T[n+=M]=v,n>>=1; n; n>>=1)  
            PushUP(n);  
    }  
      
    int Query(int s,int t)  
    {  
        int ans=-1;  
        for(s=s+M-1,t=t+M+1; s^t^1; s>>=1,t>>=1)  
        {  
            if(~s&1) ans=max(ans,T[s^1]);  
            if(t&1)  ans=max(ans,T[t^1]);  
        }  
        return ans;  
    }  
      
    int main()  
    {  
        char str[15];  
        int n,m,a,b;  
        while(~scanf("%d%d",&n,&m))  
        {  
            memset(T,0,sizeof(T));  
            Build(n);  
            while(m--)  
            {  
                scanf("%s%d%d",str,&a,&b);  
                if(str[0]=='U') Update(a,b);  
                else            printf("%d\n",Query(a,b));  
            }  
        }  
        return 0;  
    }