数据结构学习笔记

wusixuan · 2025-01-20 10:34:05 · 算法·理论

从线段树开始。

线段树（Segment tree）是一种用于存储区间信息的二叉树数据结构，主要被用于高效的处理查询和修改操作。它具有以下特点：

• 其为一棵满二叉树，每个结点都对应着一段区间，上维护着对应区间的属性。属性可以自定义，但是必须要全面，以便合并子结点、修改和查询时使用。

• 线段树的核心是递归地将区间分为两部分（左右子区间），构建一个满二叉树，叶子结点表示最小的子区间（通常是单个元素）。

• 可在 O(\log n) 时间内，完成基于一个序列的单点、区间查询和单点、区间修改。如果不需要下文所需的 lazytag 的话，只需满足维护操作的结合律；否则，必须满足 lazytag 和 value 运算各自的结合律和之间相互对于对方满足分配律。易错地，操作不需要满足交换律也可以维护，例如赋值（显然 a = b 和 b = a 是完全不同的，但是利用 lazytag 维护区间赋值是一个很典型的例子）。如果上述条件不满足，则无法使用线段树，应该尝试使用其他方法。

• 倍增思想，分治类型的处理方法。即不能自己“承担”的操作就全部“推给”子树处理。

• 模板长，考试频率高。因此是重中之重。（CSP2024 都考了然后我没做出来）

• 优点：

  • 快速。可以在 O(\log n) 时间内完成修改和查询。

  • 灵活。可以通过不同的实现方式支持多种功能，例如区间求和、区间最大值、最小值等。

  • 支持在线。在线处理数据，可在不断修改和查询的场景中高效运行。

• 缺点：

  • 实现复杂。线段树的模板代码较复杂，但是在之后还会出现许多模板更加复杂的数据结构，需要做好准备。

  • 空间消耗较高。需要 O(4n) 的额外空间来存储整个树（对静态数组的扩展）。

  • *不适合稀疏数据（普通线段树）。**普通线段树对稀疏数据（元素间距离较远）效率较低，空间利用率不高，容易出现很长一大段都是单位元的情况，这时如果可以就一定要离散化。

  • 当然还可以动态开点线段树来处理稀疏数据，将在下文阐述。在离散化过于困难的时候，就可以使用动态开点。

• 空间复杂度：

  • 线段树需要 4n 的空间来存储结点信息，其中 4n 是基于最坏情况下的空间分配策略（通常不会完全用满，但是仍然需要有一个保底）。

  • 如果使用了 lazytag，则需要额外的 4n 空间。

  • 注意，这里的 4n 是一个粗略计算。实际上我们需要得出 n 最大时，最小的 \ge n 的 2 的整数次幂 sz，此时需要 2sz 的空间。

    • 因为 sz \le 2n，所以空间可以开 4n。

抽象代数（abstract algebra）

一个数学的分支，主要研究代数系统（集合与其中元素的运算及其规律）。

运算的规律有交换律、结合律、分配律等。类似小学学习的加法、乘法交换律、结合律及乘法分配律，满足交换律指交换运算操作式子的两边与原式等价，满足结合律指交换操作的元素顺序与原式等价。

正所谓上文提到，是否满足分配律也很重要。但是这需要两种基于集合 S 的运算（分别是 value 的运算和 lazytag 的运算），设为运算 + 和运算 *。

如果满足以下条件，则称*“ 对于 + 满足分配律”**（假设存在兼容两个操作的元素 x, y, z）：

• x * (y+z) = (x*y) + (x*z).
• (y+z) * x = (y*x) + (z*x).

称“+ 对于 * 满足分配律”须满足的要求同理。不过注意，当相互都满足分配律时，才满足使用 lazytag 的条件。

为什么一定要满足分配律呢？因为本应该直接对于每一个叶结点单独做修改，但是使用了 lazytag，就相当于将所有元素拼成一个区间后再整体应用 tag 修改从而达到不需要逐个修改也可以得到正确答案。

单位元（identity element）

单位元同样在线段树中很重要，因为线段树是一棵满二叉树，因此可能存在多余的空间，此时这些空间的属性就为单位元。

另外，单位元在查询时可作为计数器初值。

定义：对于运算 ，若 a ie = ie a = a，则称 ie 为 运算的单位元。

下表给出一些常见运算的单位元：

赋值的单位元可以为一个题目中不可能出现的属性。

1.线段树基础（支持单点修改）

主要思路

构建线段树

线段树每个结点都会存储一个属性。在操作开始前先会给每个结点一个初始值，叫做构建线段树。

满二叉树规模不一定是开始给出数组（用来赋初始值的）的规模 n，而是大于等于 n 的二次幂数 sz。sz 很容易得到，将在模板中讲解。

核心思想比较容易：递归每一个结点，初始化它的初始值。

