数据结构专题-学习笔记：线段树

目录

• 一些 update
• 1.概述
• 2.模板
  • 1.线段树的建树-build
  • 2.线段树的单点修改-change
  • 3.线段树的单点查询-ask
  • 4.线段树的区间修改-add
    • 什么是 lazy_tag?
  • 5.区间加的懒标记-spread
  • 6.线段树的区间查询-ask
  • 最后的代码
  • 7.线段树的区间乘法-mul
  • 8.区间乘的懒标记-spread
• 3.例题

一些 update

update 2020/12/29:现根据个人实际情况对文章的安排做出了一定的修改，对各位读者带来的不便深表歉意，现在已经更新排版。

1.概述

线段树，顾名思义，是一种基于树的数据结构。线段树跟分块一样，也是用来支持区间操作的（比如区间加，区间求和，区间求 \(max\) 等等），而且线段树可以支持很多树状数组做不到的内容；换言之，我们可以将线段树看作升级版的树状数组。而且线段树的可扩展性很强，很多的数据结构都是从线段树上扩展的。

不过线段树也有一些弱点，比如常数比较大，不能支持插入/删除操作，没有办法维护一些东西（但是分块却可以轻易的实现）等等。

所以，虽然线段树可以完成很多事情，但是同样要熟练掌握树状数组与分块。卡常的题目就要用树状数组，一些线段树难维护的东西 （比如 lxl 的 Ynoi） 就要用分块。

所以接下来，开始讲解线段树吧！

线段树专题总共分几个板块：

1. ：主要讲解最普通线段树的用法以及写法。
2. ：线段树与别的算法/数据结构的结合，有些题目带有一定的思维性。
3. ：让我们看看 GSS1-5 的题目用线段树如何解决。
4. ：讲解可持久化数组/线段树。
5. ：讲解李超线段树及其应用。

2.模板

题单：

• P3372 【模板】线段树 1
• P3373 【模板】线段树 2

让我们先来看一组对话：

分块：这两道题不是随随便便就水过去了？线段树不行呀！

线段树：如果 \(n \leq 10^6\) 呢？

分块：。。。。。。

树状数组：线段树常数巨大，还是我好用！

（貌似线段树写法优秀常数也挺小的）

线段树：那么模板 2 要怎么做呢？

树状数组：。。。。。。

所以发现没有，线段树在时间上吊打分块，在用法上吊打树状数组。

那么什么是线段树？

比如下图，它就是一棵线段树。（取 \(n=8\)）

从上面这幅图可以看出来：

1. 线段树是一颗二叉树，因此我们可以类比二叉树的存储方式来存放线段树。
2. 线段树的每个节点维护的是一段区间，直观上像一条线段。
3. 线段树的叶子节点才是真实的数值，而非叶子节点维护的都是区间的信息。

那么了解了线段树是一个什么玩意，接下来我们看一看线段树的各种基础操作吧！

P3372 【模板】线段树 1

这道题有两个操作：区间加，区间查询。

首先，我们回顾一下分块是怎么干的：

1. 先将数列划分成若干个块
2. 然后 “大块维护，小块朴素”，大块维护时打一个 \(tag\) 维护，小块直接暴力。

那么，我们看一看线段树又是怎么干的：

1. 先建一棵线段树
2. 对于所有的区间询问，我们从根节点开始不断分叉，当一个点的区间完全被包含在询问区间当中时，完成我们需要做的事情然后退出。

有没有发现很像~~~

1.线段树的建树-build

前面说过了，线段树是基于二叉树的，因此我们可以像弄二叉树那样弄线段树。

首先我们先开一个结构体 \(tree\) 拿来建树。

\(tree_p\) 中要维护这样几个信息：这个节点的左右端点 \(l,r\) ，这个节点维护的区间和 \(sum\) ，以及一个神秘的东西 \(add\) ，下文分别用 \(l(p),r(p),s(p),a(p)\) 来表示 \(tree_p\) 里面维护的东西。而 \(a(p)\) 是干什么用的呢？等一会你就知道了。

