线段树和树状数组

线段树和树状数组是一系列神奇的数据结构的起源,但其本身却十分简洁优雅,是我非常喜欢的两种数据结构。

树状数组(binary indexed tree)

考虑求和$A[n]=a[1..n]$,平凡的解法复杂度为$O(n)$,树状数组则是$O(log \, n)$的方法。
理解树状数组,可以考虑任何一个自然数$x$可以表示成:
$ x = a_0 2^0 + a_1 2^1 + … + a_n 2^n $,其中$a_i$可以取0或1。
我们看到这样的以2为底的“科学计数法”能够将加法的计算量减少到$log_{2}n$。
同样我们希望把对一个序列的求和计算也降为对数级的,容易想到可以缓存一些连续$2^n$个数的和作为子结构,例如我们可以算出下面的这张表,即T数组:

十进制 二进制 区域和T[i]即a[i..j]的和
1 1b $a[1]$
2 10b $a[1..2]$
3 11b $a[3]$
4 100b $a[1..4]$
5 101b $a[5]$
6 110b $a[5..6]$
7 111b $a[7]$
8 1000b $a[1..8]$
9 1001b $a[9]$
10 1010b $a[9..10]$
11 1011b $a[11]$
12 1100b $a[9..12]$
13 1101b $a[13]$
14 1110b $a[13..14]$
15 1111b $a[15]$
16 10000b $a[1..16]$
17 10001b $a[17]$
18 10010b $a[17..18]$
19 10011b $a[19]$

下面我们尝试利用上面的表计算$A[13]$,首先把13分解成2的幂的代数和,即$13 = 8 + 4 + 1$。查表,我们发现$A[13] = T[8] + T[12] + T[13]$。而$T[8]$、$T[12]$、$T[13]$区间的长度分别对应了8、4、1。下面是个直观的图。

这张表是如何得出的呢?定义$T[i]$为区间$a[i-lowbit(i)+1 .. i]$共$lowbit(i) = 2^k$个元素的和,也就是说$i$最多能被2的几次幂整除,就从$i$开始往前数几个。
下面用程序来描述查表的过程。我们要从“边长”小的方块往大的方块加,即$13 \rightarrow 9..12 \rightarrow 1..8$,即

1
2
3
for (int x = i; x > 0; x -= lowbit(x)){
...
}

树状数组不仅能快速查找,还能快速更新。更新位置$i$处的值时,我们按照以下规则更新:

  1. 只更新$i$位置后的节点,因为根据定义,$i$前的节点不可能包含$i$。
  2. 只更新“边长”为1(即自己)、2、…、$2^n$等2的幂次的节点,有些“边长”可能碰不到,其实这就取决于$i$在2进制表示中1出现的位置了。
    例如更新了$a[3]$,就要同时更新4、8、16这些位置;更新了$a[7]$就要同时更新8、16、32这些幂次;更新$a[11]$就要更新12、16这些节点
    1
    2
    3
    4
    for (int x = i; x <= maxn; x += lowbit(x)){
    // 注意是maxn不是a的实际个数n
    ...
    }

最后推荐另外一个教程

二维树状数组

二维树状数组中比较常见的题型是矩形区域最值/和问题。如刚遇到的hiho1336

线段树(segment tree)

基础线段树

一个基础的线段树支持单点修改和区间查询

PushDown和PushUp

将线段树的各个操作提炼出得到一个模板,这样用户只需要PushUp这个操作和Update的一个终止条件。其中PushUp在Update和Build函数中使用,用来合并两个子区间的性质。

线段树数组的大小MAXN应当至少为4N

假设对$[1..N]$建立线段树,其中$2^n <= N <= 2^{n+1}$。容易得到树的底层至少需要$2^{n+1}$个节点,因此整个树需要$2^{n+2}$个节点,也就是必须满足$MAXN \ge 2^{n+2}$ 。把$n$用$N$代替,得到$4N >= 2^{n+2}$,显然对于任意$MAXN \ge 4N$,有$MAXN \ge 2^{n+2}$。

线段树查询

  1. 为什么需要$fr$,$to$,$l$,$r$四个变量?
    线段树的查询开销在$O(lgn)$。假设我们要求$[fr .. to]$之间的值,我们实际上是找寻若干长度为$2^i$的若干子树,它们的并集能够恰好覆盖$[fr .. to]$区间。由于线段树的结构是二分的,$[l .. r]$表示线段树中我们搜索到的当前节点所表示的区间。我们根据$l$、$r$与$fr$、$to$的关系可以判断出全取$[l, r]$结果,全不取$[l, r]$结果还是继续二分搜索。
  2. 开闭区间的问题
    首先要注意优先级,<<的优先级低于+,所以应当写成(root << 1) + 1这样。
  3. Modify操作只需要更新(被影响的)一侧

线段树的区间更新

可以对线段树进行区间更新,为了保证$log n$的复杂度,显然对每个叶子节点的更新是不可能的了,因此我们使用一个lazy[]辅助数组。当我们的update函数遍历到满足fr <= l && r <= to时,我们就停止进行update,而设置lazy[root] = tree[root],其中tree是我们维护的线段树。
与此同时我们引入PushDown这个操作。PushDown在Update和Query函数中使用,负责将本层的lazy更新信息传递给下一层。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void PushDown(int root, int ln, int rn)
{
// 当具有lazy标记时
if(lazy[root] != -1)
{
// 注意更新时仍然需要维护区间性质,而不能简单赋值为lazy[root]
// 下面的代码维护了区间内最大值的性质
tree[root << 1] = max(lazy[root], tree[root << 1]);
tree[root << 1 | 1] = max(lazy[root], tree[root << 1]);
lazy[root << 1] = max(lazy[root], lazy[root << 1]);
lazy[root << 1 | 1] = max(lazy[root], lazy[root << 1 | 1]);
// 取消lazy标记
lazy[root] = -1;
}
return;
}

二维线段树

下面用二维线段树来解决刚才的问题。
这道题目需要写三个update,原因是在使用update2更新完rx行以0为根的所有列构成的子树后,需要更新第i列中以rx行为根构成的子树。如果不更新,那么将来对于任意的第i列,当x为非叶子节点时,tree[x][i]的值都为0。
如果暴力一波肯定会T。

1
2
3
4
for (int i = 0; i < 4 * n; i++)
{
tree[rx][i] = tree[rx * 2 + 1][i] + tree[rx * 2 + 2][i];
}

所以需要用一个和update2类似的update3来更新
代码

zkw线段树

普通的递归版本的线段树的常数是比较大的,但有些题目可以考虑使用zkw线段树。