线段树讲解（小进阶）

目录

前言

一、线段树知识回顾

线段树区间加减

区间修改维护：

区间修改的操作：

区间修改update：

线段树的区间查询

区间查询：

区间查询的操作：

递归查询过程：

区间查询query：

代码：

二、线段树的区间修改---乘上一个数’x'

build

区间修改

update

mulpr_update

push_up

代码：

push_down

左：

右：

代码：

区间查询query

代码：

三、例题

例题：P3373 【模板】线段树 2 - 洛谷

​编辑

完整代码：

总结

---

前言

本篇文章主要是根据P3373 【模板】线段树 2 - 洛谷对线段树进行进一步的讲解，因为比较笨拙加上画图耗时大，没有图文搭配讲解，只有纯粹的文字讲解，但是也是非常清楚的，很容易就能理解

---

一、线段树知识回顾

我们在进一步学习前，先来看一下前置知识

开一个build函数建树，具体操作如下：

1.定义数组：首先，需要定义一个大小为 4n 的数组，其中 n 是线段树的叶子节点数量。这个数组将用于存储线段树的节点信息。

2.构建线段树：一般将线段树按照完全二叉树的形式存储在数组中。假设根节点在数组中的索引是 1，那么对于节点 i，其左子节点为 2i，右子节点为 2i + 1。

3.存储节点信息：每个节点需要保存代表的区间范围和相应的信息，比如区间的最大值、最小值、和等等。在数组中，可以按照某种顺序依次存储这些信息，以便后续的查询和更新操作。

4.建立线段树：通过递归或迭代的方式构建线段树。一般会从叶子节点开始向上构建，通过合并子节点的信息得到父节点的信息，直至构建完整的线段树。

5.查询和更新：通过线段树的结构和数组存储，可以实现高效的区间查询和更新操作。比如，对于查询一个区间的最大值，可以通过递归向下查询到包含目标区间的节点，并根据存储的信息计算出结果。

6.记得注意边界情况：在实现线段树时，需要考虑树的边界情况，比如树的根节点索引是 1，叶子节点索引从 n+1 开始等，以确保正确地访问和操作节点。