由于线段树基于二叉树，所以我们的空间不能开成正常的 1 倍空间。推荐值是开 4 倍，如果是 2 倍就太小了，可能 RE。

我们规定根节点为 1 号节点，那么根节点就维护的是 \([1,n]\) 的结果。

然后根据二叉树的基本知识，我们知道 \(p\) 号节点的左右两个节点是 \(p << 1, p << 1 | 1\)（这里用位运算是为了减小常数）。不理解？ \(p << 1 = 2 * p\) ，由于 \(p << 1\) 后二进制下最低位为 0，所以 \(p << 1 | 1 = 2 * p + 1\)。

那么根节点的左右孩子就是 \(2,3\) 两个节点。

接下来递归操作，\(2\) 号节点维护 \([1,n >> 1]\)，\(3\) 号节点维护 \([(n >> 1) + 1, n]\)，不断递归即可。

到叶子节点的标记是 \(l==r\) ,说明没法往下走了，此时我们根据题目需要更新 \(s(p)\) 的值，令其为 \(a_l\)。

那么假如这个点不是叶子节点，那么他的孩子建树完成后我们需要更新 \(s(p) = s(p << 1) + s(p << 1 | 1)\) （根据题目而变，有时候不一定是 \(sum\) ，也可以是 \(max\) 等，此时最大值就是两个孩子最大值的最大值）。

所以从上面也可以发现：线段树能够维护的一般都是满足区间可加性（比如和，最大值等）的操作，不是区间可加性的题目线段树一般不能做。（不过这还要看怎么维护，如果我们能够通过一些满足区间可加性的东西 \(O(1)\) 来推出答案那么线段树照样可以做。）

因此我们可以总结出建树操作的一般规律：

1. 首先 build 函数里面先传三个参数 \(p,l,r\) ，表示节点编号，维护的左右端点。
2. 因为我们要知道 \(p\) 节点维护的是哪段区间，所以标记 \(l(p)=l,r(p)=r\)。
3. 然后如果 \(l == r\) ，表示到了叶子节点，此时我们需要标记 \(s(p)=a_l\) 。
4. 否则，算出 \(mid = (l + r) >> 1\)，然后递归建树 \(p << 1, l, mid + 1\) 与 \(p << 1 | 1, mid + 1, r\)。
5. 最后不要忘记更新 \(s(p) = s(p << 1) + s(p << 1 | 1)\)。

分析一下时间复杂度：因为是二叉树，所以建树复杂度约为 \(O(n+\dfrac{n}{2}+\dfrac{n}{4}+...)=O(2n)=O(n)\)。

建树操作的代码：（附带结构体）

struct node
{
	int l, r;
	LL add, sum;
	#define l(p) tree[p].l
	#define r(p) tree[p].r
	#define a(p) tree[p].add
	#define s(p) tree[p].sum
}tree[MAXN << 2];
//define 宏定义 l(p),r(p),s(p),a(p)
void build(int p, int l, int r)
{
	l(p) = l, r(p) = r;//维护左右端点
	if (l == r) {s(p) = a[l]; return ;}//叶子节点
	int mid = (l + r) >> 1;
	build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);//继续建树
	s(p) = s(p << 1) + s(p << 1 | 1);//更新结果
}

接下来开始的所有操作都是从根节点开始的，函数内的参数第一个 \(p\) 都是用来表示当前树节点编号的。

2.线段树的单点修改-change

说句闲话：其实很多大佬喜欢用别的名字，比如 update，不过这不重要，只是名字而已。

模板给的是区间修改，但是在讲区间修改之前我们先看看单点修改是怎么做的（毕竟区间修改还要牵扯到那个神秘的 \(add\) ，单点修改比较简单也很重要）。

我们抛出这样一个修改：将 \(a_l\) 修改成 \(v\)。

