线段树

写在最前

我承认这个封面的线段树有点过于抽象，但是真的没有别的办法乐。

先引用一个大佬说的一句话：

什么是线段树？
如果你在考提高组前一天还在问这个问题，那么你会与一等奖失之交臂；如果你还在冲击普及组一等奖，那么这篇博客会浪费你人生中宝贵的5~20分钟。

显而易见，线段树是一个 OIer 从萌新过渡到正式 OIer 选手的标志性算法。

然而事实上，对于一个正式的 OIer 选手，线段树更应该是一个工具，所以……

线段树是世界上最好的数据结构！！！（超大声

线段树可以 $O(\log n)$ 的实现区间和，区间乘，区间最值，区间修改等操作，在很多题中都可以以略逊于正解的解法过掉。

核心思想

线段树就是将一个区间的答案分成两个子区间，需要修改的时候从最小的区间一路爬上去，需要查询的时候从上面一路往下找。
对，没了，就这么简单（（
实际上线段树的思想是非常好想的，以至于有的人可能在考场上自己想出来不是我，另一个大佬，难点其实是在实现以及右面的懒标记。

正常情况下我们存一棵树可能会用到存图的方法，或者是存每一个点的子节点，然而为了维护一串序列而真的建一个图实在是又臭又长过于屎山，不难想到父子两倍，即父节点为 $n$ 的话，子节点分别是 $2n$ 和 $2n+1$。

如果用这种方法的话不妨思考一下他所需的空间（以下非重点，可以酌情跳过）：

首先设这个序列长度为 $n$。
按照正常的逻辑，线段树的最下面是长度为 1 的区间，那么也就是说总共有 $n$ 个叶子节点。
不难发现总共有 $2n-1$ 个节点，然而事实上，我们在建树中，会浪费掉一些空间

实现

建树

（先鸽着，有空再来写（（