基础数据结构 线段树

旧专栏由于年久失修，目前已被标记为过时。本文是对旧博客的重写及内容补充。

线段树的思想就是把一段区间拆分成两个子区间，运用递归的方式，线段树能在不大规模改动原数组的情况下实现区间信息的维护。有了这一点，区间信息维护的时间复杂度就从朴素暴力算法的优化到了。

前言

本文所使用的宏定义及含义如下：

宏名	定义	作用
`le(x)`	`(x * 2)`	获取左子树的下标
`ri(x)`	`(x * 2 + 1)`	获取右子树的下标
`leftSubtree(idx)`	`tree[le(idx)]`	获取左子树对象
`rightSubtree(idx)`	`tree[ri(idx)]`	获取右子树对象

线段树的建树

根据前文所说，线段树将一段长区间分为两段，并设为它自身的子树，不断递归直到区间长度为。如下图：

可见线段树是一棵满二叉树，它有个节点（为树的高度/层数，上图中）；此外还可以发现，对于下标为的节点，如果它存在子树，那么它的左子树的下标就是、右子树为。我们平常使用线段树，则需要开四倍的空间（pushdown 位置的不同、删去某些特判可能会让这一上限最多变为八倍空间，后文将阐述其原因）。

在建树时，我们需要处理出当前区间的中点，并分别递归左右子树继续建树、顺带维护区间左右端点的信息（区间大小、初始化懒标记等）。根据前文，递归终点是区间长度降落为，此时将原序列中的信息搬过去即可。

void build(int idx, int l, int r) {
    tree[idx].l = l, tree[idx].r = r; // 维护区间左右端点
    if (l == r) {
        tree[idx].max = a[l]; // 维护区间最大值
        return;
    }
    int mid = (l + r) >> 1;
    build(le(idx), l, mid); // 递归左子树
    build(ri(idx), mid + 1, r); // 递归右子树
    pushup(idx); // 更新父节点
}

线段树的节点更新

基本分两种，已知子节点更新父节点和已知父节点更新子节点。

第一种操作一般被称作 pushup 上传操作。在子节点更新完毕回溯时进行，起到更新父节点的作用；第二种操作被称作 pushdown 下传操作。在带有懒标记的线段树中向子节点递归查找信息时进行，能够将先前积累起来的操作下放到子节点。

一般在编写上传操作时，要考虑到所维护信息的结合性质。例如维护区间和，父节点记录的值显然应该是左右子树记录的值之和；再比如维护区间最大值，显然应该是左右区间分别记录的最大值中更大的那一个。

void pushup(int idx) {
    tree[idx].max = max(leftSubtree(idx).max, rightSubtree(idx).max); // 区间最大值
    tree[idx].sum = leftSubtree(idx).sum + rightSubtree(idx).sum;     // 区间和
    // ...
}

在写标记下传时，需要特别考虑标记之间的优先级关系。例如当前有两个操作——区间推平（赋成统一的值）和区间加。当该区间需要下传一个推平标记时，可以直接把区间加标记给清空，因为推平后就不会存在区间加；反过来就不成立，因为区间可以在推平后继续进行加法。因此我们需要先判断推平标记的情况，后面再来处理区间加标记。

void pushdown(int idx) {
    if (tree[idx].que != -LLONG_MAX) { // 区间推平优先处理
        leftSubtree(idx).max = tree[idx].que;
        leftSubtree(idx).que = tree[idx].que; // 继承推平标记
        leftSubtree(idx).add = 0; // 清空加法标记
        rightSubtree(idx).max = tree[idx].que;
        rightSubtree(idx).que = tree[idx].que;
        rightSubtree(idx).add = 0; // 清空加法标记
        tree[idx].que = -LLONG_MAX; // 清空推平标记
    }
    if (tree[idx].add) { // 区间加法后处理
        leftSubtree(idx).max += tree[idx].add;
        leftSubtree(idx).add += tree[idx].add;
        rightSubtree(idx).max += tree[idx].add;
        rightSubtree(idx).add += tree[idx].add;

        tree[idx].add = 0;
    }
}

