夜深人静写算法（三） - 树状数组

图二-1-1

如图二-1-1，其中A为普通数组，C为树状数组（C在物理空间上和A一样都是连续存储的）。树状数组的第4个元素C4的父结点为C8 (4的二进制表示为”100″，所以k=2，那么4 + 2^2 = 8)，C6和C7同理。C2和C3的父结点为C4，同样也是可以用上面的关系得出的，那么从定义出发，奇数下标一定是叶子结点。

2、结点的含义

然后我们来看树状数组上的结点Ci具体表示什么，这时候就需要利用树的递归性质了。我们定义Ci的值为它的所有子结点的值 和 Ai 的总和，之前提到当i为奇数时Ci一定为叶子结点，所以有Ci = Ai ( i为奇数 )。从图中可以得出：
C1 = A1
C2 = C1 + A2 = A1 + A2
C3 = A3
C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4
C5 = A5
C6 = C5 + A6 = A5 + A6
C7 = A7
C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
建议直接看C8，因为它最具代表性。

我们从中可以发现，其实Ci还有一种更加普适的定义，它表示的其实是一段原数组A的连续区间和。根据定义，右区间是很明显的，一定是i，即Ci表示的区间的最后一个元素一定是Ai，那么接下来就是要求Ci表示的第一个元素是什么。从图上可以很容易的清楚，其实就是顺着Ci的最左儿子一直找直到找到叶子结点，那个叶子结点就是Ci表示区间的第一个元素。

更加具体的，如果i的二进制表示为 ABCDE1000，那么它最左边的儿子就是 ABCDE0100，这一步是通过结点父子关系的定义进行逆推得到，并且这条路径可以表示如下：
ABCDE1000 => ABCDE0100 => ABCDE0010 => ABCDE0001

这时候，ABCDE0001已经是叶子结点了，所以它就是Ci能够表示的第一个元素的下标，那么我们发现，如果用k来表示i的二进制末尾0的个数，Ci能够表示的A数组的区间的元素个数为2^k，又因为区间和的最后一个数一定是Ai，所以有如下公式：
Ci = sum{ A[j] | i – 2^k+ 1 <= j <= i } （帮助理解：将j的两个端点相减+1 等于2^k）

3、求和操作

明白了Ci的含义后，我们需要通过它来求sum{ A[j] | 1 <= j <= i }，也就是之前提到的sum(i)函数。为了简化问题，用一个函数lowbit(i)来表示2^k(k等于i的二进制表示中末尾0的个数)。那么：
sum(i) = sum{ A[j] | 1 <= j <= i } = A[1] + A[2] + … + A[i]
= A[1] + A[2] + A[i-2^k] + A[i-2^k+1] + … + A[i]
= A[1] + A[2] + A[i-2^k] + C[i]
= sum(i - 2^k) + C[i]
= sum( i – lowbit(i) ) + C[i]

由于C[i]已知，所以sum(i)可以通过递归求解，递归出口为当i = 0时，返回0。sum(i)函数的函数主体只需要一行代码：

int sum(int x){       return x ? C[x]+ sum( x - lowbit(x)):0;  }

观察 i – lowbit(i)，其实就是将i的二进制表示的最后一个1去掉，最多只有log(i)个1，所以求sum(n)的最坏时间复杂度为O(logn)。由于递归的时候常数开销比较大，所以一般写成迭代的形式更好。写成迭代代码如下：

int sum(int x){          int s =0;          for(int i = x; i ; i -= lowbit(i)){              <strong>s += c[i][j];</strong>          }          return s;          }

4、更新操作

更新操作就是之前提到的add(i, 1) 和 add(i, -1)，更加具体得，可以推广到add(i, v)，表示的其实就是 A[i] = A[i] + v。但是我们不能在原数组A上操作，而是要像求和操作一样，在树状数组C上进行操作。

那么其实就是求在Ai改变的时候会影响哪些Ci，看图二-1-1的树形结构就一目了然了，Ai的改变只会影响Ci及其祖先结点，即A5的改变影响的是C5、C6、C8；而A1的改变影响的是C1、C2、C4、C8。

也就是每次add(i, v)，我们只要更新Ci以及它的祖先结点，之前已经讨论过两个结点父子关系是如何建立的，所以给定一个x，一定能够在最多log(n) (这里的n是之前提到的值域) 次内更新完所有x的祖先结点，add(i, v)的主体代码（去除边界判断）也只有一行代码：

void add(int x,int v){       if(x <= n){           C[x]+= v, add( x + lowbit(i), v );       }  }

和求和操作类似，递归的时候常数开销比较大，所以一般写成迭代的形式更好。写成迭代形式的代码如下：

void add(int x,int v){      for(int i = x; i <= n; i += lowbit(i)){          C[i] += v;      }  }

5、lowbit函数O(1)实现

上文提到的两个函数sum(x)和add(x, v)都是用递归实现的，并且都用到了一个函数叫lowbit(x)，表示的是，其中k为x的二进制表示末尾0的个数，那么最简单的实现办法就是通过位运算的右移，循环判断最后一位是0还是1，从而统计末尾0的个数，一旦发现1后统计完毕，计数器保存的值就是k，当然这样的做法总的复杂度为O( logn )，一个32位的整数最多可能进行31次判断（这里讨论整数的情况，所以符号位不算）。这里介绍一种O(1)的方法计算2^k的方法。

正数：正数的补码即其二进制表示；例如一个8位二进制的整数+5，它的补码就是 00000101 （标红的是符号位，0表示”正”，1表示“负”）

