讲的就是题目啊。
知识概括
线段树是一种树形结构，用分治的思想，把数组里的元素建成二叉树，用于快速查询区间和和区间修改之类的操作。
它的修改（单点或区间 ）和区间查询时间复杂度都是 O(logn)O(\log n)O(logn)，但是，如果数组元素少或者操作次数少的时候没必要用这个，如果说是 这种题 的数据，那么我们就要使用线段树来解。
正题
如果你学过归并排序或者其他的分治思想技巧，那么你肯定知道分治就是把东西给分成多份去递归求解，线段树也是一样，左儿子管区间的左半部分，右儿子管区间的右半部分。当然，如果 l=rl=rl=r 的话，说明这个节点直接存 a[l]a[l]a[l] 的值。
比如说 1−81-81−8 的升序排列，线段树里的东西大概就是
OI里我们常常用数组存这个树结构，根的编号就是 111 ，一个节点 xxx 的左右儿子是 2x2x2x 与 2x+12x+12x+1，相信大家都知道，那为啥你去看所有的线段树题解，他们的 treetreetree 数组都要开 MAXN∗4MAXN*4MAXN∗4 呢？
举个例子，1、2、3、4、51、2、3、4、51、2、3、4、5 ，它们是数组里的元素，画一画就知道，线段树有 999 个节点，而线段树会把区间补到大于等于 nnn （这里 n=5n=5n=5）的最小的 222 的幂，这里记为 sizesizesize ，那么 sizesizesize 满足 size≥nsize ≥ nsize≥n 且有 size=2ksize = 2^ksize=2k，这一颗虚拟的满二叉树的节点数量就是 2∗size−12*size-12∗size−1。
看下最坏情况：
2k−1+1<n≤2k2^{k-1}+1 < n ≤ 2^k2k−1+1<n≤2k
设 n=2k−1+1n=2^{k-1}+1n=2k−1+1 ，此时 size=2ksize=2^ksize=2k ，总结点上限是：
2⋅size−1=2⋅2k−1=2k+1−12\cdot size -1 = 2\cdot 2^k-1 =2^{k+1} -12⋅size−1=2⋅2k−1=2k+1−1
但我们有 n>2k−1n>2^{k-1}n>2k−1 ，所以 2k<2n2^k<2n2k<2n，也有 2k+1<4n2^{k+1}<4n2k+1<4n。
至此，我们知道了 线段树节点数量 <4n<4n<4n。
线段树1.0
这个是简单的线段树，只需要实现单点修改和区间求和，虽然说听着挺难的，但是我们看下实现就能发现，hjda，嗯对。（不是我说的我是区）
看下建树吧。
递归函数 build(u,l,r)build(u,l,r)build(u,l,r) ，代表节点 uuu 管 l−rl-rl−r 这个区域
然后是单点修改。
你可以发现我们连赋值都是分治的，好美丽的线段树。
最后是区间求和。
又是分治递归，线段树你咋这么好看😍。
完整实现：
然后你就可以用这个简单的线段树过了P3372 【模板】线段树 1。
这就是简单的线段树。
P2357 守墓人
主要就是处理更新主墓碑，可以看成一个单点修改，然后减 kkk 就是加 −k-k−k ，所以仍然是那个板子，多处理几个操作就过了。
P1816 忠诚
查询实现题，连修改都不用。
其实就是把区间和的板子改了，每次的 tr[u]tr[u]tr[u] 取它左右子树里的最小值即可。
线段树2.0
你其实也在代码里看到了一个 lazylazylazy ，这就是二代线段树的重中之重，懒标记。
都说了懒标记了，线段树就先放一下啊。
懒标记
我们知道线段树的单点修改时间是 O(logn)O(\log n)O(logn) 的，如果我们要做区间修改，那么最坏情况下只能给每一个区间内的元素做单点修改，时间 O(n)O(n)O(n) ，大数据直接T飞。
这个时候懒标记就有用了，这个东西的核心思想就是 能不用就不用 ，也就是把标记先存在父节点上，等要用的时候再下传给子节点，这样拖延修改后，时间又回到了 O(logn)O(\log n)O(logn)。
我们在线段树里把懒标记数组标为 lazylazylazy ， lazy[u]lazy[u]lazy[u] 代表节点 uuu 代表的整个区间已经完成区间加，但是未更新左右儿子的值。
你在之前看到的 pushdownpushdownpushdown 函数，其实就是下传懒标记用的。（你为啥现在才说？）
算了来讲这个函数吧。
函数有 333 步：
1. 如果这个节点无懒标记，那么就返回。
2. 将父节点的修改加到左右儿子身上，更新现在的左右儿子的区间，同时给左右儿子也打懒标记。
3. 将自己的懒标记清空，代表这个懒标记已经打给儿子们了，不用再继续下传。
都说到这里了，来说下 pushdownpushdownpushdown 和 pushuppushuppushup 的区别， pushdownpushdownpushdown 就是把懒标记下传，是 fa→son ，而 pushuppushuppushup 是更新父亲的区间值（合并区间），是 son→fa 。
讲完函数了。
说下啥时候要用 pushdownpushdownpushdown 。
在 修改、查询 的时候要用。
修改时，如果当前区间被完全覆盖，直接返回，如果不是就先改掉左右儿子，就是 pushdownpushdownpushdown ，最后 pushuppushuppushup 合并区间。
查询也是如此，下传懒标记后递归返回左儿子加右儿子的值。
好啦，花开两朵，一支表完了。
回到线段树。
线段树2.0
有了对懒标记的了解，想必你一定知道该怎么写 P3373 【模板】线段树 2 了，那么就来写吧。
我们需要维护加乘查询 333 个操作，哎呀加写过了，查询也是，不讲，来讲讲乘。
其实也是开一个数组来统计，再开一个函数用来做区间乘，每次判断区间、下发懒标记、最后合并区间，其实和加的思路一样，这里沿用一句全站最强 管理员 Xylophone 的五字真言。
E 题 要 取 模 ！👊👊👊
别忘了取模！
P4588 [TJOI2018] 数学计算
妙妙题。
反正你们都会写 op=1op=1op=1 的，那就来看操作 222 吧。
我们先要知道线段树里放的是啥，比如说 tr[v]tr[v]tr[v] ，它放的是第 vvv 次操作的乘数，那操作 111 就是在第 vvv 个位置放这个乘数。
那么操作 222 ，就是除掉这个乘数，不就是把那个放被除掉的数的位置清空吗？/震惊/思考/炸开
由于线段树维护的是乘积，那么我们的 tr[1]tr[1]tr[1] ，也就是管 1−q1-q1−q 的这个乘积，就是我们的答案，所以对于 op=2op=2op=2 的情况，先撤销 pospospos 位置的乘数，更新完后输出 tr[1]tr[1]tr[1] 就行。
