欢迎访问我的博客:blog.chungzh.cn

早就学习过线段树了,但惭愧的是更简单的树状数组却一直没有深入理解过,仅仅停留在背代码的层级。今天认真学习一下树状数组。

引入

树状数组(Binary Index Tree, BIT / Fenwick Tree)支持单点修改区间查询两种简单操作,时间复杂度均为 O(logn)O(\log n)。它的实现比线段树简单,速度更快,但功能稍逊一筹。

原理

bit

我们用 CiC_i 来表示 AA 数组的一段区间,定义 xx 的二进制表示中,最低位的 11 的位置为 lowbit(x)\operatorname{lowbit}(x),那么用 CiC_i 代表 AA 数组的下标区间 [ilowbit(i)+1,i][i-\operatorname{lowbit}(i)+1, i]。举个例子,4(10)=100(2)4_{(10)} = 100_{(2)}100(2)lowbit(100(2))+1(2)=1(2)=1(10)100_{(2)}-\operatorname{lowbit}(100_{(2)})+1_{(2)}=1_{(2)}=1_{(10)},那么 C4C_4 代表的区间就是 [1,4][1, 4]。通过这样的设计,树状数组将结点数压缩到与数组长度相同,不像线段树一样需要 2n2n 个结点。

之所以会有这个特点,是因为对于位置 ii,其对应的结点所在的高度就是 lowbit(i)\operatorname{lowbit}(i) 的位数。第一层结点为全体 20+21k2^0 + 2^1k,即所有 lowbit(i)=1\operatorname{lowbit}(i)=1 的数字;第二层结点为全体 21+22k2^1 + 2^2k ,即所有 lowbit(i)=2\operatorname{lowbit}(i)=2 的数字;第三层结点为全体 22+23k2^2 + 2^3k ,即所有 lowbit(i)=4\operatorname{lowbit}(i)=4 的数字;以此类推。也就是说,对于位置 ii,在这个位置往上垂直追溯,能追溯的层数就是 ii 的二进制表示的末尾 00 数量。而结点高度又决定了其子树的大小,于是它所代表的信息区间大小也就一定是 2i的末尾0数量=lowbit(i)2^{i的末尾0数量}=\operatorname{lowbit}(i)

*来源于参考资料 1

实现

lowbit\operatorname{lowbit} 如何计算呢?我们有这样一条公式:lowbit(x)=(x)&(x)\operatorname{lowbit}(x)=(x)\&(-x)。在计算机中,有符号数采用补码表示。在补码表示下,xx 的相反数 -x = ~x + 1,也就是按位非再加一。例如 xx 的最后一个 11 的位置附近是 01000\cdots 01000\cdots,按位非之后是 10111\cdots 10111\cdots,加一再变成 11000\cdots 11000\cdots;而前面每一位都与原来相反。这时我们再把它和 xx 按位与,得到的结果为 0100001000\cdotslowbit(x)\operatorname{lowbit}(x)

单点修改

修改操作类似于向上爬树的过程。例如我们要修改第三个元素,那么依次要修改 C3,C4,C8C_3, C_4, C_8,用二进制表示就是 11,100,100011, 100, 1000,发现下标 xx 每次都要 x+=lowbit(x)x += \operatorname{lowbit}(x),直到到达顶部。

int add(int x, int y) {
	while (x <= n) {
		tree[x] += y;
		x += lowbit(x);
	}
}

区间查询(前缀和)

例如查询第六个元素的前缀和,即 [1,6][1, 6] 这一区间。首先 C6C_6 表示的区间是 [5,6][5, 6],然后跳到 C4C_4,代表的区间是 [1,4][1, 4],加起来就 OK 了。从 C6C_6C4C_4 是怎么跳的呢?实际上是 110lowbit(110)=100110 - \operatorname{lowbit}(110) = 100。所以下标 xx 每次都要 x=lowbit(x)x -= \operatorname{lowbit}(x),直到 x<1x<1

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

至于求 [a,b][a, b] 这一区间的和,只需要分别求 [1,b][1, b][1,a)[1, a) 再相减即可。

O(n)O(n) 建树

暴力的建树方法是进行 nn 次单点修改,时间复杂度为 O(nlogn)O(n\log n)

有两种方法可以实现 O(n)O(n) 建树。

前缀和

前面讲到 CiC_i 表示的区间是 [ilowbit(i)+1,i][i-\operatorname{lowbit}(i)+1, i],那么我们可以先预处理一个 sumsum 前缀和数组,再计算 CC 数组。

void init() {
  for (int i = 1; i <= n; ++i) {
    C[i] = sum[i]-sum[i-lowbit(i)];
  }
}

倒着贡献

我们很容易知道当前点 ii 的父亲是 i+lowbit(i)i+\operatorname{lowbit}(i),所以用自己的值更新父亲即可。

void init() {
  for (int i = 1; i <= n; ++i) {
    C[i] += a[i];
    int j = i + lowbit(i);
    if (j <= n) C[j] += C[i];
  }
}

参考资料

  1. 树状数组的原理是什么? - SleepyBag 的回答 - 知乎
  2. 算法学习笔记(2) : 树状数组 - Pecco 的文章 - 知乎