负数：负数的补码即将其整数对应的二进制表示所有位取反(包括符号位)后+1；例如一个8位二进制的整数-5，它的二进制表示是00000101，取反后为11111010，再+1就是11111011，这就是它的补码了。

下面的等式可以帮助理解补码在计算机中是如何工作的：
+5 + (-5) = 00000101 + 11111011 = 1 00000000 (溢出了!!!) = 0这里的加法没有将数值位和符号位分开，而是统一作为二进制位进行计算，由于表示的是8进制的整数，所以多出的那个最高位的1会直接舍去，使得结果变成了0，而实际的十进制计算结果也是0，正确。

补码复习完毕，那么来看下下面这个表达式的含义：x & (-x) (其中 x >= 0)

首先进行&运算，我们需要将x和-x都转化成补码，然后再看&之后会发生什么，我们假设 x 的二进制表示的末尾是连续的 k 个 0，令x的二进制表示为 X₀X₁X₂…X_n-2X_{n-1, 则} {X_i = 0 | n-k <= i < n}， 这里的X₀表示符号位。

x的补码就是由三部分组成：(0)(X₁X₂…X_n-k-1)(k个0) 其中X_n-k-1为1，因为末尾是k个0，如果它为0，那就变成k+1个0了。

-x的补码也是由三部分组成：(1)(Y₁Y₂…Y_n-k-1)(k个0) 其中Y_{n-k-1为1，其它的}X_i和Y_i相加为1，想想补码是怎么计算的就明白了。

那么 x & (-x) 也就显而易见了，由两部分组成 (1)(k个0)，表示成十进制为 2^k 啦。由于&的优先级低于-，所以代码可以这样写：

int lowbit(int x) {       return x & -x;  }

6、小结

至此，树状数组的基础内容就到此结束了，三个函数就诠释了树状数组的所有内容，并且都只需要一行代码实现，单次操作的时间复杂度为O( log(n) )，空间复杂度为O(n)，所以它是一种性价比非常高的轻量级数据结构。

树状数组解决的基本问题是 单点更新，成端求和。上文中的sum(x)求的是[1, x]的和，如果需要求[x, y]的和，只需要求两次sum函数，然后相减得到，即sum(y) – sum(x-1)。

下面一节会通过一些例子来具体阐述树状数组的应用场景。

三、树状数组的经典模型

1、PUIQ模型

【例题1】一个长度为n(n <= 500000)的元素序列，一开始都为0，现给出三种操作：
1. add x v : 给第x个元素的值加上v； ( a[x] += v )
2. sub x v : 给第x个元素的值减去v； ( a[x] -= v )
3. sum x y： 询问第x到第y个元素的和； ( print sum{ a[i] | x <= i <= y } )

这是树状数组最基础的模型，1和2的操作就是对应的单点更新，3的操作就对应了成端求和。

具体得，1和2只要分别调用add(x, v)和add(x, -v), 而3则是输出sum(y) – sum(x-1)的值。

我把这类问题叫做PUIQ模型(Point Update Interval Query 点更新，段求和)。

2、IUPQ模型

【例题2】一个长度为n(n <= 500000)的元素序列，一开始都为0，现给出两种操作：
1. add x y v : 给第x个元素到第y个元素的值都加上v； ( a[i] += v, 其中 x <= i <= y )
2. get x： 询问第x个元素的值； ( print a[x] )

这类问题对树状数组稍微进行了一个转化，但是还是可以用add和sum这两个函数来解决，对于操作1我们只需要执行两个操作，即add(x, v)和add(y+1, -v)；而操作2则是输出sum(x)的值。

这样就把区间更新转化成了单点更新，单点求值转化成了区间求和。

我把这类问题叫做IUPQ模型(Interval Update Point Query 段更新，点求值)。

3、逆序模型

【例题3】给定一个长度为n(n <= 500000)的排列a[i]，求它的逆序对对数。1 5 2 4 3 的逆序对为(5,2)(5,3)(5,4)(4,3)，所以答案为4。

朴素算法，枚举任意两个数，判断他们的大小关系进行统计，时间复杂度O(n²)。不推荐！来看一个给定n个元素的排列 X₀ X₁ X₂ … X_n-2 X_n-1,对于某个 X_i 元素，如果想知道以它为”首”的逆序对的对数( 形如(X_iX_j) 的逆序对)，就是需要知道 X_i+1 … X_n-2 X_n-1 这个子序列中小于X_i 的元素的个数。

那么我们只需要对这个排列从后往前枚举，每次枚举到 X_i 元素时，执行cnt += sum(X_i-1)，然后再执行add(X_i, 1)，n个元素枚举完毕，得到的cnt值就是我们要求的逆序数了。总的时间复杂度O(nlogn)。

这个模型和之前的区别在于它不是将原数组的下标作为树状数组的下标，而是将元素本身作为树状数组的下标。逆序模型作为树状数组的一个经典思想有着非常广泛的应用。

【例题4】给定N(N <= 100000)个区间，定义两个区间(Si, Ei)和(Sj, Ej)的’>’如下：
如果Si <= Sj and Ej <= Ei and Ei – Si > Ej – Sj,则(Si, Ei) > (Sj, Ej)，现在要求每个区间有多少区间’>’它。将上述三个关系式化简，可以得到 区间i > 区间j 的条件是：区间i 完全覆盖 区间j，并且两者不相等。

void add(int x,int y,int v){      for(int i = x; i <= n; i += lowbit(i)){          for(int j = y; j <= n; j += lowbit(j)){              c[i][j]+= v;          }      }  }    int sum(int x,int y){       int s =0;       for(int i = x; i ; i -= lowbit(i)){           for(int j = y; j ; j -= lowbit(j)){               s += c[i][j];           }       }       return s;  }