因此，可以考虑从根结点开始递归左右儿子。到叶结点时记录并返回（注意，多出来的点属性设为所维护操作的单位元）。当一个点左右儿子都遍历之后，把两个儿子的属性合并即可。

假设合并两个儿子的时间复杂度为 O(1)，则构建线段树的时间复杂度为 O(sz) \approx O(n)。

修改部分

只寻找一个点，很容易想到二分搜索的思想。

因此，从根结点开始比较需要修改的点在左或右区间，递归到该区间，到单点上时修改一下，然后一路回退更新即可。

因为满二叉树的层数为 O(\log sz) \approx O(\log n)，则时间复杂度为 O(\log n)。

查询部分

将区间分割为好几个线段树结点上的区间加起来，答案也就是这几个区间属性的合并。

至于如何分成几个区间，可以在递归时保留着查询区间的左右端点。有三种情况：

• 查询区间包含了这个区间，直接返回答案。

• 查询区间与该区间没有联系，返回单位元。

• 查询区间与该区间有交集，则将分区间的任务传给子结点，向下递归。最终在返回时合并两个子结点的答案，默认时间复杂度为 O(1)。

根据直观感受，时间复杂度最坏可能会遍历所有的结点，也就是 O(n)，是无法达到预期的。接下来，证明最多只会关联到 O(\log sz) 个结点。

考虑同一层，所要查询的区间很显然会涉及到一串连续的本层区间，然而除了首尾两个区间可能需要递归以外，中间的区间一定是要么遍历到就返回答案要么在祖先就返回了，不可能产生递归。

因此，每一层最多只有 2 \times 2 = 4 个区间需要考虑是否在区间中。

因为 4 是一个很小的常数，可以忽略不计。因此，时间复杂度也为 O(\log n)。但是，这里的 “4” 也是导致线段树常数巨大的主要原因。

模板详解

模板采用封装形式。

线段树这里使用 node[] 一个数组维护，也可用 vector 但是较慢。

因为是满二叉树，第一步是先要计算出满二叉树的规模，设为 sz。而输入数据为 a，规模是 n。并先初始化单位元，以后要使用。

前置部分：

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define mid ((l + r) >> 1)

ls(x) 是 x 的左儿子编号，使用二叉树的存储方式，x 的左儿子编号为 x << 1。

rs(x) 是 x 的右儿子编号，使用二叉树的存储方式，x 的右儿子编号为 x << 1 | 1。

mid 是指一个结点代表的 [l,r] 区间的中间端点，在以后的分治模块有用，可分为几乎等长的 [l,mid] & [mid+1,r] 两个区间。

因为模板需要使用的左儿子、右儿子、分半分治较多，因此使用三个函数简化。

构建线段树

由于定义的结构体 Segtree 为类型，而在语言中有 int(x) 的用法，故如法炮制，在结构体中定义构造函数，格式如下：

Segtree(vector<int> &a){}//真正的构造函数。因为 a 可能规模巨大，可以传指针
Segtree(){}//空函数，无实际意义，不加会 CE

在构造函数中，首先要算出 sz 的具体值。之后可以执行 build() 函数。

void build(int nw, int l, int r){//记录目前的编号，以及对应的区间。
    if(l == r - 1) {//如果递归到叶结点点上了，直接返回。注意区间左闭右开
        seg[nw] = (l <= n) ? a[n - 1] : 0;//为叶结点赋初值。a 是 vector，从 0 开始。易错点：还要特判是否存在对应的数组值，若没有则设为单位元
        return ;
    }
    build(ls(nw), l, mid);//左子树递归
    build(rs(nw), mid, r);//右子树递归
    seg[nw] = seg[ls(nw)] + seg[rs(nw)];//将左右子树的属性合并
}

注意，此时的“递归”不可以称为“分治”，因为“分治”是通过划分问题而提高效率的手法，但线段树的相关操作显然不会因为划分问题而提高效率。只是一种程序的实现方式。 因为会遍历整棵树，因此 build 函数的复杂度为 O(2sz-1)。

不要忘记在主函数内执行 st = segtree()，st 是已经定义过的 segtree 类型。

查询部分

segtree qry(int nw, int l, int r, int ql, int qr){//目前所在结点，该结点对应的区间，需要查询的区间
    if(ql <= l && r <= qr) 
        return seg[nw];
    if(qr <= l || ql >= r)
        return ie;//单位元
    return qry(ls(nw), l, mid, ql, qr) + qry(rs(nw), mid, r, ql, qr);//直接搜左右结点
}

修改部分

void upd(int nw, int l, int r, int pos, int val){
    if(l == r) {//单点修改在叶结点结束
        //设此时需要进行的操作为 +，此时 + 操作就是更新操作而不是加法
        seg[nw] = seg[nw] + val;
        return ;
    }
    if(pos <= mid) 
        upd(ls(nw), l, mid, pos, val);//否则二分查找
    if(mid < pos) 
        upd(rs(nw), mid, r, pos, val);
    seg[nw] = seg[ls(nw)] + seg[rs(nw)];//将左右子树的属性合并
}