那么显然的，我们首先要找到 \(a_i\) 对不对？因此我们考虑从根节点开始搜索 \(a_i\) 所在的位置。

还是刚刚那张图：

假如我们要寻找 \(a_7\) 的位置，那么我们从根节点出发，先看看 \(a_7\) 是被左儿子维护还是右儿子维护；哪边维护往哪里走，递归寻找。而判断是哪边维护也很简单，我们不是维护了 \(l(p),r(p)\) 吗？看看 \(7\) 在不在 \(l(p),r(p)\) 当中即可。

当然，实际写代码的时候我们可以先算出 \(mid = (l(p) + r(p)) >> 1\)，模仿建树操作找到 \(mid\)，这样 \(tree[p << 1]\) 维护 \([l(p),mid]\)，\(tree[p << 1 | 1]\) 维护 \([mid + 1, r(p)]\)。判断询问位置 \(a_l\) 在哪里是直接判断 \(l\) 和 \(mid\) 的大小关系即可，\(l \leq mid\) 表示在左儿子，\(l > mid\) 表示在右儿子。

最后找到叶子节点，判断依据依然是 \(l(p) == r(p)\) ，找到后更新结果。

然后逐层返回根节点，但是同时不要忘记更新路上节点的值（因为他们维护的区间已经有值被修改了）。

分析一下时间复杂度：树高约为 \(logn\)，所以时间复杂度是 \(O(logn)\)

单点修改的代码如下：

void change(int p, int l, int v)//单点修改
{
	if (l(p) == r(p)) {s(p) = v; return ;}//叶子节点
	int mid = (l(p) + r(p)) >> 1;
	if (l <= mid) change(p << 1, l, v);//在左儿子里面
	else change(p << 1 | 1, l, v);//不在左儿子里就在右儿子里
	s(p) = s(p << 1) + s(p << 1 | 1);//不要忘记更新
}

3.线段树的单点查询-ask

一样的，线段树的区间查询如果是基于区间修改之上的那么依然会牵扯到这个神秘的 \(add\)，所以先将单点查询。

单点查询更多的地方写作 \(\text{query}\)，同样只是个人喜好问题，我习惯于使用 \(\text{ask}\)。

我们抛出这样一个询问：询问 \(a_x\) 的值。

模仿单点修改的套路，我们直接找到 \(a_x\) 所在的叶子节点，然后返回其值即可。怎么找？见单点修改。

分析一下时间复杂度：与上面同理 \(O(logn)\)。

单点查询的代码如下：

int ask(int p, int x)//单点修改
{
	if (l(p) == r(p)) return s(p);//叶子节点
	int mid = (l(p) + r(p)) >> 1;
	if (x <= mid) return ask(p << 1, l, r);//在左儿子里面
	else return ask(p << 1 | 1, l, r);//不在左儿子里就在右儿子里
}

4.线段树的区间修改-add

到区间修改了，我们开始要和 \(add\) 打交道了。

我们抛出这样一个问题：将 \([l,r]\) 内的数全部加上 \(k\)。

我们可以模仿单点修改的套路，直接抛一个区间进去，然后暴力找到叶子节点后修改。

但是，如果我们这样做就会导致一个问题：我们将区间修改强制性的拆成了单点修改，这样无故增加了 \(O(n)\) 的时间复杂度。

于是我们考虑这样几个问题：是不是我们所有的结果都是我们一定要用到的？如果有一些不用，我们不是就浪费时间了？而且万一我们有好几次修改操作连续压在一个点上，那么我们不是可以一起修改吗？

这就是线段树里面一个很重要的东西了：懒标记 lazy_tag。

什么是 lazy_tag?

懒标记懒标记，肯定很懒对不对？而懒标记 lazy_tag 很重要的一个作用就是：维护修改。而这里就是 \(add\) 的作用：加法 lazy_tag。

