数据结构：树状数组模板

点击查看折叠代码块

int lowbit(int x){
	return x & -x;
}

void update(int x,int v){
	while(x<=n){
		c[x]+=v;
		x+=lowbit(x);
	}
}

int query(int x){
	int ret=0;
	while(x){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}