完整代码

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define mid ((l + r) >> 1)

struct Segtree {
    long long seg[N * 4], sz;
    int ie;
    void build(int nw, int l, int r) {
        if (l == r - 1) {
            seg[nw] = (l <= n) ? a[n - 1] : 0;
            return ;
        }
        build(ls(nw), l, mid);
        build(rs(nw), mid, r);
        seg[nw] = seg[ls(nw)] + seg[rs(nw)];
    }
    Segtree() {
        for (sz = 1; sz < n; sz *= 2);
        build(1, 1, sz);
    }
    Segtree() {};
    Segtree qry(int nw, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr)
            return seg[nw];
        if (qr <= l || ql >= r)
            return ie;
        return qry(ls(nw), l, mid, ql, qr) + qry(rs(nw), mid, r, ql, qr);
    }
    void upd(int nw, int l, int r, int pos, int val) {
        if (l == r) {
            seg[nw] = seg[nw] + val;
            return ;
        }
        if (pos <= mid)
            upd(ls(nw), l, mid, pos, val);
        if (mid < pos)
            upd(rs(nw), mid, r, pos, val);
        seg[now] = seg[ls(nw)] + seg[rs(nw)];
    }
}

方法练习

T227981 线段树 区间和

线段树的模板题。线段树维护区间和即可。

T227984 线段树 最小值个数

线段树维护最小值和最小值个数。合并时先比较两个最小值，合并出来的最小值就是两个值中间的最小值，最小值个数可以分类讨论。

T227985 线段树 最大子段和

线段树维护左边最长连续、右边最长连续、最大子段和和区间和即可。

2.lazytag（支持区间修改）

主要思路

lazytag 与普通线段树的唯一区别就是支持了区间修改。

区间修改显然不可以每个点进行单点修改，因为这样就至多会产生 O(nq) 次，这显然不是我们所期望的，考虑优化。

这时有一个想法，就是可以修改不全部落实到叶结点上，而是去修改较高的区间的属性（前提是这个较高的区间一定包含在修改区间内，且为线段树的一个结点）。但是光修改上面的还不够（下面的怎么办呢？），因此可把所进行的修改存储在较高的结点，代替了存储在不高的上面（只需访问一个结点就相当于修改了下面的所有结点，很节省时间），可以在下面的结点被真正使用到时将修改准时传到下面的结点（然而这时访问这个结点时必须的，因为需要被使用。下传修改以其 O(1) 的优秀复杂度没有算进函数内，则使用这种想法可以节省很多时间而只有很小的“副作用”）。这种所谓的“老师不检查作业，我就一笔不动”的想法，正是懒标记的精髓。其中，懒标记正是存储修改的那个数组，在一开始应该作为其运算的单位元。

如何下传修改（懒标记）？

显然，下传修改（懒标记）的前提是修改（懒标记）存在，即懒标记不是其运算的单位元。懒标记的运算取决于如何对操作进行存储，例如“区间加”操作，懒标记的操作就为加。

既然是下传，就必须要牵扯到左右儿子结点。首先是关于修改（懒标记）的下传，将左右儿子的懒标记分别对此结点执行运算（根据前文，此运算必须满足结合律）；然后是关于 value（线段树属性）的下传，将此结点的 lazytag 通过懒标记和属性之间的运算（此运算存在当且仅当懒标记的运算、属性 value 之间的运算需要相互对于对方满足分配律）更新左右儿子结点的 value 即可。

最终一定要记得清空修改（懒标记）！否则可能会导致一个懒标记更新左右结点多次，导致错误。把修改（懒标记）变成没有懒标记时的值（具体问题具体分析）即可。

注意懒标记的操作其实有可能不存在单位元（只需符合抽象代数中“半群”的定义），例如赋值。但是为了使它不存在，需要假装有单位元（题目中的操作一定有一个值的上限和下限，因此使其“单位元”为一个不可能涉及到的数即可）。

正确性及复杂度证明

正确性证明

结论：一个叶结点，它的所有祖先恰是线段树中所有包含此位置的区间。

感性理解，此结论好像显然。因为叶结点的父亲由它和它的兄弟拼成，爷爷由父亲和父亲的兄弟拼成……以此类推，它的所有祖先都一定包含此位置；而除这些结点以外，其他区间都一定不会包含此位置。

这个结论启发：任何一个有操作没有处理的叶结点，它的修改一定可以在它的祖先中找到痕迹。因为区间修改的暴力做法本质上就是修改叶结点的属性，因此下传懒标记，就相当于把标记从祖先下传到了下面的结点，间接地修改了叶结点。即使最终懒标记可能没有传到叶结点，但如果是这样，传到叶结点似乎又没有什么作用（没有传到叶结点就说明叶结点没有被真正使用，而是在它的祖先就已经停止下传了，此时我们只需要它的祖先帮我们执行操作）。