// 建树函数
void build(LL l, LL r, LL fa) {if (l == r) { // 如果区间只有一个元素t[fa] = a[l] % m; // 直接赋值return;}LL mid = (l + r) >> 1; // 计算中间节点build(l, mid, fa << 1); // 递归构建左子树build(mid + 1, r, fa << 1 | 1); // 递归构建右子树push_up(fa); // 更新父节点
}

线段树区间加减

区间修改维护：

1.需要修改线段树中某个特定区间的值时，可以通过递归的方式向下更新区间。
2.如果要修改的区间与当前节点表示的区间没有交集，则无需修改该节点。
3.如果要修改的区间完全包含当前节点的区间，则直接更新当前节点的信息，并将修改操作下传给子节点。
4.如果要修改的区间与当前节点的区间部分相交，则需要先将当前节点的信息更新，然后将修改操作同时下传给左右子节点。

区间修改的操作：

1.区间修改的操作通常包括加法、减法、赋值等。
2.当需要对区间内的每个元素进行相同的修改时，可以利用线段树的特性进行高效操作。
3.在修改区间时，需要根据当前节点的区间范围、待修改区间和修改方式来确定如何操作当前节点和其子节点。

递归更新过程：

从线段树的根节点开始递归向下更新，直到找到包含待修改区间的叶子节点。
在递归过程中根据节点的区间范围和待修改区间的关系，决定如何更新节点的信息并向下传递修改操作。
       此外，对于区间操作，我们考虑引入一个名叫“ lazy tag ”（懒标记）的东西——之所以称其“lazy”，是因为原本区间修改需要通过先改变叶子节点的值，然后不断地向上递归修改祖先节点直至到达根节点，时间复杂度最高可以到达 O(nlogn) 的级别。但当我们引入了懒标记之后，区间更新的期望复杂度就降到了 O(logn) 的级别且甚至会更低。

因此，我们再弄一个tag数组，大小也是4*N

区间修改update：

void psuh_up(LL fa) {t[fa] = t[fa << 1] + t[fa << 1 | 1];//向上不断维护父节点
}
void push_down(LL l,LL r,LL fa) {LL mid = (l + r) >> 1;t[fa << 1] += tag[fa] * (mid - l + 1);tag[fa << 1] += tag[fa];t[fa << 1|1] += tag[fa] * (r-mid);tag[fa << 1|1] += tag[fa];tag[fa] = 0;// //每次将懒惰标识下放到两个儿子节点，自身置为0，以此不断向下传递 
}
void update(LL ql, LL qr, LL l, LL r, LL k, LL fa) {if (ql <= l && qr >= r) //如果区间被包含，直接返回该节点的懒惰标识{t[fa] +=k * (r - l + 1);tag[fa] += k;return;}LL mid = (l + r) >> 1;push_down(l, r, fa);//下放懒惰标识if (ql <= mid)update(ql, qr, l, mid,k, fa << 1);//朝左边下放if (qr > mid)update(ql, qr, mid + 1, r,k, fa << 1 | 1);//右边psuh_up(fa);//再将修改后的值向上返回，维护父节点
}

我们这一期会对update和push_down进行更改

线段树的区间查询

1. 区间查询：

   • 当需要查询线段树中某个特定区间的信息时，可以通过递归的方式向下查询区间。
   • 如果要查询的区间与当前节点表示的区间没有交集，则无需查询该节点，直接返回默认值（如0或无穷大）。
   • 如果要查询的区间完全包含当前节点的区间，则直接返回该节点存储的信息。
   • 如果要查询的区间与当前节点的区间部分相交，则需要同时查询左右子节点，并根据查询结果合并得到最终结果。

2. 区间查询的操作：

   • 区间查询的操作通常包括求和、求最大值、求最小值等。
   • 在查询区间时，需要根据当前节点的区间范围、待查询区间和查询方式来确定如何操作当前节点和其子节点。

3. 递归查询过程：

   • 从线段树的根节点开始递归向下查询，直到找到包含待查询区间的叶子节点。
   • 在递归过程中根据节点的区间范围和待查询区间的关系，决定如何查询节点的信息并向下传递查询操作。
   • 最终将所有查询结果合并得到最终的区间查询结果。

      通过以上方法，可以实现对线段树中特定区间的查询操作。线段树区间查询是线段树的一个重要功能，能够快速有效地获取区间内的信息，提高了区间查询的效率。

区间查询query：

LL query(LL ql, LL qr, LL l, LL r, LL fa) {LL ret = 0;if (ql <= l && qr >= r) 如果区间被包含，直接返回该节点的懒惰标识{return t[fa];}LL mid = (l + r) >> 1;push_down(l, r, fa);//没有被包含，下放任务if (ql <= mid)ret += query(ql, qr, l, mid, fa << 1);if (qr > mid)ret += query(ql, qr, mid + 1, r, fa << 1|1);//在查询范围的左区间和右区间的值相加并返回return ret;
}

代码：

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL n, m, t[N * 4], tag[N * 4], a[N];
void psuh_up(LL fa) {t[fa] = t[fa << 1] + t[fa << 1 | 1];//向上不断维护父节点
}
void push_down(LL l,LL r,LL fa) {LL mid = (l + r) >> 1;t[fa << 1] += tag[fa] * (mid - l + 1);tag[fa << 1] += tag[fa];t[fa << 1|1] += tag[fa] * (r-mid);tag[fa << 1|1] += tag[fa];tag[fa] = 0;// //每次将懒惰标识下放到两个儿子节点，自身置为0，以此不断向下传递 
}
LL query(LL ql, LL qr, LL l, LL r, LL fa) {LL ret = 0;if (ql <= l && qr >= r) 如果区间被包含，直接返回该节点的懒惰标识{return t[fa];}LL mid = (l + r) >> 1;push_down(l, r, fa);//没有被包含，下放任务if (ql <= mid)ret += query(ql, qr, l, mid, fa << 1);if (qr > mid)ret += query(ql, qr, mid + 1, r, fa << 1|1);//在查询范围的左区间和右区间的值相加并返回return ret;
}
void update(LL ql, LL qr, LL l, LL r, LL k, LL fa) {if (ql <= l && qr >= r) //如果区间被包含，更新懒惰标识并返回{t[fa] +=k * (r - l + 1);tag[fa] += k;return;}LL mid = (l + r) >> 1;push_down(l, r, fa);//下放懒惰标识if (ql <= mid)update(ql, qr, l, mid,k, fa << 1);//朝左边下放if (qr > mid)update(ql, qr, mid + 1, r,k, fa << 1 | 1);//右边psuh_up(fa);//再将修改后的值向上返回，维护父节点
}
void build(LL l, LL r, LL fa) {if (l == r) // //如果左右区间相同，那么必然是叶子节，只有叶子节点是被真实赋值的{t[fa] = a[l];return;}LL mid = (l + r) >> 1;build(l, mid, fa << 1);build(mid + 1, r, fa << 1 | 1);//使用二分来优化psuh_up(fa);//此处由于我们是要通过子节点来维护父节点，所以push_up的位置应当是在回溯时将子节点的值取和交给父节点
}
int main() {cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i];build(1, n, 1);while (m--) {int op; cin >> op;if (op == 1) {LL x, y, k; cin >> x >> y >> k;update(x, y, 1, n, k, 1);}else if(op==2){LL x, y;cin >> x >> y;cout << query(x, y, 1, n, 1) << endl;}}return 0;
}

