线段树专题复习

今天的主题是线段树专题复习！
（什么？是昨天的？不听不听，只要我不说都不知道我鸽了一天！）
好了，言归正传，我们来看一下今天的知识点们吧。

Part 1 线段树自己

不想讲了，想看的移步其他博客
想看踢我，今天没时间了

Part 2 一些优化

ZKW线段树

俗称重口味线段树，是一种不用递归实现的线段树，常数和码量均远小于其他线段树，居家旅游良选
其实现原理利用了满二叉树的一些非常优美的性质，比如第 \(M+i\) 个结点在这个结构中一定代表第 \(i\) 个数字，将编号左移一位是父亲，异或以后是兄弟的美好特质，所以我们更新可以从底下向父亲更新，省去了向下的时间与空间。
代码示例：
单点修改

d[p=M+i]=value;
while(p<<=1) d[p]=d[p>>1]+d[p>>1|1];

而区间查询与以往有所不同，我们将查询\([i,j]\)的任务转化为查询\((i-1,j+1)\)的内容，然后结合图像：
假设我们现在要查询\([2,3]\)的和，我们便将其变为\((1,4)\)的和。
我们先找到1,4所对应的点，然后判断：
如果左端点对应着左儿子，则他的兄弟一定在区间内；右端点同理。这个时候异或找兄弟的好处就出来辣！log完美解决。
那么如果我们要区间修改要怎么办呢？我们提供两种方式。第一种，像普通线段树一样打上lazy标记。但这种我们一般不用，因为在非递归的情况下是极其麻烦的，具体可以移步度娘学习。
我们一般采取标记永久化的方式。
和区查一样，我们可以log地求出哪些点所在区间被我们所要修改的区间所包含。所以我们可以自下而上的以同样方法再来一遍。这个时候我们还需要记录我们在这里实际修改的值，方便打tag。查询的时候直接查就好辣！
强推。（主要是码量小的离谱）
缺点：部分操作有点麻烦，比较难以理解。对性质有部分要求（详见度娘）

空间回收

对于卡常的动态开点线段树有奇效。
也很简单，比如在合并线段树后，我们可以遍历一遍消失的线段树并把点重置后塞进一个栈里面，下次直接在栈里面取点而不是cnt++，节约大量空间。

其他想到再说。