比如我们对区间 \([l,r]\) 内的数加上 \(k\) 。本来我们是暴力拆成单点修改的，但是有了懒标记之后：

情况一：

\([l,r]\) ：\(p\) 节点，为什么你的 \(l(p),r(p)\) 都被我们包含了啊？（指 \(l(p) >= l \&\& r(p) <= r\)），我们要暴力单点修改了哦~

\(p\) 的 lazy_tag：等一等！现在有我在这里，你们不需要单点修改了，把 \(k\) 加到我身上，我来帮你们单点修改，你们负责把 \(s(p)\) 修改了即可。

\([l,r]\) ：还有这等好事？那我们把 \(k\) 给你，我们修改 \(s(p)\)。

于是 \(a(p) += k,s(p) += k * (r(p) - l(p) + 1)\)，快乐返回~

这里关于 \(s(p)\) 的更新：里面有 \(r(p) - l(p) + 1\) 个数，每个数加 \(k\) ，那么直接提取出来即可。

情况二：

\([l,r]\)：啊 \(p\) 节点，这一次虽然我们仍然包含了你的 \(l(p),r(p)\) ，但是你的 \(a(p)\) 已经有值了，那我们只能单点修改了哦~

\(a(p)\)：等一等！难道你忘记了 加法具有区间可加性 吗？给我，我照样解决！

于是仿照上面的方式，我们愉快返回~

情况三：

\([l,r]\)：\(p\) 节点，这回我们没有包含你的全部区间了，只有一部分了，我们就只能暴力修改了。

\(a(p)\) （很遗憾）：那好吧，我只能放你们过去了，不过等一等，我要下压 lazy_tag。

\([l,r]\) ：为什么？

\(a(p)\) ：因为你们接下来要更新的时候会影响到 \(s(p << 1), s(p << 1 | 1)\) 及其 lazy_tag，而且此时此刻 你们直接作用在我儿子的区间上，我对他们没有束缚力了，必须下压 lazy_tag，才能保证答案正确。

因此我们来看看这种情况下的两个问题：

1. 怎么判断部分包含？
2. 怎么下压 lazy_tag?

先看如何判断部分包含。

实际上根据单点修改的思想，我们仍然可以求出 \(mid = (l(p) + r(p)) >> 1\)，如果 \(l \leq mid\) ，说明有一部分结果在左子树，递归左子树；如果 \(r > mid\) ，说明有一部分结果在右子树，递归右子树。

于是，我们就完美的判断了部分包含。

Q：那么如果不包含呢？

A：如果不包含首先父亲节点就不会让他进来，其次不包含也不会满足上述任意一个条件。

接下来看下压 lazy_tag。

5.区间加的懒标记-spread

首先，我们将 \(a(p)\) 下压到 \(tree[p << 1], tree[p << 1 | 1]\)，需要更新 \(s(p << 1), s(p << 1 | 1)\)。更新方法见上。

然后，我们处理一下 \(a(p << 1)+=a(p), a(p << 1 | 1)+=a(p)\)，其实就是维护儿子的 lazy_tag。

最后 不要忘记将 \(a(p)\) 清零！！！！！！

下压懒标记 lazy_tag 的代码如下：

void spread(int p)//下压 lazy_tag
{
	if (a(p))//如果有 lazy_tag
	{
		s(p << 1) += a(p) * (r(p << 1) - l(p << 1) + 1);
		s(p << 1 | 1) += a(p) * (r(p << 1 | 1) - l(p << 1 | 1) + 1);
		//更新左右儿子的值
		a(p << 1) += a(p); a(p << 1 | 1) += a(p);
		//更新左右儿子的 lazy_tag
		a(p) = 0;
		//不要忘记清零！！！！！！
	}
}

于是有了这一段代码后，结合上述所讲，区间修改就很好写了。

分析一下时间复杂度：极限状况下就是 \(l = r\) ，此时变为单点修改，时间复杂度 \(O(logn)\) 。其他情况一般都走不到叶子节点，即使你左右子树疯狂递归，因为有 lazy_tag 的阻挠，时间复杂度也是近似 \(O(logn)\)。