因此可以证明，下传懒标记一定是可行的且正确的。

复杂度证明

请注意，这是关于区间的修改！

运用区间查询使用的结论：任何区间都能使用约 O(\log n) 个线段树结点（区间）拼成。

因为每一层最多两个点产生递归，下面一层最多有 4 个结点。常数忽略不计，上述结论成立。

因为下传懒标记的复杂度为 O(1)，可以不计。而使用结论，修改和查询的原本复杂度就是 O(\log n)，乘上下传懒标记的 O(1)，复杂度还是 O(\log n)，是预期的复杂度。

模板详解

存储进行修改的数组就是 lazytag 数组，简称 lazy[]。

为了实现下传操作，需要一个 pushdown 函数（为了避免重名，使用缩写 pd）。

void pd(int nw){
    if(lazy[now] != ie) { //如果懒标记存在
        //设此时需要进行的操作为 +，+ 操作就是更新懒标记操作而不是加法
        lazy[ls(nw)] = lazy[ls(nw)] + lazy[nw]; //更新左儿子的懒标记
        lazy[rs(nw)] = lazy[rs(nw)] + lazy[nw]; //更新右儿子的懒标记

        //设此时需要进行的操作为 *，* 操作就是更新区间属性 value 操作而不是乘法
        seg[ls(nw)] = seg[ls(nw)] * lazy[nw]; //更新左儿子的区间属性
        seg[rs(nw)] = seg[rs(nw)] * lazy[nw]; //更新右儿子的区间属性
        //由于懒标记没有更新子树所有结点，所以此时 pushup 无法得到正确的区间信息，于是结合懒标记的值对儿子代表的区间信息进行计算
        lazy[nw] = ie; //将懒标记变为不存在
    }
}//将懒标记继续推到左右儿子

这样就完成了下传操作，前文提到，Pd 函数需要在修改函数和查询函数递归前调用，因为都需要使用它进行下传。

有时候的 pushdown 函数过于繁杂，这时可以采取 https://www.luogu.com.cn/article/7dnx35wf 的思路，再次新开一个函数进行懒标记的修改区间即可。

前文提到，注意在 Build() 函数中将懒标记初始化成其操作的单位元。

3.标记永久化

有时候懒标记可以一直保存在结点上，而不下传。前提是维护操作必须也要满足交换律，因为下传懒标记是克服不满足交换律的方法，不下传就必须遵循交换律。

此方法用于将某操作撤销，例如扫描线。如果懒标记下传就找不到了，而不下传就可以直接删除懒标记，并重置属性。

扫描线问题： 给出一些图形，要求其的一些性质的交（人话：就是要求解面积并或周长并，以及其他的一些东西）。这是我们就可以有一种朴素的做法，直接划分成若干个小的矩阵，并一一求解其的属性。

显然这样不用考虑重复计算的问题。

假设我们需要计算一些矩形的面积交，类似这样的一些图形：

然后进行扫描线之后变成这样：

答案就是各种颜色的面积之和，而我们对于每一种颜色（一个矩形）都可以用一遍矩形面积公式。难点在于得到每一个矩形的长（不妨设是竖着的边）和宽（不妨设是横着的边）。

宽很容易得到，只需要处理出每一个初始给出的矩形的宽（不妨设是矩形竖着的边），然后排序。相邻的坐标差就是各种颜色的矩形的宽。

但是长就需要维护：每一个坐标到底有没有出现。

不妨划分一下纵坐标，并使用线段树维护划分出来每一个区间是否出现。

然后扫描线从左往右扫，遇到一个初始给出矩形的更左边的宽则将对应的区间的出现次数加一，遇到一个初始给出矩形的更由边的宽则将对应的区间的出现次数减一。

发现这样不可以进行下传，而操作满足交换律，于是考虑标记永久化。

使用线段树的 val 维护出现的非 0 值个数， tag 维护区间内每一个数的统一出现次数（不下传了）。

如果发现 tag > 0，则 val = 区间长度。

如果发现 tag = 0，则 val = 两个儿子的 val 值之和。

顺带维护 val 和 tag 即可。

发现可能需要离散化，于是需要使用一个前缀和来处理对应区间的长的长度。

实际上有一些问题，可以通过转化得到一些矩形，并使用扫描线求解。

4.树链剖分

树链剖分是一种数据结构，而剖分出链的过程才是算法（以前讲错了），即将一棵规模为 n 的树（不要求二叉树）剖分为若干条链或单点从而解决问题，就是形如在一棵树上、对一点之下子树和两点之间路径的属性修改。本质上是一种分组的方法。

（一次）路径维护的时间复杂度为 O(\log ^ 2 n)。

（一次）子树维护的时间复杂度为 O(\log n)。

优点包括：

• ‌高效处理树上路径问题‌：树链剖分通过将树分解成若干条链，使得树上路径问题转化为区间问题，从而可以利用线段树等数据结构高效处理。

