树状数组模板

int lowbit(int x) {return x&(-x);} int sum(int i)//求前i项和 { int s=0; while(i>0) { s+=bit[i]; i-=lowbit(i); } return s; } void add(int i,int val) { while(i<=n) { bit[i]+=val; i+=lowbit(i); } }