不过：不要忘记更新 \(s(p)\) ！

我告诉我旁边的人：知道单点修改怎么写吗：add(1,l,l,k)

区间修改的代码如下：

void add(int p, int l, int r, LL k)//区间修改
{
	if (l(p) >= l && r(p) <= r)//区间完全包含 
	{
		s(p) += k * (r(p) - l(p) + 1);//更新 s(p)
		a(p) += k; return ;//更新 lazy_tag
	}
	spread(p);//下压 lazy_tag，不要忘记！
	int mid = (l(p) + r(p)) >> 1;
	if (l <= mid) add(p << 1, l, r, k);//左儿子有要修改的
	if (r > mid) add(p << 1 | 1, l, r, k);//右儿子有要修改的
	s(p) = s(p << 1) + s(p << 1 | 1);//不要忘记更新！
}

6.线段树的区间查询-ask

有了区间修改的基础后，区间查询就不难写了。

如果 \([l,r]\) 包含这段区间，那么直接返回 \(s(p)\) 。

否则 先下压 lazy_tag，然后递归左右子树，统计一下答案。

分析一下时间复杂度：依旧是 \(O(logn)\)。

区间查询的代码：

LL ask(int p, int l, int r)//区间查询
{
	if (l(p) >= l && r(p) <= r) return s(p);//包含区间
	spread(p);//下压 lazy_tag，不要忘记！
	int mid = (l(p) + r(p)) >> 1; LL val=0;
	if (l <= mid) val += ask(p << 1, l, r);//左儿子有答案，统计
	if (r > mid) val += ask(p << 1 | 1, l, r);//右儿子有答案，统计
	return val;
}

最后的代码

于是，将上述的 build,spread,add,ask(区间修改) 四个函数整理一下，加一个主程序就做完了！！！

再放一遍题目链接：P3372 【模板】线段树 1

不过：

友善的出题人友情提醒您：
道路千万条，long long 第一条。
结果存 int ，爆零两行泪。

道路千万条，long long 第一条。
快读用 int ，爆零两行泪。

道路千万条，%lld 第一条。
输出用 %d ，爆零两行泪。

贴一下全部的代码：

#include 
using namespace std;

const int MAXN = 1e5 + 5;
typedef long long LL;
int n, m;
LL a[MAXN];
struct node
{
	int l, r;
	LL add, sum;
	#define l(p) tree[p].l
	#define r(p) tree[p].r
	#define a(p) tree[p].add
	#define s(p) tree[p].sum
}tree[MAXN << 2];
//define 宏定义 l(p),r(p),s(p),a(p)
LL read()
{
	LL sum = 0, fh = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fh = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {sum = (sum << 3) + (sum << 1) + (ch ^ 48); ch = getchar();}
	return sum * fh;
}

void build(int p, int l, int r)
{
	l(p) = l, r(p) = r;//维护左右端点
	if (l == r) {s(p) = a[l]; return ;}//叶子节点
	int mid = (l + r) >> 1;
	build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);//继续建树
	s(p) = s(p << 1) + s(p << 1 | 1);//更新结果
}

void spread(int p)//下压 lazy_tag
{
	if (a(p))//如果有 lazy_tag
	{
		s(p << 1) += a(p) * (r(p << 1) - l(p << 1) + 1);
		s(p << 1 | 1) += a(p) * (r(p << 1 | 1) - l(p << 1 | 1) + 1);
		//更新左右儿子的值
		a(p << 1) += a(p); a(p << 1 | 1) += a(p);
		//更新左右儿子的 lazy_tag
		a(p) = 0;
		//不要忘记清零！！！！！！
	}
}