• ‌支持动态维护信息：树链剖分支持修改操作，可以动态维护树上的信息。

• 常数较小：看实现的方法。

缺点包括：

• 适用场景有限：它只能处理形态不变的树。如果树的形态在过程中发生了变化，则就需要重新剖分，造成时间开销。

• ‌实现复杂‌：树链剖分本身的两个 dfs 不算复杂，但是如果加上了线段树、修改和查询函数，代码很有可能超过 200 行。

• 占用空间较大：树链剖分光是两个 dfs 就需要 6 至 8 个数组，因此光计算空间复杂度是不够的，还要留意这些常数。

先来探讨一下如何分组。

至于如何分组，是一个问题：

• 如果组员不多，则组内结构简单，可以整组快速修改。

• 如果组数不多，每次操作所需整组处理次数较小。

存在一种均衡的方式即为组数和组员都是 \sqrt(n)，即分块的分组方式。因为分块就是整块处理 + 不完整块暴力，所以单次操作复杂度为组数 + 组员数 \approx \sqrt(n)。对于分块来说，这种划分方式是最优的。

与其不同，树链剖分的分组就是使组数为大约 \log n 个（不是指的整棵树分成组的个数，一个点不是很可能经过整棵树的全部点。这里是将点到根结点上的路径的组数变成了 O(log n)），更加偏向分组的数量而不是组员数，那是因为组员数（链上的结点）的数量并不重要：在之后会使用线段树进行快速维护。而一般情况下每一个结点到根结点的路径上不可能经过所有的链，而是有限的链。这些链的数量就是 O(\log n) 个。即使不是一个结点到根结点，两点之间的路径所经过的链也最多只有 O(2 \times \log n) \approx O(\log n) 个。

这种通过斟酌组员数和组数来调整算法复杂度，并最终得出一种最优的划分方法的思想，叫做平衡规划思想。

这个思想在很多算法都会体现出来，例如分块、莫队、根号分治。

树链剖分的分组方式与分块、莫对的分组方式的不同告诉我们，算法分组方式并不是一成不变的。只有灵活调整方案，才能快速地解决各种问题。

剖分思路（当前仅介绍剖分部分，后面的维护还有很多）

树链剖分一般都是重链剖分，在此处讲解。当然还有其他的剖分方式，例如高低剖分或长链剖分，但是不常考。

首先需要对每一个点找到重儿子（指向子树规模最大的儿子），显然一开始需要使用树形 dp 计算出每一个点的子树大小 sz。

对于一个点 u，若它的儿子 s 的子树规模在 u 的所有儿子中最大，则称 s 为 u 的重儿子，即 son_u = s。请注意，如果一点有多个儿子的规模一样，任意选取一个即可。

此外，轻儿子是指不是一个点的重儿子的其他所有儿子（不是与这个点有连结的父亲）。

重链就是每一个点向其重儿子连边，依次连结成的长链，这样就会变成一个个链。如果一个点不是其父亲的重子，则就自己作为一条链的顶端向下延生。如果一个点既不是父亲的重儿子，自己也没有重儿子，那么这个点就单点成链。

也许你已经猜到了——一条链就是一组，链上面的点是这组的组员。于是，分组完毕。组内的结构也确实比树简单多了。

我们的目标就是能够对一条链上的点进行整组处理，根据上文，我们也一定希望一条路径上涉及到的链也很有限。

整组处理：可以对于每一个结点，记录一下所在链上的最高点（top）值，而希望每一个点都可以直接跳到所在链最高点上（称为“跳链”），从而修改最高点变成修改整组。显然，为了在 O(n) 内时间完成，一定是从上到下传递。

于是就出现了一个矛盾的点：遍历并计算出重儿子可以在同一个 dfs 中完成，但是计算出 top 就不能了。因为遍历并计算子树规模是先一路搜到叶结点，然后返回；而并不知道自己是不是自己父亲的重儿子（如果不是，则 top 显然就是自己；否则一定是祖先），就需要再次下去一趟。因此，树链剖分的实现中一种运用了两次深搜。

然而为了满足上文，需要使得跳链次数尽量少。

于是需要解答这个问题：从 u 结点到根，至多需要多少次向上跳？答案是 \log n 的级别。

可以发现向上跳一共两种类型：跳到 top 或 top 跳到父结点。可以发现，两种类型的次数几乎相同，因为两种类型的操作一定是交替进行的，正确性显然。因此，我们只需要证明其中一个操作的次数为 \log n 量级，就可以得到问题的答案。

不妨证明第二种操作的时间复杂度：

假设 top 的父结点为 f 点，其重儿子（一定不是 top）的编号为 son。因为 son 作为重儿子而 top 不是重儿子，显然 sz_{top} \leq sz_{son}。因为 sz_{top} + sz_{fon} \leq sz_f，结合上文的公式，可以得知 2 \times sz_{top} \leq sz_f。解读一下式子，则从 top 跳到父结点，规模至少乘以了 2。

