HDU 1166 敵兵布陣 樹狀數組||線段樹

題目大意：

給定n個數的區間N<=50000，還有Q個詢問（Q<=40000）求區間和。

每個詢問可能增加點k x的值或者減少x。

思路：

原題描述很有愛啊~

樹狀數組好久沒寫了~

依舊很熟練，WA了兩三次，第一次因為沒有輸出case，。。。。。。。第二次發現多組數據沒有初始化。T^T

~像這種單點修改求區間和的還是用樹狀數組比較簡單~

樹狀數組：

#include
#include
const int MAXN=50000+10;
int sum[MAXN];
inline int lowbit(int x)
{
	return x&-x;
}

int getsum(int x)
{
	int ans=0;
	while(x>0)
	{
		ans+=sum[x];
		x-=lowbit(x);
	}
	return ans;
}

void add(int x,int v)
{
	while(x
線段樹：
 
#include
#include
const int MAXN=50000+10;
int sum[MAXN<<2],a[MAXN];
void build(int k,int L,int R)  
{  
    if(L==R)  sum[k]=a[L];  
    else  
    {  
        int m=(L+R)/2;  
        build(k*2,L,m);  
        build(k*2+1,m+1,R);  
        sum[k]= sum[k*2]+sum[k*2+1];
    }  
}  

int getsum(int k,int L,int R,int a,int b) 
{  
    int m=(L+R)/2,ans=0;  
    if(a<=L && R<=b) return sum[k];  
    if(a<=m) ans+=getsum(k*2,L,m,a,b);  
    if(m