子段和.txt

normal template for acm/ICPC

//求sum{[0..n-1]}
//维护和查询复杂度均为O(logn)
//用于动态求子段和,数组内容保存在sum.a[]中
//可以改成其他数据类型
#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;}
};