而根结点的子树规模为 n，也只能负担地其 \log n 次除 2，也就是最多跳 \log n 次，就证明了答案的确为 \log n。

最终，说一下树链剖分与并查集的区别：两者都是使用了分组的方法，在分组上可以算是相像。但是树链剖分是利用分组去精巧的解决各种问题，而并查集是完成分组操作的实现方式。

模板讲解（当前仅介绍剖分部分，后面的维护还有很多）

模板采用封装。

前置部分

const int N = 500010;
int n, m, s;
vector<int> v[N];
int d[N], sz[N], fa[N];
int tp[N];

N 表示数组大小，为了后面不出现太多重复的数字影响美观，所以设置一个常量。

n, m, s 分别表示结点的数量、边的数量以及默认的根。

v 是邻接表，存储树的形状。

d 表示结点的深度，sz 表示结点的子树规模，fa 表示结点的父结点。

tp 表示 top，即一条链的顶端。

第一次 dfs

我们假设每一个点的第一个子结点就是其重儿子，然后再让其他的每一个儿子来进行挑战，如果挑战成功就交换并取代它。

int dfs1(int x, int pre, int dep) {//目前的结点，父亲结点，结点深度
    fa[x] = pre, d[x] = dep, sz[x] = 1;//存储父亲结点和结点深度，并初始化子树大小为 1
    for (auto i : v[x])//遍历每一个儿子
        if (i != pre)//如果自己儿子非自己父亲（因为建树时连的是双向边）
            sz[x] += dfs1(i, x, dep + 1);//更新子树大小
    for (int i = 1; i < (int)v[x].size(); i++)//枚举其他的每一个儿子
        if (v[x][i] != pre && (v[x][0] == pre || sz[v[x][i]] > sz[v[x][0]]))//翻译过长，将在下文讲解。
            swap(v[x][i], v[x][0]);//如果挑战成功就取而代之
    return sz[x];
}

dfs1() 函数返回结果是子树大小。

第 7 行的含义是：第一个条件，这个儿子必须不是这个点的父亲；第二个条件，目前待定的“重儿子”是该点的父亲（这个待定的点就一定不是重儿子，一定要把它换下来！）则条件成立，这个儿子的子树规模比待定的重儿子的子树规模还大（而且这个待定的点不是父亲，因此这个儿子更有理由成为重儿子）也条件成立。只有两个条件都成立才算挑战成功，就交换并且取而代之。

复杂度就是每一个点都遍历一下其子结点，即为 O(n)。

第二次 dfs

这次主要是求出 top 数组 tp[]。

void dfs2(int x, int top) {
    tp[x] = top;//先将最高点存入
    for (auto i : v[x])//遍历自己的所有儿子
        if (i != fa[x]) {//是真正的儿子而不是与此结点有联系的父亲
            if (i == v[x][0])//如果是重儿子
                dfs2(i, top);//这条链将会延续下去，top 值不变
            else//如果是轻儿子
                dfs2(i, i);//新开一条以这个儿子为最高点的链
        }
}

这仅仅只是求出 top 数组，以后在与线段树的应用中还会在这两个 dfs 中顺带求出更多东西。

注意，auto i : v[x] 的用法只有在 C++14 及更高版本中才可以使用，而 auto [a,b,···] : v[x] 只有在 C++17 及更高版本中使用。如果在只有 C++14 的环境中使用了后者，后果将不堪设想。

upd：C++11 就可以使用了，C++14 是笔误。因此可以在绝大部分竞赛中使用。

配套操作

你认为树链剖分仅仅只是划分个链、找个点吗？错误的。前文提到树链剖分是利用分组从而使得更容易整体修改和更少次数的整体修改，单单剖分一下树太没有含金量了。

树链剖分常常被用于求 lca（树上最近公共祖先），以及与两点路径有关的所有操作和查询（使用线段树）。

1.求 lca

剖分树的过程不在阐述，仅展示求 lca 相关内容。

思路

设要求 lca 的点为 x, y。

显然，如果 x, y 在同一条链上，则两点之间的 lca 显然就是深度最浅的那个点。

否则应用求 lca 标准思路的向上跳。不过这次不是跳到第 2 的整数次幂个祖先，而是在链上跳跃。这次也不是分成两个阶段进行跳跃，而是链的顶部结点深度浅的跳到最高点，跳完之后再深度浅的跳到最高点……

upd：应该是链的顶部结点。这是一个很容易搞错以及搞混的地方。

只有最终跳到了同一条链上才会结束，两点之间的 lca 显然就是深度最浅的那个点。

因为任意两点之间一定存在 lca，因此最终一定会跳到同一条链上。因此正确性得证。

因为使用上文的结论，从 u 结点到根，至多需要 \log n 次向上跳。即使两个点交替跳，也无法改变 O(\log n) 的时间复杂度，与原本的方法没有很大的区别。因此时间复杂度正确。