void add(int p, int l, int r, LL k)//区间修改
{
	if (l(p) >= l && r(p) <= r)//区间完全包含 
	{
		s(p) += k * (r(p) - l(p) + 1);//更新 s(p)
		a(p) += k; return ;//更新 lazy_tag
	}
	spread(p);//下压 lazy_tag，不要忘记！
	int mid = (l(p) + r(p)) >> 1;
	if (l <= mid) add(p << 1, l, r, k);//左儿子有要修改的
	if (r > mid) add(p << 1 | 1, l, r, k);//右儿子有要修改的
	s(p) = s(p << 1) + s(p << 1 | 1);//不要忘记更新！
}

LL ask(int p, int l, int r)//区间查询
{
	if (l(p) >= l && r(p) <= r) return s(p);//包含区间
	spread(p);//下压 lazy_tag，不要忘记！
	int mid = (l(p) + r(p)) >> 1; LL val=0;
	if (l <= mid) val += ask(p << 1, l, r);//左儿子有答案，统计
	if (r > mid) val += ask(p << 1 | 1, l, r);//右儿子有答案，统计
	return val;
}

int main()
{
	n = read(); m = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	build(1, 1, n);
	for (int i = 1; i <= m; ++i)
	{
		int opt = read();
		if (opt == 1)
		{
			int l = read(), r = read(), k = read();
			add(1, l, r, k);
		}
		else
		{
			int l = read(), r = read();
			printf ("%lld\n", ask(1, l, r));
		}
	}
	return 0;
}

线段树 1 已经解决，我们看看线段树 2 怎么办。

7.线段树的区间乘法-mul

P3373 【模板】线段树 2

当然，分块照样能够水过，但是我们看看时间上吊打分块的线段树会有怎样优秀的表现。

这道题显然，根据题意我们要维护 5 个东西：\(l,r,sum,add,mul\)，分别为维护的左端点、右端点，总和，加法 lazy_tag，乘法 lazy_tag。\(mul\) 下文写作 \(m(p)\)。

那么问题来了：我们在下压 lazy_tag 与更新 lazy_tag 的时候要怎么办呢？是先考虑乘法再考虑加法（下文称其为『先乘后加』）还是先考虑加法再考虑乘法（下文称其为『先加后乘』）？

8.区间乘的懒标记-spread

那么，以这组数据为例，看看是先乘后加好还是先加后乘好。

比如现在 \(n = 4, a = {1, 2, 3, 4}\)。

建树如图：（为了方便已经省略了 \(sum,add,mul\)）

我们有三个针对区间 \([1,4]\) 的操作：\(+2,*5,+4\)。

首先的 \(+2\) ：\(a(1)=2\)

然后的 \(\times 5\)：\(m(1)=5\)

最后的 \(+4\)：\(a(1)=2+4=6\)

于是：

操作 2 之后的式子是：$$sum=\sum_{i=1}^{4}(a_i+2)\times5$$

但是操作三之后呢？按照先乘后加的原则：$$sum=\sum_{i=1}^{4}(a_i+6)\times5$$

但是肉眼可见这与结果不符合，正确的结果应该是：$$sum=\sum_{i=1}^{4}(a_i+2+\dfrac{4}{5})\times5$$

结果出现了可恨的分数，不要！

那么先乘后加呢？

结果手动模拟了一遍，发现：$$sum=\sum_{i=1}^{4}(a_i\times5+2\times5+4)$$

没毛病！就先乘后加了！

于是我们确定使用先乘后加。

具体做法：

1. 如果是区间加，直接在加法 lazy_tag 上打标记就好。
2. 如果是区间乘，在更新乘法 lazy_tag 时不要忘记更新加法 lazy_tag （让它乘上要乘的那个数）
3. 在下压 lazy_tag 时总和先乘乘法 lazy_tag 再加加法 lazy_tag 对其产生的贡献。
4. 注意 \(m(p)\) 的初始化为 1 而不是 0！！！！！！
5. 注意 long long 与 %lld

代码：

#include 
using namespace std;

