线段树和树状数组

发表于 |

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

树状数组(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操作只需要更新（被影响的）一侧

线段树离散化

将所有的 Update 按照顺序映射到一个数组中。

线段树的区间更新

可以对线段树进行区间更新，为了保证$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线段树。