线段树的查询操作

线段树既可以查询单点信息，也可以查询整个区间的信息，前者可以看作是区间长度为的区间查询，是区间查询的一类特殊情况。

在这个例子中，我们假设查询区间的某些信息，首先我们就需要找到这个区间：递归查找、缩小范围，发现当递归到下标时，区间就被包含了，于是直接返回；当查询至下标，区间被包含进去，此时我们就可以不用花费大力气继续向下递归了，因为线段树的父节点就存储了子节点的信息。以查询区间最大值为例：

int queryMax(int idx, int l, int r) {
    if (l <= tree[idx].l && tree[idx].r <= r) return tree[idx].max; // 完全包含，直接返回
    pushdown(idx);   // 子节点可能存在积累的操作
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    int res = -INF;
    if (l <= mid) res = max(res, queryMax(le(idx), l, r)); // 递归左侧
    if (r > mid) res = max(res, queryMax(ri(idx), l, r));   // 递归右侧
    return res;
}

线段树的修改操作

同样分为单点修改和区间修改，前者同样是后者的特殊情况。基本思路相同，先找到被完全包含的区间。但是此时可以有一个优化——不用每一次都递归到区间的叶子节点再进行修改，可以直接将修改信息记录在一个大区间内，当查询需要用到子节点的值时再一次性下放积累的操作。线段树中记录这些操作的标记便被称作懒标记。

对于某个区间，需要先把当前区间的相关信息修改之后再返回，否则相当于没有修改（只是打个标记，当前节点并未更新）。以区间加为例：

