树状数组

树状数组用来解决单点修改和区间查询时，代码实现比线段树简单。
在树状数组t中，t[x]，x表示t[x]覆盖的长度。

lowbit操作

可以知道数值x的二进制最低位的1及后面的0表示的数字

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

单点修改

下标x每次加lowbit(x)即可找到其父亲节点。

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

区间查询

下标x每次减lowbit(x)即可得到前面覆盖一层的节点下标。

//前缀和
int getsum(int x) {  // a[1]..a[x]的和
  int ans = 0;
  while (x >= 1) {
    ans = ans + c[x];
    x = x - lowbit(x);
  }
  return ans;
}