zkw 线段树瞎写
感觉最近太颓了，要学点亲民的东西，就整了下这个
其实就是非递归的线段树，然后稍微高明一点+卡常一点
可能会有错误，如果发现请往死里喷我
先说树的结构
众所周知线段树递归的原因一方面是在于难以确定点的编号，需要每一次重新从根开始搜索然后得到对应点的编号
因此我们要非递归，就要采用一种更为方便处理的编号手段
考虑一般都是用二进制，而这么处理的前置条件就是堆式建树
于是把序列大小先扩到 $2^k$
另外这里扩到 $2^k$ 之前要先把 $n$ 加一，具体原因后面会说
日报里直接多扩了一倍我是没想到的
那么剩下的点的编号就有很多优美的性质了，一会儿看操作讲
首先考虑建树
假设当前树的大小是 $2^{k+1}-1$
那么发现最后一层的 $2^k$ 个结点刚好就是扩充后的原序列
编号还是连续的，真好
然后考虑 $[1, 2^{k}-1]$ 这些点
显然可以迭代 pushup，就是从 $2^k-1$ 向前循环，然后 pushup 就行
显然这样顺序也是对的
然后考虑单点修改
发现一个位置的编号是确定的
发现一个点的父亲结点的编号一定是 $\lfloor{x\over 2}\rfloor$
于是直接确定修改点的位置，然后把所有祖先 pushup 就行
常数小
考虑单点查询
没标记的情况下甚至是 $O(1)$ 的
考虑区间查询
其实这部分的做法挺高妙的（（
考虑整两个指针，分别指向 $l - 1,r + 1$ 对应的结点（所以序列长度要加 1）
然后这两个指针不断往上跳直到父亲相同
在此之前，我们发现只要左指针的右儿子不是它跳上来的方向，就是我们要的结点
右指针同理
这个画图就能理解
而且这种自底向上的可能可能不访问所有结点
常数又变小了（（
区间修改
为了减小常数，考虑使用标记永久化（不然 zkw 线段树就失去意义了？）
显然可以用类似区间查询的方法，而且发现我们所有访问到的结点 pushup 即可
发现最后终止状态时，可能还要往上遍历一些点然后 pushup
这里显然直接跳就行
同理区间查询也得跳到根回收标记
空间卡常
这部分多半是口胡的，但感觉挺对的（（
上面说了 zkw 线段树不卡常就失去意义了（？？？）
因此我们继续卡常
我们发现一个性质：t[x] = t[x << 1] + t[x << 1 | 1]
然后我们有时会打 tag ，又要新的空间
这不好，我们好像没有充分利用空间
发现一个性质，如果我们是 pushdown 式的打标记，那么一个 有标记 的结点 pushdown 之后，其儿子的值之和一定变了
因此若 t[x] != t[x << 1] + t[x << 1 | 1] 就是没有 pushdown
所以标记可以直接打在结点上（（
欢迎各位大佬来卡掉这个东西，卡掉就能出成一道构造 / 提答 / 结论题了
简单总结一下，上面也说过，这东西除了卡常就没什么用，还不见得有原版线段树好写
实战中一般不会有人特意放 zkw 过然后卡递归线段树
感觉实用性甚至不如什么猫树
不过思想还可以，值得学学