void modify(int idx, int l, int r, int x) {
    pushdown(idx); // 可能还有积累的操作
    if (l <= tree[idx].l && tree[idx].r <= r) {
        tree[idx].max += x; // 更新当前区间的最大值
        tree[idx].add += x; // 打标记
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (l <= mid) modify(le(idx), l, r, x, type);
    if (r > mid) modify(ri(idx), l, r, x, type);
    pushup(idx); // 由于更新了当前节点，需要向上更新其他节点
}

一些细节

一句话，让评测结果从 RE 到 AC

有时你会发现——明明题目中说了，我也开了四倍空间，为什么还是会 RE？事实上，这可能是因为错误的 pushdown 位置和特判的缺乏。

比如下面这段区间修改的代码（来源 P2574 XOR的艺术）：

void modify(int idx, int l, int r, int x) {
    pushdown(idx);
    if (l <= tree[idx].l && tree[idx].r <= r) {
        tree[idx].sum = x * tree[idx].size;
        tree[idx].que = x;
        tree[idx].lmax[x] = tree[idx].rmax[x] = tree[idx].max[x] = tree[idx].size;
        tree[idx].lmax[x ^ 1] = tree[idx].rmax[x ^ 1] = tree[idx].max[x ^ 1] = 0;
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (l <= mid) modify(le(idx), l, r, x);
    if (r > mid) modify(ri(idx), l, r, x);
    pushup(idx);
}

其中，代码中也是如此，但是最后有两个点 RE。这是因为 pushdown 放在了错误的位置上，在递归到单点前，会执行一次 pushdown 操作，此时就会在叶子节点的左右子树上检测懒标记（事实上没必要），在极端情况下，会访问到最后一个叶子节点的右子树（最坏），是肯定会 RE 的。把下传操作放在 l == r 的判断之后即可。

标记置零问题

有时，在下传操作中，在处理完当前标记之后是不能直接把标记置零的，例如（来源 P1253 扶苏的问题）：

void pushdown(int idx) {
    if (tree[idx].que != -LLONG_MAX) {
        leftSubtree(idx).max = tree[idx].que;
        leftSubtree(idx).que = tree[idx].que;
        leftSubtree(idx).add = 0;
        rightSubtree(idx).max = tree[idx].que;
        rightSubtree(idx).que = tree[idx].que;
        rightSubtree(idx).add = 0;

        tree[idx].que = -LLONG_MAX;
        tree[idx].add = 0;
    }
    if (tree[idx].add) {
        leftSubtree(idx).max += tree[idx].add;
        leftSubtree(idx).add += tree[idx].add;
        rightSubtree(idx).max += tree[idx].add;
        rightSubtree(idx).add += tree[idx].add;

        tree[idx].add = 0;
    }
}

乍一看没什么问题，但是推平标记里 tree[idx].add = 0 却是造成 WA 的元凶。清空加运算标记，其实也就意味着把整段区间的区间加标记清空。然而在递归时是有可能向该区间的某个子区间递归的，于是当前区间就会有一头一尾的部分位置不需要被处理，但是你却把它们的区间加标记清空了，显然错误。正确做法是删去这一行。

常见应用及应对策略

最大子段和

例题：GSS1 - Can you answer these queries I

难度：提高+/省选-

维护变量：最大前缀、最大后缀、最大子段和、区间和。

维护最大子段和考虑三种情况：

最大子段和为左侧的最大子段和
最大子段和为右侧的最大子段和
最大子段和跨区间，为左区间的最大后缀加右区间的最大前缀

最大子段和就是上述三种情况的最大值。

维护最大前缀考虑两种情况（最大后缀同理）：

最大前缀为左区间的最大前缀
最大前缀跨区间，为整个左区间和右区间的最大前缀之和

最大前/后缀就是上述两种情况的最大值。

注意选取的子段中必须包含至少一个元素，否则不可用这种方式做。

区间推平+区间翻转+最大连续数（01串）

例题：P2572 序列操作

题目难度：提高+/省选-

题目来源：四川 2010 各省省选

维护变量：区间左端最大连续数、区间右端最大连续数、区间最大连续数、区间大小、区间和

最大连续数考虑三种情况：

左区间最大连续数
右区间最大连续数
跨区间，左区间右端最大连续数与右区间左端最大连续数

最大左端连续数（右端同理）考虑两种情况：

不可跨区间，为左区间最大左端连续数
可以跨区间（左区间均为同一个数），那么为左区间最大左端连续数与右区间最大左端连续数之和

标记优先级推平大于翻转。注意当前区间如果已经存在一个推平标记，那么下传翻转标记时就需要把推平标记取反。推平后相应数字的最大连续数均设置成区间长度、另一个数字的最大连续数设为，此时的区间的和就是该区间的长度减去先前记录的区间和。

区间开方+区间和

例题：GSS4 - Can you answer these queries IV

题目难度：提高+/省选-

维护变量：区间和、区间开方判别标记

由于平方根之和没有计算公式，但是考虑到像这样的大数据，在经过次开方后都会变成，而。因此把区间修改变为暴力单点修改，记录一下当前数开方后是否等于或，如果是则给它做一个标记、并向上更新标记。如果区间被标记，更改时则无需递归进去，简化了操作。

区间加+区间sin和

例题：P6327 区间加区间 sin 和

题目难度：提高+/省选-

维护变量：区间和、区间和、角度加法懒标记

根据正弦值的和角公式：，维护一个加法懒标记，在下传时使用和角公式一次性计算、同时维护和即可。

区间加+区间平均数+区间方差

例题：P1471 方差

题目难度：提高+/省选-

维护变量：区间平方和、区间和

方差公式：，展开化简得。因此维护平方和用于计算分数部分。进行区间加时，维护平方和有这个公式：。按照公式维护即可。

基础数据结构 线段树

前言

线段树的建树

线段树的节点更新

线段树的查询操作

线段树的修改操作

一些细节

一句话，让评测结果从 RE 到 AC

标记置零问题

常见应用及应对策略

最大子段和

区间推平+区间翻转+最大连续数（01串）

区间开方+区间和

区间加+区间sin和

区间加+区间平均数+区间方差

基础数据结构线段树