浅谈树状数组

和线段树一样,树状数组也是处理区间操作的利器，可以处理的区间问题有：

区间查询 单点查询 单点更新

原理就不详细说了 （当板子用吧）
实现:

函数部分

#define lowbit(i) (i&-i) //也可以 int lowbit(i){return i&-i;}

const int maxn = 10010;//数据范围
int t[maxn],a[maxn];

void init() //a[] 是 原来的数组 
{
  for (int i = 1; i <= n; ++i) 
  {
    t[i] += a[i];
    int j = i + lowbit(i);
    if (j <= n) t[j] += t[i];
  }
}

void add(int x,int num)
{
	for(;x<=n;x+=x&-x)
		t[x]+=num;
} 
int sum(int x)
{
	int ans =0;
	for(;x>0;x-=x&-x)
		ans += t[x];
	return ans;
}