以下模板都是点更新,区间查询,如果是区间更新点查询,只需将利用lowbit的循环方向倒过来
一维:
inline int lowbit(int x){return x & -x;}void add(int x, int val){for(int i = x; i <= n; i += lowbit(i)) C[i] += val;}int sum(int x){int ret = 0;for(int i = x; i > 0; i -= lowbit(i)) ret += C[i];return ret;}
二维:
inline int lowbit(int x){return x & -x;}void add(int x, int y, int val){for(int i = x; i <= n; i+=lowbit(i)) {for(int j = y; j <= n; j+=lowbit(j)) {C[i][j] += val;}}}int sum(int x, int y){int ret = 0;for(int i = x; i > 0; i-=lowbit(i)) {for(int j = y; j > 0; j-=lowbit(j)) {ret += C[i][j];}}return ret;}
,一个人的心胸宽阔,可以容不能容的事,可以赢难以赢的人。