代码

int lca(int x, int y) {
    if (tp[x] == tp[y])//如果两点在同一条链上
        return d[x] < d[y] ? x : y;//深度浅的为 lca
    return d[tp[x]] < d[tp[y]] ? lca(x, p[tp[y]]) : lca(y, p[tp[x]]);//否则比较深度更浅的点（注意是顶部结点！！！）向上跳
}

使用递归的方式，比 while 的循环简洁多了，也更加好写好调。

2.与线段树解决一些操作问题

思路

前面说过树链剖分是利用链来分组，而且还要实现整组修改。我们不如赋予每一个结点一个值，便于修改。

如果一条链上的值是散乱的，则就说明我们需要快速维护一些散乱的无规律的对应位置修改，而目前并没有足够快的手段。

如果一条链的值是连续的话，则就说明我们需要快速维护一段区间的对应位置，那么就会浮现出一车的维护方法：线段树，树状数组……

因此，我们定义一个叫做“先重子深搜序”，也就是当一个点有很多儿子时就先搜索重子再搜索轻子。

因为一条链上面相邻的两个点，低的一定是高的重儿子，所以这样深搜就可以保证每一条链上搜索的顺序都为连续的。

此时这个先重子深搜序的名字，我们设置成 dfn[]。

顺带说一下，“先重子深搜序”得到的结点值对于每一个子树来说也是一个连续的区间。因此，树链剖分还可以维护子树操作。

如何维护路径操作呢？

我们假设一棵树上需要在执行操作的路径有 u,v 两点，其 lca 为 x。

则我们需要找出 u \to x 与 v \to x 的路径上的所有的点，并对其进行修改、查询。

这时候一条条链就派上用场了。根据上文的复杂度推导，可以知道一路上经过的链为 O(\log n) 量级，包括不完整的链。

每一条链因为上面的结点编号连续，所以可以使用线段树区间修改。不使用树状数组的原因是操作过于纷繁而树状数组有很大的局限性。

乍一看，经过的链为 O(\log n) 个，每一条链区间修改的最坏复杂度也是 O(\log n)。

那么，一次操作的复杂度就是 O(\log ^ 2 n)。

这个复杂度比 O(\log n) 多了一只 log，需要谨慎使用。例如 n = 10 ^ 6 时一次操作大约要运算 400 次。

到现在，我们还有一个问题：如何确定一条链（子链）在线段树中的对应的区间？

众所周知，一条链（子链）对应的是一个连续区间。而根据“先重子深搜序”的原理，这条链（子链）的搜索顺序一定是自上而下的，对应区间的自左向右。

则这条链（子链）的顶部点的编号是区间的左端点，链（子链）的底部点的编号是区间的右端点。这样就可以找出区间并进行修改。

既然都有链的区间了，那么就一定有子树对应的区间。

子树的根结点一定是最先访问到的，其编号就是区间的左端点。

而这时就会有一种呼之欲出的方式：我可以记录区间编号最大值，就是区间的右端点。可以使用类似树形 dp 来实现。

这是一种不错的思路，但是不妨转变一下方向：子树的规模我们就已经在剖分时得出来了。

而子树的每一个结点都是被访问到了一次，因此子树的规模恰好就是区间的长度。

结合左端点和区间长度，可以轻松算出右端点。从而对整个区间进行维护。

因为我们不止需要深搜序编号对应的结点（dfn[]），还需要结点对应的深搜序编号，所以还需要有一个数组 rev[]，在 dfs2() 处理即可。

模板代码

剖分部分模板仅在 dfs2() 部分产生了不同。

新增数组：

• dfn[i] 表示第 i 个使用“先重子深搜序”搜到的结点。

• rev[i] 表示第 i 个结点是第 rev[i] 个使用“先重子深搜序”搜到的结点。

int dfn[N], rev[N], cnt = 0;//前面两个数组如上。cnt 记录目前的结点是第 `cnt` 个使用“先重子深搜序”搜到的结点
void dfs2(int x, int top) {
    tp[x] = top;//先将最高点存入
    dfn[++cnt] = x, rev[x] = cnt;//更新
    for (auto i : v[x])//遍历自己的所有儿子
        if (i != fa[x]) {//是真正的儿子而不是与此结点有联系的父亲
            if (i == v[x][0])//如果是重儿子
                dfs2(i, top);//这条链将会延续下去，top 值不变
            else//如果是轻儿子
                dfs2(i, i);//新开一条以这个儿子为最高点的链
        }
}

//线段树模板

一些练习

P3384 【模板】重链剖分/树链剖分

题目要求我们维护路径和子树上的点权和。

子树貌似很好维护，直接按照上述方法计算区间即可。但是一条路径所对应的区间不一定是连续的区间，好像不好维护。

然后我们想到：路径是由一条条链（子链）组成的，而链（子链）又对应着一段区间！于是把路径分割成一条条链即可。

