树状数组

零. 前言

本文是在笔者参考 boba5551 在 TopCoder 上的 Algorithm Tutorial 后写的

有关 boba5551 的 Blog 原文，请点击右边的链接：Binary Indexed Trees

一. 树状数组的定义

假设现在有一组数：a[1], a[2], a[3], ... , a[n]（注意：下标是从 1 开始的）

一个数组 tree[idx] 记录的是

令 r 表示：在 idx 的二进制表示下，最后一个 1 的位置

那么 tree[idx] 表示：下标 i 在 [idx-2^r+1, idx] 中的 a[i] 的和

这个奇葩的表示法，可能会比较难理解，也可能被我给说晕了，我们来看看下面的一个例子

举个例子：tree[6]

为了方便阅读，对于一个数字，我们在他的右下角加一个下标表示他是几进制下的数，例如 6 是十进制下的数，那么就表示为 6₁₀

6₁₀=110₂

tree[110₂]=a[100₂+1₂]+a[100₂+1₂+1₂]

即：tree[6₁₀]=a[5₁₀]+a[6₁₀]

当然，实际上我们讨论的都是十进制下的，所以除非不是十进制数，我们就不写下标了

可能这一个例子还不能使读者理解，那么看看下面的一个表格，还不能理解的读者请细细体会

Binary Index Tree 每个 index 表示的区间一览表
tree	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
表示的区间	[1, 1]	[1, 2]	[3, 3]	[1, 4]	[5, 5]	[5, 6]	[7, 7]	[1, 8]	[9, 9]	[9, 10]	[11, 11]	[9, 12]	[13, 13]	[13, 14]	[15, 15]	[1, 16]

二. 取一个正数在二进制下的最后一个 1

这里要用到计算机编码的相关知识

我们知道，在计算机中，所以的数都是采用的二进制表示的，通常，有三种编码方式：

原码（Signed-Magnitude Representation）：最高位是符号位，0 正 1 负

反码（One's-Complement Representation）：表示负数的时候，在原码的基础上，符号位不变，其余位按位取反

补码（Two's-Complement Representation）：表示负数的时候，在补码的基础上，再加上 1

正数在三种编码中都是一样的表示，例如：6₁₀=00000110₂（原码）=00000110₂（反码）=00000110₂（补码）

而负数却不同，例如：-6=10000110₂（原码）=11111001₂（反码）=11111010₂（补码）

计算机采用的是补码的表示法，在此基础上，怎么得到一个正数的最后一位 1 呢？观察上面 6 和 -6 的补码表示我们不难得到一个猜测：x&(-x)

没错，这个猜测是正确的，下面来证明这个猜测

x = (a)(1)(b)₂ 其中 a 是随便一个二进制数；b 是一个全部为 0 的二进制数

-x =(a)^-(0)(b)^-₂+1 其中 a^-₂ 表示 a 这个二进制数所有位按位取反

=(a)^-(1)(b)₂

x&(-x) = (1)(b)₂ 这样我们就证明到了上面猜想的正确性

于是，我们要取正数 x 的最后一位 1，只需要执行 x&(-x) 即可

三. 更新点的操作

更新点，就是把某个 a[i] 的值加上或者减去一个数，其实都可以归结为加法

需要注意的是，更新 i 这个点，我们能影响到的就是所有能够覆盖 i 这个点的 tree 节点，如果 a[i] 的值加上了 keyVal，那么所有能够覆盖 i 这个点的 tree 节点都应该加上 keyVal

首先，第一个能够覆盖 i 的 tree 节点肯定是 tree[i]，但是下一个是谁呢？我们来看看看下面的这幅图：

更新 1 这个节点会影响到 2，4，8，16，...

更新 2 这个节点会影响到 4，8，16，...

更新 3 这个节点会影响到 4，8，16，...

更新 4 这个节点会影响到 8，16，...

更新 5 这个节点会影响到 6，8，16，...

...

有什么规律？

把他们写成二进制看看：

更新 1₂ 会影响到 10₂ 100₂ 1000₂ 10000₂ ...

更新 10₂ 会影响到 100₂ 1000₂ 10000₂ ...

更新 11₂ 会影响到 100₂ 1000₂ 10000₂ ...

更新 100₂ 会影响到 1000₂ 10000₂ ...

更新 101₂ 会影响到 110₂ 1000₂ 10000₂ ...

...

假设现在要更新的是 x，能影响到的下一个是 x+(x&(-x))

我们不难写出如下的 update 代码

update

1 void update(int tree[], int pos, int val)
2 {
3     for(; pos<N; pos+=pos&(-pos))
4         tree[pos]+=val;
5 }

四. 查询某段区间的和

假设现在我们要查询的是 [1，pos] 这个区间中所有的数的和，不难想到这样的处理方式：

把 pos 用二进制表示。比如 6 表示成为 110₂

然后查询每一个 tree[110₂]+tree[100₂]

至于为什么，相信读者根据 binary index tree 的定义，很容易想明白的

那么现在假设要查询的区间是 [L，R]，我们完全可以用 [1，R] 的和减去 [1，L-1] 的和，不过要注意下 L 等于 1 的时候（按照下面的查询代码，是不会出错的）

可以容易的写出如下的 query 代码

query

1 int query(int tree[], int pos)
2 {
3     int sum=0;
4     for(; pos; pos-=pos&(-pos))
5         sum+=tree[pos];
6     return sum;
7 }

五. 查询某个点的值

我们完全可以用查询区间的值处理这种查询，相信读者也很容易推出来：query(tree, pos)-query(tree, pos-1)

但是这种方法还不是最优的，因为他是 2log(N) 级别的，在 boba5551 的 blog 中还有一种更优的方法，是 log(N) 级别的，这里不再讲述，有兴趣的读者可以看看原文，代码也很短

不过对于这种“更新点查询点”的问题，一般也没谁会用树状数组吧？

六. 后记

关于树状数组的介绍先到这里，本打算一次性写完二维树状数组、更新区间查询区间和更新区间查询点的，但这着实是一件浩大的工程，时间有限，以后再写

这算是树状数组的一个入门级的介绍了吧