树状数组

我是一个无情的博客搬运工

1.树 or 数组？

​ 名曰树状数组，那么究竟它是树还是数组呢？数组在物理空间上是连续的，而树是通过父子关系关联起来的，而树状数组正是这两种关系的结合，首先在存储空间上它是以数组的形式存储的，即下标连续；其次，对于两个数组下标x，y(x < y)，如果x + 2^k = y (k等于x的二进制表示中末尾0的个数)，那么定义(y, x)为一组树上的父子关系，其中y为父结点，x为子结点。

其中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为奇数 )。从图中可以得出：

1
2
3
4
5
6
7
8
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

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

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

其实ABCDE1000 的所有儿子就是 ABCDE0100， ABCDE0110， ABCDE0111，所以最左儿子就是ABCDE0100

​ 这时候，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.求和操作

  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]

代码：

1
2
3
4
5
6
7
int sum(int x){
        int s =0;
        for(int i = x; i ; i -= lowbit(i)){
            s += c[i][j];
        }
        return s;    
    }

4.更新操作

​ 更新操作就是之前提到的add(i, 1) 和 add(i, -1)，更加具体得，可以推广到add(i, v)，表示的其实就是 A[i] = A[i] + v。但是我们不能在原数组A上操作，而是要像求和操作一样，在树状数组C上进行操作。
​ 那么其实就是求在Ai改变的时候会影响哪些Ci，看图的树形结构就一目了然了，Ai的改变只会影响Ci及其祖先结点，即A5的改变影响的是C5、C6、C8；而A1的改变影响的是C1、C2、C4、C8。
​ 也就是每次add(i, v)，我们只要更新Ci以及它的祖先结点，之前已经讨论过两个结点父子关系是如何建立的，所以给定一个x，一定能够在最多log(n) (这里的n是之前提到的值域) 次内更新完所有x的祖先结点，add(i, v)的主体代码（去除边界判断）也只有一行代码：

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

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

代码：

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

5.lowbit

上文提到的两个函数sum(x)和add(x, v)都是用递归实现的，并且都用到了一个函数叫lowbit(x)，表示的是$2^k$，其中k为x的二进制表示末尾0的个数

代码：

1
2
3
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)。

7.板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int c[MAX];
int a[MAX];

int lowbit(int x) //要取的数
{
	return x & -x;
}
void add(int x,int v)//更新的数，更新的值
{
	for(int i = x; i <= n; i += lowbit(i))
	{
        c[i] += v;
    }
}
int sum(int x)//求和的右坐标
{
    int s =0;
    for(int i = x; i ; i -= lowbit(i))
    {
        s += c[i];
    }
    return s;    
}