理解树状数组

标准代码模板#

int s[N];
inline int lb(x)
{
	return x&-x;
}
void add(int i,int x)
{
	while(i<N)
	{
		s[i]+=x;
		i+=lb(i);
	}
}
int query(int i)
{
	int ret=0;
	while(i>0)
	{
		ret+=s[i];
		i-=lb(i);
	}
	return ret;
}

可视化#

来自树状数组详解（附图解，模板及经典例题分析）- CSDN ↗

解释#

设基于 a[i] 建立树状数组 s[i]，则对于一个位置 i，s[i] 将会存储 $[i-\operatorname{lb}(i)+1,i]$ 的求和。特别地，对所有奇数位置 i 有 s[i]=a[i]。

不理解？举个例子：

假设 $i_0=(110100)_2$ ，那么 $(110001)_2,(110010)_2,(110011)_2,(110100)_2$ 这几个位置都会通过若干次 i+=lb(i) 的操作转移到 $i_0$，也就是上图中的小子树。

此外，我们注意到 $2^p$ 位置会存储全局的前缀和，因此有一个很巧妙的应用——

查找前缀和 $\ge k$ 的最小位置#

要求前缀和递增，即原数组非负。

这个本应是平衡树的任务之一，但是使用树状数组也可以实现，并且复杂度优秀、常数小。

一般做法#

二分查找位置，然后比较前缀和与 $k$. 复杂度 $O(\log^2n)$.

优化#

通过倍增，与树状数组深度结合，类似 ST 表思想，思路来自 P10497 题解 ↗。

从 $1$ 开始倍增 $2^p$，由于上述分析，我们知道 s[1<<p] 位置存储了全局前缀和，因此是正确的；倍增到最大的 $p_0$，使得 $s[2^{p_0}]<k$，然后维护一个 sum+=s[1<<p].

接着，从新的位置 $i=2^{p_0}$ 继续倍增，找到使得 $sum+s[i+2^p]<k$ 的最大的 $p_1$，然后一直继续。此处，由于 $s[i+2^p]$ 保存的是 $[i+2^p-\operatorname{lb}(i+2^p)+1,i+2^p]$ 的区间和，也就是 $[i+1,i+2^p]$ 的区间和，因此 $sum+s[i+2^p]$ 得到的仍然是全局前缀和。继续 sum+=s[1<<p].

最终，得到的 $i$ 就是最大的 $pre[i]<k$ 的位置，$i+1$ 即为所求。

重新审视上述过程，发现我们其实是利用了树状数组本身的倍增机制，始终保证我们可以维护全局前缀和以供比较。

复杂度 $O(\log n)$.