不难想到直接运用现成的办法：在求 lca 的过程中维护路径！而且路径又恰好与 lca 有关，在跳链的过程中顺带获取区间进行维护即可。

而一条链的区间获取方式已经在上文讲述。

//modifies
void routeupd(int x, int y, int val) {//x,y表示路径的两端，val表示修改的值
    if (tp[x] == tp[y]) {//两点在同一条链上，则一定有一个点是 lca
        if (d[x] < d[y])
            st.modify(1, 1, n, rev[x], rev[y], val);
        else
            st.modify(1, 1, n, rev[y], rev[x], val);
        return ;
    }
    if (d[tp[x]] < d[tp[y]]) { //y up
        st.modify(1, 1, n, rev[tp[y]], rev[y], val);//跳链
        routeupd(x, fa[tp[y]], val);
    } else { //x up
        st.modify(1, 1, n, rev[tp[x]], rev[x], val);//跳链
        routeupd(y, fa[tp[x]], val);//不用跳到父亲上去，是因为父亲也会在下一次跳链的过程中被维护
    }
}

void treeupd(int x, int val) {
    int l = rev[x], r = rev[x] + sz[x] - 1;//获取区间
    st.modify(1, 1, n, l, r, val);
}

//queries
int routeqry(int x, int y, int ans) {//x,y表示路径，ans是顺带记录的答案
    if (tp[x] == tp[y]) {
        if (d[x] < d[y])
            ans = (ans + st.query(1, 1, n, rev[x], rev[y])) % p;
        else
            ans = (ans + st.query(1, 1, n, rev[y], rev[x])) % p;
        return ans % p;
    }
    if (d[tp[x]] < d[tp[y]]) { //y up
        ans = (ans + st.query(1, 1, n, rev[tp[y]], rev[y])) % p;
        return routeqry(x, fa[tp[y]], ans);
    } else { //x up
        ans = (ans + st.query(1, 1, n, rev[tp[x]], rev[x])) % p;
        return routeqry(y, fa[tp[x]], ans);
    }
}

int treeqry(int x) {
    int l = rev[x], r = rev[x] + sz[x] - 1;
    return st.query(1, 1, n, l, r) % p;
}

P7735 [NOI2021] 轻重边

考虑到直接维护轻边还是重边并不方便，因此考虑借助某些东西来自动判断是轻边还是重边。

这时有一个方法：维护点权。如果一条边两点点权相同即为重边，不同即为轻边。

显然一开始 n 个点的点权必须要两两不同（即为 1 \to n），全部都是轻边。

在每一条路径的修改时，将途径点权全部修改为同样的新的点权就可以完美契合题目中需要维护的操作。

查询时需要线段树维护区间相同连续子段和即可。

5.二维线段树

为什么是二维“线段树”啊？

为了节省字数，“普通线段树”在这里将被写成“线段树”。

顾名思义，二维线段树就是线段树加上一维的版本。即线段树维护的是线段上的区间，则二维线段树维护的是矩阵中的矩阵。（那么三维线段树维护的就是长方体中的长方体？）

注意二维线段树只能维护矩阵，而不是菱形或圆形（这些图形上很有可能直接穿过了某些单位正方形，而非包含，因此无法维护）。

upd:拓展一下，上面这句话不一定正确。

菱形可以通过旋转坐标系来实现，而圆形又可以采用极坐标系来实现。这些都是计算几何的相关问题了。

二维线段树有两种方法。一是在线段树每个结点的两（2 = 2 ^ 1）个子结点变为 4（4 = 2 ^ 2） 个（称为四叉线段树），二是在树套树（即外层线段树的每个结点都是一个内层线段树）上维护。

注意二维线段树的常数可能很大，且代码较为复杂。

四叉线段树

这是一种最自然、最易于想到的方法，不过其效率并不能让我们满意。

因为线段树是使用的二分区间（一维），则二维线段树不就是四分矩阵？！

因此我们可以将二维线段树看成四叉树，其查询和修改与线段树一样的原理。

接下来我们分析它的复杂度。

不管 build() 函数，光是维护的复杂度就让我们难以接受。

查询和修改除了分区间（分矩阵）其他的操作可以设为 O(1)，只需要考虑将查询矩阵分为若干个小矩阵的复杂度即可。

因为线段树我们就是运用一层层产生递归的点数来分析复杂度，故如法炮制。

先看一下这张图：黑色矩阵是线段树维护的，红色矩阵是查询的。

我们假设二维线段树在某一层将矩形分为的小矩形，长有 x 个，宽有 y 个，容易发现不管 x, y 取什么值，其乘积都必须相等。

如上图，我们可以发现这次产生递归的点数（即与查询矩阵有关系又不是完全包含的点数）竟然达到了 O(x + y) 个！

因此，最坏情况下，每一层最多有 O(x + y) 个点向下递归了。