树状数组

树状数组能处理的是下标为1~n的数组

考虑使用的情况：求前缀和、修改区间中的某个数，时间复杂度均为logn

基本思想

将x分解为二进制x = 2ⁱ¹ + 2ⁱ²+…+2^im (i1 > … > im)

则可以将[1,x]的区间划分为[1, 2ⁱ¹],[2ⁱ¹+1,2ⁱ¹+2ⁱ²],[2ⁱ¹+2ⁱ²+1, 2ⁱ¹+2ⁱ²+2ⁱ³] …,[2ⁱ¹+2ⁱ²+…+2^im-1 +1,2ⁱ¹+2ⁱ²+…+2^im ]这些区间

c[x]保存序列a区间[x-lowbit(x) + 1, x]中所有数的和

C[i] = A[i - 2^k+1] + A[i - 2^k+2] + … + A[i]; //k为i的二进制中从最低位到高位连续零的长度

该结构满足以下性质：

（1）每个内部节点c[x]保存以他为根的子树中所有叶节点的和

（2）每个内部节点c[x]的子节点数等于lowbit(x)的大小

（3）除数根外，每个内部节点c[x]的父节点是c[x+lowbit(x)]

（4）树的深度为O(logN)

int lowbit(int x){
	return x& -x;
} //求x二进制下的最小的2次幂

void add(int x, int c) {
	for (int i = x; i <= n; i += lowbit(i)) t[i] += c;
}//a[x] += c

void ask(int x) {
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i)) ans += t[i];
    return ans;
} //[1,x]的和

//初始化
for (int i = 1; i <= n; i++) add(i, a[i]);

1.区间加减数，查询单点，可先差分再树状数组

2.区间加减数，查询区间，树状数组维护差分数组b[i]及i*b[i]，[1,x]的前缀和课用ask1(x) * (x + 1) - ask2(x)得出

3.找到区间[l,r]还存在的第k小的数，删除区间[1,x]中的某个数，可使原数组a[i] = 1，树状数组维护a[i]，删除x点的数使用add(x, -1)，查询[l,r]第k小的数利用ask(mid) - ask(l) >= k二分