ACM►知识小结

线段树小结

前言：

实验室要开展每周的算法讲堂活动，大概是每周一个集训队员来给大家将一个知识点，于是我去讲线段树来开头了，但是自己好弱啊，自从寒假集训后就一直没敲过线段树代码了，于是这几天一直在照着金巨巨的博客刷线段树的题（也是抄的金巨巨的模板…）。

这里总结一些做到的题，一些线段树的基本思路，也当做理一下总结的思路。

用到的一些宏定义：

1
2
3
#define lson root<<1
#define rson root<<1|1
#define MID int m = (l + r) / 2

线段树的基本概念：

如果把线段树当做一个数据结构的话，那么可以这样解释线段树：

首先线段树是一颗二叉树，特殊的是线段树的每个节点，用来维护一段区间的信息，通常的写法都是这样，假设父节点维护的区间是$[a, b]$，那么他的左右儿子维护的区间分别是$[a, (a+b)/2], [(a+b)/2+1, b]$。

一个节点维护的信息通常有，区间和，区间连续子串和，区间最大值，区间最小值等。

建树过程：

构造一颗线段树的过程，可以参考分治算法的步骤：

  1. 假设要计算区间$[a, b]$中需要维护的信息，我们将这个问题分解成计算$[a, (a+b)/2], [(a+b)/2+1, b]$中需要维护的信息两个子问题，这样子问题与原问题的形式一样，只是规模更小.
  2. 对于第一步分解出的每个子问题，继续使用第一步进行分解得到规模更小的子问题，直到问题的规模足够小，可以直接求解。通常来讲是区间长度为$1$的时候，这样容易计算出需要维护的信息，比如区间和、区间极值等可以以$O(1)$的时间直接计算出。
  3. 最后一步是将上面分解出的子问题的解，合并成原问题的解，通常这一步也是最难的一步。

下面是建树的代码，完美的符合了上述过程。
这里需要注意的一点是，对于每个节点，要么他是一个叶子节点，要么他是一个同时具有左右儿子的节点。

1
2
3
4
5
6
7
8
9
10
void build (int root ,int l, int r) {
    if (l == r) {
        tree[root].maintain(data[l], l);
        return;
    }
    MID;
    build(lson, l, m);
    build(rson, m+1, r);
    tree[root] = tree[lson] + tree[rson];
}

通过上述分治的步骤，我们也可以另一种方式理解线段树：
我们要解决一个大问题，然后我们用分治的方法是解决这个问题，不过这里我们要把每一步解决的子问题的解都记录下来。这样所有子问题的解，和原问题的解就构成了一颗线段树。

更新：

线段树的更新过程，也是递归来实现的。这里以单点更新来举例，因为线段树是储存着许多子问题的解的，所以对一个点进行更新，可能会对多个子问题有影响，这里我们也用分治算法去更新。

假设要对$[1,n]$的区间下标为$p$的点进行更新。那么对于$[1,n]$区间可以先对他的两个儿子节点$[1,(1+n)/2], [(1+n)/2+1, r]$进行更新，$[1,n]$区间可由更新后的两个儿子节点组合而成。对他的两个儿子节点也进行如下操作，直到一个节点可以直接计算出更新后的变化。

下面是更新的代码，符合上述过程，不过这里加入了一个剪枝，如果需要更新的点不在当前节点维护的区间，那么这次更新对当前节点一点没有影响，不需要继续向下更新。

1
2
3
4
5
6
7
8
9
10
11
12
void updata(int root, int l, int r, int pos, int v) {
    if (pos < l || r < pos)
        return;
    if (l == r) {
        tree[root].maintain(v, pos);
        return;
    }
    MID;
    updata(lson, l, m, pos, v);
    updata(rson, m+1, r, pos, v);
    tree[root] = tree[lson] + tree[rson];
}

查询：

查询过程其实就是用已经解决的子问题的解去构造新问题的解的过程。

比如之前说过，对于一个维护$[1,n]$区间的线段树，它里面就存着着分治解决$[1,n]$这个问题的所有子问题的解。那么对于每次查询区间$[l,r],1\leq l \leq r \leq n$，都是一个规模小于$[1,n]$的问题。那么对于这个问题的解，可以用解决$[1,n]$问题的子问题的解构造出来。

以下是查询过程中的代码，就是遍历原问题的所有子问题的解，去构造新问题的解，这里加入了剪枝，如果一个区间和需要查询的区间没有交集，那么就可以剪枝。

1
2
3
4
5
6
7
8
9
Info query(int root, int l, int r, int ql, int qr) {
    if (qr < l || r < ql)
        return Info();
    if (ql <= l && r <= qr) {
        return tree[root];
    }
    MID;
    return query(lson, l, m, ql, qr) + query(rson, m+1, r, ql, qr);
}

合并：

所谓合并就是合并两个节点为一个节点，也就是合并子问题，构造原问题解的过程。

比如我分别知道$[a, b]$和$[b+1, c]$区间的最大值为$x_1, x_2$，那么区间$[a, b]$的最大值，那么就是$max(x_1, x_2)$。这样就用这两段区间的解构造出了另一个区间的解。

这里重载了加号，用起来比较方便。

1
2
3
4
5
Info operator + (const Info & a, const Info & b) {
    Info rst;
    rst.value = max(a.value, b.value);
    return rst;
}

当然这只是一个简单的例子，在许多线段树中合并起来非常麻烦，比如求一段区间内的最大的连续子串和。

对于区间$[1, n]$，那么最长连续子串和一定来自于以下的三种：

  • 区间$[1,(n+1)/2]$的最长连续子串和；
  • 区间$[(n+1)/2+1, n]$的最长连续子串和；
  • 区间$[1,(n+1)/2]$的从右端开始的最长连续子串和加上区间$[(n+1)/2+1,n]$从左端开始的最长连续子串和。

对于每段区间需要维护三个信息，从左端开始的最长连续子串和，从右端开始的最长连续子串和，最长连续子串和。分别记为lmax,rmax,value。

那么合并两个区间的代码如下：

1
2
3
4
5
6
7
8
Info operator + (const Info & a, const Info & b) {
    Info rst;
    rst.lmax = max(a.lmax, a.sum + b.lmax);
    rst.rmax = max(b.rmax, a.rmax + b.sum);
    rst.sum = a.sum + b.sum;
    rst.value = max(max(a.value, b.value), a.rmax + b.lmax);
    return rst;
}

这里为了方便操作，记录了区间的和。