线段树是什么？？线段树怎么写？？
如果你在考提高组前一天还在问这个问题，那么你会与一等奖失之交臂；如果你还在冲击普及组一等奖，那么这篇博客会浪费你人生中宝贵的5~20分钟。
上面两句话显而易见，线段树这个数据结构是一个从萌新到正式OI选手的过渡，是一个非常重要的算法，也是一个对于萌新来说较难的算法。不得不说，我学习了这个算法5遍左右才有勇气写的这篇博客。
但是，对于OI正式选手来说，线段树不是算法，应该是一种工具。她能把一些对于区间（或者线段）的修改、维护，从的时间复杂度变成。
第一部：线段树概念引入
第二部：简单(无pushdown）的线段树
第三部：区间+/-修改与查询
第四部：区间乘除修改与查询
线段树是一种二叉树，也就是对于一个线段，我们会用一个二叉树来表示。比如说一个长度为4的线段，我们可以表示成这样：
这是什么意思呢？ 如果你要表示线段的和，那么最上面的根节点的权值表示的是这个线段 的和。根的两个儿子分别表示这个线段中 的和，与 的和。以此类推。
然后我们还可以的到一个性质：节点 的权值 她的左儿子权值 她的右儿子权值。因为 的和就是等于 的和与 的和的和。
根据这个思路，我们就可以建树了，我们设一个结构体 ， 与 分别表示这个点代表的线段的左右下标， 表示这个节点表示的线段和。
我们知道，一颗从 开始编号的二叉树，结点 的左儿子和右儿子编号分别是 和 。
再根据刚才的性质，得到式子： 就可以建一颗线段树了！代码如下：
嗯，这就是线段树的构建，你可能会问为什么要开好几倍的内存去储存一条线段。这是因为我们还没有让这个过大的数组干一些实事，那么什么是实事呢？让我们进入下一部（在你看懂这一部的情况下）
其实这一章开始才是真正的线段树，我们要用线段树干什么？答案是维护一个线段（或者区间），比如你想求出一个 区间中， 这些元素的和，你会怎么做？朴素的做法是，这样固然好，但是算得太慢了。
我们想一种新的方法，先想一个比较好画图的数据，比如一个长度为 的区间，分别是 ，我们想求出第 项的和。按照上一部说的，我们要建出一颗线段树，其中点权（也就是红色）表示和：
然后我们要求 的和，我们先从根节点开始查询，发现她的左儿子1-2这个区间和答案区间1~3有交集，那么我们跑到左儿子这个区间。
然后，我们发现这个区间 被完全包括在答案区间 这个区间里面，那就把她的值 返回。
我们回到了 区间，发现她的右儿子 区间和答案区间 有交集，那么我们走到 区间
到了 区间，我们发现她并没有完全包含在答案区间 里面，但发现她的左儿子 区间和 区间又交集，那么久走到 区间
到了 区间，发现其被答案区间完全包含，就返回她的值 一直到最开始
区间的 区间的 ，我们知道了 区间和为 。
有人可能会说你这样是不是疯了，我拿脚都能算出 ，为什么这么麻烦？！
因为这才几个数，如果一百万个数，这样时间会大大增快。
我们总结一下，线段树的查询方法：
- 如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
- 如果这个区间的左儿子和目标区间有交集，那么搜索左儿子
- 如果这个区间的右儿子和目标区间有交集，那么搜索右儿子
写成代码，就会变成这样：
关于那几个if的条件一定要看清楚，最好背下来，以防考场上脑抽推错。
然后,我们怎么修改这个区间的单点，其实这个相对简单很多，你要把区间的第dis位加上k。
那么你从根节点开始，看这个dis是在左儿子还是在右儿子，在哪往哪跑，
然后返回的时候，还是按照的原则，更新所有路过的点
如果不理解，我还是画个图吧，其中深蓝色是去的路径，浅蓝色是返回的路径，回来时候红色的+标记就是把这个点加上这个值。
把这个过程变成代码，就是这个样子：
区间修改和单点查询，我们的思路就变为：如果把这个区间加上 ，相当于把这个区间涂上一个 的标记，然后单点查询的时候，就从上跑到下，把沿路的标记加起来就好。
这里面给区间贴标记的方式与上面的区间查找类似，原则还是那三条，只不过第一条：如果这个区间被完全包括在目标区间里面，直接返回这个区间的值变为了如果这个区间如果这个区间被完全包括在目标区间里面，讲这个区间标记
具体做法很像，这里贴上代码：
然后就是单点查询了，这个更好理解了，就是dis在哪往哪跑，把路径上所有的标价加上就好了：
区间修改，单点查询完整测试代码：
这里区间修改，单点查询的完整代码没有问题，已 AC 洛谷 P3368 【模板】树状数组 2：
为什么需要把路上的 加起来：
因为我们在进行区间修改的时候，若当前区间已经被完全包含在目标区间 里，直接将该区间 ，不需要再继续往下走了，类似 lazy 标记，所以单点查询的时候要再加上路径上的值（即原本的权值再加上经过的若干次修改的值才是这个单点的值）。
不知不觉，这第二章已经结束。这样的简单（原谅我用这个词）线段树，还可除了求和，还可以求区间最小最大值，还可以区间染色。
但是！这样的线段树展现不出来她的魅力，因为区间求和，树状数组比她少了一个很大的常数。二区间最值，ST表的那神乎其技 查询也能完爆她。这是为什么？因为线段树的魅力还没有展现出来，她最美丽的地方：pushdown还未展现于世，如果你已经对这一章充足的了解，并且能不看博客把洛谷上树状数组模板1、2都能写出来，那么请你进入下一部。
区间修改、区间查询，你可能会认为，把上一章里面的这两个模块加在一起就好了，然后你就会发现你大错特错。
因为如果对于 这个区间，你把 区间 ，相当于把节点 和 标记，但是如果你查询 时，你会发现你加的时没有标记的 节点和没有标记的 节点加上去，结果当然是错的。
那么我们应该怎么办？这时候 pushdown 的作用就显现出来了。
区间修改的时候，我们按照如下原则：
- 如果当前区间被完全覆盖在目标区间里，讲这个区间的 sum+k*(tree[i].r-tree[i].l+1)
- 如果没有完全覆盖，则先下传懒标记
- 如果这个区间的左儿子和目标区间有交集，那么搜索左儿子
- 如果这个区间的右儿子和目标区间有交集，那么搜索右儿子
然后查询的时候，将这个懒标记下传就好了，下面图解一下：
如图，区间 分别是 ，我们要把 区间 。因为 区间被完全覆盖，所以将其 ，并将紫色的 lazytage+1， 区间同理
注意我们处理完这些以后，还是要按照的原则返回，代码如下：
其中的pushdown，就是把自己的lazytage归零，并给自己的儿子加上，并让自己的儿子加上k*(r-l+1)
查询的时候，和上一章的几乎一样，就是也要像修改一样加入pushdown，这里用图模拟一下。我们要查询 区间的和，这是查询前的情况，所有紫色的代表lazytage
然后，我们查到区间 时，发现这个区间并没有被完全包括在目标区间里，于是我们就pushdown，lazytage下传，并让每个区间 sum 加上 。
然后查到 区间，发现被完全包含，所以就返 ，再搜索到 区间，发现被完全包含，那么直接返回 ，最后 就是答案
这里是代码实现：
好了，到了这里，我们就学会了用线段树进行区间加减操作，大家可以完成洛谷的线段树模板1.
如果这个线段树只有乘法，那么直接加入lazytage变成乘，然后tree[i].sum*=k就好了。但是，如果我们是又加又乘，那就不一样了。
当lazytage下标传递的时候，我们需要考虑，是先加再乘还是先乘再加。我们只需要对lazytage做这样一个处理。
lazytage分为两种，分别是加法的plz和乘法的mlz。
mlz很简单处理，pushdown时直接*父亲的就可以了，那么加法呢？
我们需要把原先的plz*父亲的mlz再加上父亲的plz.
然后加法和减法的函数同理，维护lazytage的时候加法标记一定要记得现乘再加。
值得一提的是，计算*2时一定要改成i<<1这样能解决很多时间，还有要开long long，还有，函数前面要加inline 我在其他OJ交这道题时，就因为没加inline 就被卡了，交了就过了。
其实，根号线段树和除法线段树一样。她们乍眼一看感觉直接用lazytage标记除了多少，但是实际上，会出现精度问题。
c++的除法是向下取整，很明显，（在向下取整的情况下），而根号，很明显根号（a）+根号(b)!=根号(a+b)那么怎么办？
第一个想法就是暴力，对于每个要改动的区间l~r,把里面的每个点都单独除，但这样就会把时间复杂度卡得比大暴力都慢（因为多个常数），所以怎么优化？
我们对于每个区间，维护她的最大值和最小值，然后每次修改时，如果这个区间的最大值根号和最小值的根号一样，说明这个区间整体根号不会产生误差，就直接修改（除法同理）
其中，lazytage把除法当成减法，记录的是这个区间里每个元素减去的值。
下面是根号线段树的修改过程：
然后pushdown没什么变化，就是要记得tree[i].minn、tree[i].maxx也要记得-lazytage。
附赠一份支持单点修改，区间取相反数，区间最小值，区间最大值的线段树代码
题目链接：https://www.luogu.com.cn/problem/P1505
题解：BZOJ 2157 「国家集训队」旅游（树链剖分，线段树，边权转点权）
最后，我们给几道模板题，再贴上代码：
P3374 【模板】树状数组 1
P3368 【模板】树状数组 2
P3372 【模板】线段树 1
P3373 【模板】线段树 2
这一篇文章讲解的非常详细易懂，所以存下来用来复习。
对原作者的图进行了重画，更加清晰，对排版也做了优化。
后面的模板代码也用的是我自己AC的代码。
注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧 ! 当然，也欢迎在讨论区指出此文的不足处，作者会及时对文章加以修正 !
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/857.html