线段树专题训练
练一下线段树专题吧，本篇博客持续更新！
线段树
线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。
线段树可以在 \(O(\log N)\) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
线段树维护的信息在很多时候可以认为是满足（幺）半群的性质的信息。
一个幺半群 \(M=(S,\circ ,e)\)，其中 \(\circ\) 为在集合 \(S\) 上定义的二元运算符，幺半群具有以下性质：
- 封闭性：\(\forall x\in S\) 和 \(\forall y\in S\) 有 \(x\circ y\in S\)。
- 结合律：\(\forall x,y,z\in S\) 有 \((x\circ y)\circ z=x\circ (y\circ z)\)。
- 存在幺元：即 \(\exists e\in S\) 满足 \(\forall x \in S\) 有 \(e\circ x=x\)，\(e\) 为左幺元；或 \(x\circ e=x\)，\(e\) 为右幺元。
我们观察到线段树上的信息一般满足这样的性质，一些数域上的加法与乘法自然，考虑二元的 \(\max(x,y)\) 运算，此时幺元为 \(-\infty\) 也满足这样的性质（一般左右幺元相同时简称为幺元）。
线段树将每个长度不为 \(1\) 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。
有个大小为 \(5\) 的数组 \(a=\{10,11,12,13,14\}\)，要将其转化为线段树，有以下做法：设线段树的根节点编号为 \(1\)，用数组 \(d\) 来保存我们的线段树，\(d_i\) 用来保存线段树上编号为 \(i\) 的节点的值（这里每个节点所维护的值就是这个节点所表示的区间总和）。
我们先给出这棵线段树的形态，如图所示：
图中每个节点中用红色字体标明的区间，表示该节点管辖的 \(a\) 数组上的位置区间。如 \(d_1\) 所管辖的区间就是 \([1,5]\)（\(a_1,a_2, \cdots ,a_5\)），即 \(d_1\) 所保存的值是 \(a_1+a_2+ \cdots +a_5\)，\(d_1=60\) 表示的是 \(a_1+a_2+ \cdots +a_5=60\)。
通过观察不难发现，\(d_i\) 的左儿子节点就是 \(d_{2\times i}\)，\(d_i\) 的右儿子节点就是 \(d_{2\times i+1}\)。如果 \(d_i\) 表示的是区间 \([s,t]\)（即 \(d_i=a_s+a_{s+1}+ \cdots +a_t\)) 的话，那么 \(d_i\) 的左儿子节点表示的是区间 \([ s, \frac{s+t}{2} ]\)，\(d_i\) 的右儿子表示的是区间 \([ \frac{s+t}{2} +1,t ]\)。
在实现时，我们考虑递归建树。设当前的根节点为 \(p\)，如果根节点管辖的区间长度已经是 \(1\)，则可以直接根据 \(a\) 数组上相应位置的值初始化该节点。否则我们将该区间从中点处分割为两个子区间，分别进入左右子节点递归建树，最后合并两个子节点的信息。（以上来自wiki）
在进行区间操作的时候，我们一般不会把状态更新到每个节点，如果更新，那么一次操作最大的复杂度会是 \(O(n)\)。因此我们会采取懒惰标记的方式去记录这次的操作，如果这次更新完整地包含了一个区间，那么我们对这个区间打上懒惰标记，不继续往下更新，若要查询，则会将懒惰标记加到对应的节点上去。可以证明，每一次操作不会超过4个区间，加上区间操作是从上往下延的，那么一次操作理论最坏的情况应该是 \(O(log_2n)\)，非常符合我们的要求。查询复杂度同理，也是 \(O(log_2n)\)。
这里需要注意几点：
懒惰标记怎么打？
当当前区间完全包含于我要操作的区间，这个时候可能会有点疑问，这个区间的值我是加或者不加，我的懒惰标记肯定会给到这个区间，但是这个值加不加，懒惰标记给到了，那么一个区间带了一个懒惰标记，它的值到底是意味着加了还是没加呢？因为感觉理论上好像都可行的，但是这里实际情况是：要加！因为我区间的值会被更新到父亲节点，如果我不加，那么更新上去的节点值就是错误的。因此此时我一定要把值加上去。那么一个区间带了懒惰标记它的含义是：我自己的值已经加上去了，但是我的儿子区间和孙子，曾孙子区间都没加上这个值，等会过来的时候都需要加上，那么带了懒惰标记的那个区间是已经加上了的。
所以懒惰标记什么含义一定要搞清楚，不能模棱两可，不能，不能！！！
什么时候push down
懒惰标记下传的操作我们叫
push_down。什么时候需要呢？我们理解了懒惰标记的含义之后，我们就清楚了，带了懒惰标记的区间，本身已经加上了值，只是儿子都没加上去。那么如果我直接再对整个区间操作，需不需要
push_down
呢？不需要，因为这个区间已经是真实值了，但是我在对一个带有懒惰标记的区间的儿子区间尝试进行操作的时候呢？那肯定需要了！因为儿子区间还不是真实值，还得加上父亲给它的懒惰标记才是。
那么我们 push_down
一次就会把一个区间的懒惰标记清零，给对应的两个儿子区间加上对应的值，并把懒惰标记分发给他们。
练习题
P2023 [AHOI2009] 维护序列
题目背景
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。
题目描述
有一个长为 \(n\) 的数列 \(\{a_n\}\)，有如下三种操作形式：
- 格式
1 t g c，表示把所有满足 \(t\le i\le g\) 的 \(a_i\) 改为 \(a_i\times c\) ; - 格式
2 t g c表示把所有满足 \(t\le i\le g\) 的 \(a_i\) 改为 \(a_i+c\) ; - 格式
3 t g询问所有满足 \(t\le i\le g\) 的 \(a_i\) 的和，由于答案可能很大，你只需输出这个数模 \(p\) 的值。
输入格式
第一行两个整数 \(n\) 和 \(p\)。
第二行含有 \(n\) 个非负整数，表示数列 \(\{a_i\}\) 。
第三行有一个整数 \(m\)，表示操作总数。
从第四行开始每行描述一个操作，同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
输出格式
对每个操作 3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。
样例 #1
样例输入 #1
1 | 7 43 |
样例输出 #1
1 | 2 |
提示
样例输入输出 1 解释
- 初始时数列为 \(\{1,2,3,4,5,6,7\}\)。
- 经过第 \(1\) 次操作后，数列为 \(\{1,10,15,20,25,6,7\}\)。
- 对第 \(2\) 次操作，和为 \(10+15+20=45\)，模 \(43\) 的结果是 \(2\)。
- 经过第 \(3\) 次操作后，数列为 \(\{1,10,24,29,34,15,16\}\)。
- 对第 \(4\) 次操作，和为 \(1+10+24=35\)，模 \(43\) 的结果是 \(35\)。
- 对第 \(5\) 次操作，和为 \(29+34+15+16=94\)，模 \(43\) 的结果是\(8\)。
数据规模与约定
测试数据规模如下表所示：
| 数据点编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,10 |
|---|---|---|---|---|---|---|---|---|---|
| \(n=\) | \(10\) | \(1000\) | \(1000\) | \(10000\) | \(60000\) | \(70000\) | \(80000\) | \(90000\) | \(100000\) |
| \(m=\) | \(10\) | \(1000\) | \(1000\) | \(10000\) | \(60000\) | \(70000\) | \(80000\) | \(90000\) | \(100000\) |
对于全部的测试点，保证 \(0 \leq p, a_i, c \leq 10^9\)，\(1 \leq t \leq g \leq n\)。
分析
是一个线段树的翻版题，只不过要取模，并且有乘法，乘法其实跟加法一样，如果区间里的数都乘上一个数，那么其实就相当于先和再乘，乘法懒惰标记默认应该为1。因为既有加法也有乘法，因此我们需要两个懒惰标记，当懒惰标记乘上去时，加法的懒惰标记应该对应要乘上去，在push_down的时候，我们先乘，再加即可。
标程
1 |
|