hdu1166 樹狀數組

 
不知道為什麼用C++輸入輸出死活不過，換成C的就過了。。。 
#include <stdio.h>  
#include <string.h>  
 
//==============================  
#define maxn 50020  
 
int c[maxn]; 
int a[maxn]; 
int n; 
int t; 
 
int lowbit(int x) 
{ 
    return x&(-x); 
} 
 
int Sum(int n) 
{ 
    int sum = 0; 
    while(n>0) 
    { 
        sum += c[n]; 
        n = n - lowbit(n); 
    } 
    return sum; 
} 
 
void update(int i,int x) 
{ 
    while(i <= n) 
    { 
        c[i] = c[i] + x; 
        i = i + lowbit(i); 
    } 
} 
 
int GetSum(int x1,int x2) 
{ 
    return Sum(x2) - Sum(x1-1); 
} 
 
//===================================  
int main() 
{ 
    scanf("%d",&t); 
    int count = 0; 
    while(t--) 
    { 
        count++; 
        memset(a,0,sizeof(a)); 
        memset(c,0,sizeof(c)); 
        scanf("%d",&n); 
        for(int i = 1; i <= n; i++) 
        { 
            scanf("%d",&a[i]); 
            update(i,a[i]); 
        } 
        //cout<<"case "<<count<<":"<<endl;  
        printf("Case %d:\n",count); 
        char oper[11]; 
        int i,j; 
        while(scanf("%s",oper)==1) 
        { 
            if(strcmp(oper,"End")==0) 
                break; 
            scanf("%d%d",&i,&j); 
            if(strcmp(oper,"Query")==0) 
            { 
                printf("%d\n",GetSum(i,j)); 
            } 
            if(strcmp(oper,"Add")==0) 
            { 
                a[i] += j; 
                update(i,j); 
            } 
            if(strcmp(oper,"Sub")==0) 
            { 
                a[i] -= j; 
                update(i,-j); 
            } 
        } 
    } 
    return 0; 
}