const int MAXN = 1e5 + 10;
typedef long long LL;
int n, m, P;
LL a[MAXN];
struct node
{
	int l, r;
	LL mul, add, sum;
	#define l(p) tree[p].l
	#define r(p) tree[p].r
	#define m(p) tree[p].mul
	#define a(p) tree[p].add
	#define s(p) tree[p].sum
}tree[MAXN << 2];

LL read()
{
	LL sum = 0, fh = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fh = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {sum = (sum << 3) + (sum << 1) + (ch ^ 48); ch = getchar();}
	return sum * fh;
}

void build(int p, int l, int r)
{
	l(p) = l, r(p) = r, m(p) = 1;//注意 m(p) = 1！！！！！！
	if (l == r) {s(p) = a[l] % P; return ;}
	int mid = (l + r) >> 1;
	build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
	s(p) = (s(p << 1) + s(p << 1 | 1)) % P;
}

void spread(int p)
{
	s(p << 1) = (s(p << 1) * m(p) + a(p) * (r(p << 1) - l(p << 1) + 1)) % P;
	s(p << 1 | 1) = (s(p << 1 | 1) * m(p) + a(p) * (r(p << 1 | 1) - l(p << 1 | 1) + 1)) % P;
	//先乘后加
	m(p << 1) = m(p << 1) * m(p) % P; m(p << 1 | 1) = m(p << 1 | 1) * m(p) % P;
	a(p << 1) = (a(p << 1) * m(p) + a(p)) % P; a(p << 1 | 1) = (a(p << 1 | 1) * m(p) + a(p)) % P;
	//先乘后加
	m(p) = 1; a(p) = 0;//注意 m(p) = 1！！！！！！
}

void mul(int p, int l, int r, LL k)
{
	if (l(p) >= l && r(p) <= r) {s(p) = s(p) * k % P; m(p) = m(p) * k % P; a(p) = a(p) * k % P; return ;}
	spread(p);
	int mid = (l(p) + r(p)) >> 1;
	if (l <= mid) mul(p << 1, l, r, k);
	if (r > mid) mul(p << 1 | 1, l, r, k);
	s(p) = (s(p << 1) + s(p << 1 | 1)) % P;
}

void add(int p, int l, int r, LL k)
{
	if (l(p) >= l && r(p) <= r) {s(p) = (s(p) + k * (r(p) - l(p) + 1)) %P; a(p) = (a(p) + k) % P; return ;}
	spread(p);
	int mid = (l(p) + r(p)) >> 1;
	if (l <= mid) add(p << 1, l, r, k);
	if (r > mid) add(p << 1 | 1, l, r, k);
	s(p) = (s(p << 1) + s(p << 1 | 1)) % P;
}

LL ask(int p, int l, int r)
{
	if (l(p) >= l && r(p) <= r) return s(p);
	spread(p);
	int mid = (l(p) + r(p)) >> 1; LL val = 0;
	if (l <= mid) val += ask(p << 1, l, r);
	if (r > mid) val += ask(p << 1 | 1, l, r);
	return val % P;
}

int main()
{
	n = read(); m = read(); P = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	build(1, 1, n);
	for (int i = 1; i <= m; ++i)
	{
		int opt = read();
		if (opt == 1)
		{
			int l = read(), r = read(); LL k = read();
			mul(1, l, r, k);
		}
		else if (opt == 2)
		{
			int l = read(), r = read(); LL k = read();
			add(1, l, r, k);
		}
		else
		{
			int l = read(), r = read();
			printf ("%lld\n", ask(1, l, r) % P);
		}
	}
	return 0;
}

3.例题

这里就不放例题了（其实是文章篇幅问题），例题会按照最开始讲过的方式放置与讲解。

总之线段树还是挺重要的数据结构，因为线段树的很多思想都能够套到别的数据结构上。

在下一个专题中，将会讲解线段树与别的算法/数据结构的总和，以及一些带有思维性的题目。

详情请见