二、线段树的区间修改---乘上一个数’x'

老样子，先看题目

根据题目意思先建树

build：

代码：

// 建树函数
void build(LL l, LL r, LL fa) {if (l == r) { // 如果区间只有一个元素t[fa] = a[l] % m; // 直接赋值return;}LL mid = (l + r) >> 1; // 计算中间节点build(l, mid, fa << 1); // 递归构建左子树build(mid + 1, r, fa << 1 | 1); // 递归构建右子树push_up(fa); // 更新父节点
}

因为题目增加了一个区间乘一个数，所以我们需要维护两个tag数组，tag1，tag2，大小都是n*4；

令tag1为区间乘一个数的数组，由于区间乘一个数，所以数组tag1全部初始化为1；

代码：

int main() {cin >> n >>q>> m;for (int i = 0; i <= N * 4; i++)tag1[i] = 1;for (int i = 1; i <= n; i++)cin >> a[i];build(1, n, 1);while (q--) {int op; cin >> op;if (op == 2) {LL x, y, k; cin >> x >> y >> k;update(x, y, 1, n, 1, k%m);}else if (op == 3) {LL x, y; cin >> x >> y;cout << query(x, y, 1, n, 1)%m  << endl;}else if (op == 1) {LL x, y, k; cin >> x >> y >> k;mulpr_update(x, y, 1, n, 1, k);}}return 0;
}

这个模去m是题目要求的，后面不会去详细讲，只会说tag数组如何维护以及query的一点改动；

区间修改

需要两个不同的update来维护区间加和区间乘

区间加就不多赘述了

update

// 更新函数
void update(LL ql, LL qr, LL l, LL r, LL fa, LL k) {if (ql <= l && qr >= r) { // 如果更新区间完全覆盖当前区间t[fa] = (t[fa] + (r - l + 1) * k) % m; // 更新当前节点的值tag2[fa] = (tag2[fa] + k) % m; // 更新加法标记return;}LL mid = (l + r) >> 1; // 计算中间节点push_down(l, r, fa); // 向下更新标记if (ql <= mid) // 如果更新区间在左子树update(ql, qr, l, mid, fa << 1, k); // 更新左子树if (qr > mid) // 如果更新区间在右子树update(ql, qr, mid + 1, r, fa << 1 | 1, k); // 更新右子树push_up(fa); // 更新父节点
}

来看一下区间乘

如果要更新的区间覆盖了当前的区间，直接更新当前t数组的值，更新tag1，tag2的懒惰标识，然后return，就不需要下放懒惰标识了；

如果区间没有覆盖，puah_down下放懒惰标识，更新左边，然后更新右边，然后push_up向上更新父节点；

mulpr_update

// 乘法更新函数
void mulpr_update(LL ql, LL qr, LL l, LL r, LL fa, LL k) {if (ql <= l && qr >= r) { // 如果更新区间完全覆盖当前区间t[fa] = t[fa] * k % m; // 更新当前节点的值tag1[fa] = tag1[fa] * k % m; // 更新乘法标记tag2[fa] = tag2[fa] * k % m; // 更新加法标记return;}LL mid = (l + r) >> 1; // 计算中间节点push_down(l, r, fa); // 向下更新标记if (ql <= mid) // 如果更新区间在左子树mulpr_update(ql, qr, l, mid, fa << 1, k); // 更新左子树if (qr > mid) // 如果更新区间在右子树mulpr_update(ql, qr, mid + 1, r, fa << 1 | 1, k); // 更新右子树push_up(fa); // 更新父节点
}

push_up

代码：

// 向上更新函数，更新父节点的值
void push_up(LL fa) {// 父节点的值等于左右子节点的和，取模 mt[fa] = (t[fa << 1] + t[fa << 1 | 1]) % m;
}

push_down

比较有难度的一个push_down，如果思路清晰的话就会变得很简单

左：

先将需要下放懒惰标识的区间取mid，更新树t左子节点，用tag1和tag2 fa位置的懒惰值更新

然后更新tag1左子节点，因为是乘，所以将tag1fa父节点的懒惰标识乘上tag1[fa<<1]左子节点的懒惰标识更新该左子节点的懒惰标识

然后更新tag2左子节点，虽然是区间加的懒惰数组，但是tag1和tag2作用在同一个线段树，所以在更新tag2时需要看看tag1[fa]有没有懒惰标识，有的话得加上tag1[fa] * tag2[fa << 1]，即如果tag1有懒惰标识，将其乘上tag2左子节点[fa<<1]原本有的懒惰标识；

右：

更新树t右子节点，用tag1和tag2 fa位置的懒惰值更新

然后更新tag1右子节点，因为是乘，所以将tag1fa父节点的懒惰标识乘上tag1[fa<<1|1]右子节点的懒惰标识更新该左子节点的懒惰标识

然后更新tag2右子节点，虽然是区间加的懒惰数组，但是tag1和tag2作用在同一个线段树，所以在更新tag2时需要看看tag1[fa]有没有懒惰标识，有的话得加上tag1[fa] * tag2[fa << 1|1]，即如果tag1有懒惰标识，将其乘上tag2左子节点[fa<<1|1]原本有的懒惰标识；

代码：

// 向下更新函数，处理懒惰标记
void push_down(LL l, LL r, LL fa) {LL mid = (l + r) >> 1; // 计算中间节点// 更新左子节点t[fa << 1] = (tag1[fa] * t[fa << 1] % m + tag2[fa] * (mid - l + 1) % m) % m;tag1[fa << 1] = (tag1[fa << 1] * tag1[fa]) % m; // 更新乘法标记tag2[fa << 1] = (tag2[fa] + tag1[fa] * tag2[fa << 1] % m) % m; // 更新加法标记// 更新右子节点t[fa << 1 | 1] = (tag1[fa] * t[fa << 1 | 1] % m + (tag2[fa] * (r - mid)) % m) % m;tag1[fa << 1 | 1] = (tag1[fa << 1 | 1] * tag1[fa]) % m; // 更新乘法标记tag2[fa << 1 | 1] = (tag2[fa] + tag1[fa] * tag2[fa << 1 | 1] % m) % m; // 更新加法标记// 清空当前节点的标记tag1[fa] = 1;tag2[fa] = 0;
}

区间查询query

代码：

// 查询函数
LL query(LL ql, LL qr, LL l, LL r, LL fa) {LL ret = 0; // 初始化返回值if (ql <= l && qr >= r) { // 如果查询区间完全覆盖当前区间return t[fa] % m; // 返回当前节点的值}LL mid = (l + r) >> 1; // 计算中间节点push_down(l, r, fa); // 向下更新标记if (ql <= mid) // 如果查询区间在左子树ret = (ret + query(ql, qr, l, mid, fa << 1)) % m; // 查询左子树if (qr > mid) // 如果查询区间在右子树ret = (ret + query(ql, qr, mid + 1, r, fa << 1 | 1)) % m; // 查询右子树return ret % m; // 返回结果
}

三、例题

例题：P3373 【模板】线段树 2 - 洛谷

完整代码：

#include <iostream>
#include <cstring>
using namespace std;// 定义常量 N，表示数组的最大大小
const int N = 1e5 + 10;// 定义长整型别名 LL
typedef long long LL;// 全局变量
LL n, m, q; // n: 数组大小, m: 模数, q: 查询次数
LL t[N * 4], a[N]; // t: 线段树数组, a: 原始数组
LL tag1[N * 4], tag2[N * 4]; // tag1: 乘法标记, tag2: 加法标记// 向上更新函数，更新父节点的值
void push_up(LL fa) {// 父节点的值等于左右子节点的和，取模 mt[fa] = (t[fa << 1] + t[fa << 1 | 1]) % m;
}// 向下更新函数，处理懒惰标记
void push_down(LL l, LL r, LL fa) {LL mid = (l + r) >> 1; // 计算中间节点// 更新左子节点t[fa << 1] = (tag1[fa] * t[fa << 1] % m + tag2[fa] * (mid - l + 1) % m) % m;tag1[fa << 1] = (tag1[fa << 1] * tag1[fa]) % m; // 更新乘法标记tag2[fa << 1] = (tag2[fa] + tag1[fa] * tag2[fa << 1] % m) % m; // 更新加法标记// 更新右子节点t[fa << 1 | 1] = (tag1[fa] * t[fa << 1 | 1] % m + (tag2[fa] * (r - mid)) % m) % m;tag1[fa << 1 | 1] = (tag1[fa << 1 | 1] * tag1[fa]) % m; // 更新乘法标记tag2[fa << 1 | 1] = (tag2[fa] + tag1[fa] * tag2[fa << 1 | 1] % m) % m; // 更新加法标记// 清空当前节点的标记tag1[fa] = 1; tag2[fa] = 0;
}// 建树函数
void build(LL l, LL r, LL fa) {if (l == r) { // 如果区间只有一个元素t[fa] = a[l] % m; // 直接赋值return;}LL mid = (l + r) >> 1; // 计算中间节点build(l, mid, fa << 1); // 递归构建左子树build(mid + 1, r, fa << 1 | 1); // 递归构建右子树push_up(fa); // 更新父节点
}// 查询函数
LL query(LL ql, LL qr, LL l, LL r, LL fa) {LL ret = 0; // 初始化返回值if (ql <= l && qr >= r) { // 如果查询区间完全覆盖当前区间return t[fa] % m; // 返回当前节点的值}LL mid = (l + r) >> 1; // 计算中间节点push_down(l, r, fa); // 向下更新标记if (ql <= mid) // 如果查询区间在左子树ret = (ret + query(ql, qr, l, mid, fa << 1)) % m; // 查询左子树if (qr > mid) // 如果查询区间在右子树ret = (ret + query(ql, qr, mid + 1, r, fa << 1 | 1)) % m; // 查询右子树return ret % m; // 返回结果
}// 更新函数
void update(LL ql, LL qr, LL l, LL r, LL fa, LL k) {if (ql <= l && qr >= r) { // 如果更新区间完全覆盖当前区间t[fa] = (t[fa] + (r - l + 1) * k) % m; // 更新当前节点的值tag2[fa] = (tag2[fa] + k) % m; // 更新加法标记return;}LL mid = (l + r) >> 1; // 计算中间节点push_down(l, r, fa); // 向下更新标记if (ql <= mid) // 如果更新区间在左子树update(ql, qr, l, mid, fa << 1, k); // 更新左子树if (qr > mid) // 如果更新区间在右子树update(ql, qr, mid + 1, r, fa << 1 | 1, k); // 更新右子树push_up(fa); // 更新父节点
}// 乘法更新函数
void mulpr_update(LL ql, LL qr, LL l, LL r, LL fa, LL k) {if (ql <= l && qr >= r) { // 如果更新区间完全覆盖当前区间t[fa] = t[fa] * k % m; // 更新当前节点的值tag1[fa] = tag1[fa] * k % m; // 更新乘法标记tag2[fa] = tag2[fa] * k % m; // 更新加法标记return;}LL mid = (l + r) >> 1; // 计算中间节点push_down(l, r, fa); // 向下更新标记if (ql <= mid) // 如果更新区间在左子树mulpr_update(ql, qr, l, mid, fa << 1, k); // 更新左子树if (qr > mid) // 如果更新区间在右子树mulpr_update(ql, qr, mid + 1, r, fa << 1 | 1, k); // 更新右子树push_up(fa); // 更新父节点
}// 主函数
int main() {cin >> n >> q >> m; // 输入数组大小 n, 查询次数 q, 模数 mfor (int i = 0; i <= N * 4; i++) tag1[i] = 1; // 初始化乘法标记为 1for (int i = 1; i <= n; i++) cin >> a[i]; // 输入数组元素build(1, n, 1); // 构建线段树while (q--) { // 处理每个查询int op; cin >> op; // 输入操作类型if (op == 2) { // 加法更新操作LL x, y, k; cin >> x >> y >> k; // 输入区间 [x, y] 和加数 kupdate(x, y, 1, n, 1, k % m); // 执行加法更新}else if (op == 3) { // 查询操作LL x, y; cin >> x >> y; // 输入查询区间 [x, y]cout << query(x, y, 1, n, 1) % m << endl; // 输出查询结果}else if (op == 1) { // 乘法更新操作LL x, y, k; cin >> x >> y >> k; // 输入区间 [x, y] 和乘数 kmulpr_update(x, y, 1, n, 1, k); // 执行乘法更新}}return 0; // 程序结束
}

---

总结

本期关于线段树的讲解就到这里，有什么疑问或者有什么错误的地方欢迎大家一起交流学习，下期带来线段树的离散化，二分搜索等进阶内容