树状数组

概念

树状数组，简单来说就是一个很奇怪的树

eg. (原图引自 OI Wiki)

这棵树的每个点都管辖着一段区间的和，具体地：

$tr[x]$ 的管辖区间为 $[x - k + 1 , x]$，其中 $k$ 为 $x$ 转为二进制后最低位的 1 所在的二进制位数

eg：$tr[10]$: 将 $10$ 转化为二进制后为 $1010$，所以 $k = (10)_2 = 2$ , 所以其管辖区间为 $[9 ， 10]$，即为 $a_9 + a_{10}$ 的和

这棵树有一个很重要的性质：若 $y$ 为 $x$ 的父亲节点，当且仅当 $x$ 的管辖区间是 $y$ 的子集

能干啥

树状数组也可以理解为加强版前缀和或差分数组，即可以随时的查询或修改，其最为核心的能力就是单点加区间查或区间加单点查

树状数组还可以结合二分或离线来实现更为强大的功能，eg.

1. 在数列中插入，查询或删除元素
2. 在数列中维护大于或小于某个元素的个数，结合标记数组实现
3. 查询区间内元素的性质

lowbit

lowbit 函数为 $x$ 转为二进制后最低位的 1 所在的二进制位数，即上文中的 $k$，根据位运算知识：

$$lowbit(x) = x \& (-x)$$

lowbit 函数有如下性质($fa_x$ 为 $x$ 父亲)：

$$fa_x = x + lowbit(x) \text{ if } x \neq 2^k$$ $$fa_x = 2x \text{ if } x = 2^k$$

修改（modify）

易知，要修改 $x$ 的值，必然要修改所有的包含 $x$ 的 $tr[i]$ 的值，因为在树状数组中，经过推导可以得出（推导过程详见 OI Wiki）：所有的包含 $x$ 的 $tr[i]$ 有且仅有为 $x$ 的父亲节点，所以可以枚举 $x$ 和 $x$ 的父亲节点，更新这些节点即可

时间复杂度：$O(\log n)$

代码：

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

查询（query）

查询的过程与修改的过程是相反的

要查询 $query(x)$ 的值，分为两种情况

1. $x = 2^k$ 这时直接返回 $tr[x]$ 即可
2. $x \neq 2^k$ 这时需要将 $x$ 分为不重合的子区间，使的每一段的长度都为 $2^k$ ，所以可以将 $x$ 转化为二进制，累加每一位的树状数组值即可

时间复杂度：$O(\log n)$

代码：

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