//求sum{[0..n-1]}
//維護(hù)和查詢復(fù)雜度均為O(logn)
//用于動(dòng)態(tài)求子段和,數(shù)組內(nèi)容保存在sum.a[]中
//可以改成其他數(shù)據(jù)類型
#include <string.h>
#define lowbit(x) ((x)&((x)^((x)-1)))
#define MAXN 10000
typedef int elem_t;

struct sum{
	elem_t a[MAXN],c[MAXN],ret;
	int n;
	void init(int i){memset(a,0,sizeof(a));memset(c,0,sizeof(c));n=i;}
	void update(int i,elem_t v){for (v-=a[i],a[i++]+=v;i<=n;c[i-1]+=v,i+=lowbit(i));}
	elem_t query(int i){for (ret=0;i;ret+=c[i-1],i^=lowbit(i));return ret;}
};