线段树
重新整理一下线段树。
画线段树的网站 (Segment Tree) - VisuAlgo
线段树基础
线段树是每个节点代表一个区间构成的二叉树结构。
普通线段树就不说了。看看线段树还可以在那些地方做文章。
- 节点的编排顺序
直接编号会发现叶子节点的编号可能不连续，于是空间需要开 4 倍，但是线段树明明只有 2n 的节点。
动态开点即可解决，但是要存 ls 和 rs 要空间。
可以把一个节点的左儿子编号为 mid * 2，右儿子编号为 mid * 2 + 1。可以发现，每个区间的 mid 必然不同，所以不同区间的儿子编号必然不同，除了根节点，每个节点都是作为另一个节点的儿子出现，所以只用把根节点编号为 1 就没有区间编号重了。最大的 mid 是 n - 1（不给叶子的儿子编号），那么节点的最大编号为 \((n-1)*2-1=2*n-1\)，刚好是节点数，这样就没有浪费空间了。
- 递归改为非递归
众所周知，递归常数大。那么线段树是否可以非递归？这就是重口味 zkw 线段树。
总体来说，zkw 线段树与普通线段树最大的区别就是一个是递归一个是递推，然后 zkw 的编号方式也有一点点不同。
普通线段树叶子节点的编号很乱，zkw 的编号方式就略有不同。设 \(N=2^{\left \lfloor \log_2 n \right \rfloor }\) ，原序列第 i 个数对应的叶子节点为 \(i+N\)，然后新填两个节点，0 号节点和 n+1 号节点，然后在这上面建线段树。每个节点的父亲的编号都是儿子编号的一半。（如果不向 2 的次幂取整，就会导致 2 号节点的儿子是 4 和 5，但是这两个节点代表的可能不是连续的区间，感觉有点麻烦，如果是 N 是 2 的整数幂，那么最左边的路径上的数就都是 2 的整数倍，4 和 5 肯定就是同一层的连续区间了）
以一个 [1,4] 的区间为例，这是它的 zkw，
考虑如何不递归地定位区间。
有一个非常人类智慧的做法：对于区间 \([l,r]\) 找到 \(l - 1\) 和 \(r + 1\) 的根链，两条根链中间的大区间就是目标区间。这和递归线段树找到的区间是一摸一样的。然后改打标记打标记，改求和求和。这就是 zkw 线段树的核心思想。
这是它定位区间 [2,4] 的过程，最后找到了 5 号和 12 号节点，
以 modify 为例，
inline void mdf(int l, int r, ll a, ll b) {l += nn - 1, r += nn + 1, push_down(l), push_down(r); // 必须把从根往下的 tag 先铺平while(l ^ r ^ 1) {// l 和 r 的父亲节点不同，如果相同，l r 只有最后一位相差1if(~l & 1) upd(l ^ 1, a, b); // 如果是左儿子，就区间加右儿子if(r & 1) upd(r ^ 1, a, b); // 同上l >>= 1, r >>= 1, up(l), up(r); // 勿忘 up}up(r); while(l) up(l), l >>= 1; // 必须让上面的节点是对的
}
具体来说，
现在还有一个问题，就是祖先节点上可能有标记，但是用这个方法找区间的过程很有可能根本不会下放这些祖先节点的标记，所以开始找区间之前，要先从上到下把 \(l - 1\) 和 \(r + 1\) 的根链上的标记下传了。
现在还有一个问题，就是如果直接按照上述方法实现的话，求区间和的时候，这个区间可能还没被 push_up，也就是儿子节点的值在之前区间加了，但是祖先还没有更新。这其实只需要在找到区间以后一路 push_up 上去就行了。
比递归版快了 4 倍多，冲进了最优解第二页。
线段树2 提交记录
似乎还有一个两倍空间的混沌邪恶 zkw 写法，我研究了很久都没懂。如何写出简单又强势的线段树 - 洛谷专栏。
- 广义线段树
也就是不在中点处划分左右区间。
用处：可以在 mid 向上取 2 的整数次幂，这样复杂度也是对的，不过可拓展性弱，似乎没什么用。还用一个用处就是来出各种混沌邪恶题目，让你维护一个 xjb 乱划分左右区间的线段树。
然而 zkw 的这种思想非常的牛逼，有些时候甚至可以用来做广义线段树的邪恶题目：
例题：校门外歪脖树上的鸽子（某邪恶联考题）可以通过这个读题
大意是区间加区间求和的广义线段树，但是不下传标记，然后问你询问的答案在这种写法下是多少。
按照 zkw 的思想，找到 l - 1 和 r + 1 的根链，对于 l - 1 的根链，统计在它是左儿子时统计右儿子的答案，r + 1 的根链统计它是右儿子时左儿子的答案。如果你理解了 zkw 线段树，这是显然的。所以问题变成了树链打加法标记，树链求和，注意这里的树链求和指的是对区间标记乘上一个关于深度的系数后的和。然后就可以用数剖线段数做了。
猫树
参考：一种神奇的数据结构——猫树 - 洛谷专栏。
用处：满足结合律且支持快速合并的信息，如区间和，区间最大子段和。不过如果是可以差分的信息肯定就直接维护前缀然后差分来做了，猫树做的是合并容易差分难的静态问题。
复杂度：预处理 \(O(n\log n)\)，询问 \(O(1)\)，空间 \(O(n\log n)\)，单点修改 \(O(n)\) ，区间修改 \(O(n\log n)\) （区间修改相当于重构树）
可以看出，猫树不支持修改！
- 大体思路
想办法把询问区间拆成只拆成两个预处理过的区间，问题就在于如何在一个较短的时间内预处理区间信息，并且使得任意一个区间都能被分成两份预处理过的区间。
- 正文
其实就是分治，按照类似线段树的方法分治。对于线段树每个节点代表的区间，为了维护跨过 mid 的答案，维护一个左区间的后缀信息和右区间前缀信息。这样就能把任意询问区间分成两个被预处理过的区间。
以区间求和为例，
对于左边的区间，i 倒序遍历， \(f[i]=f[i+1]+a[i]\)
对于右边的区间，i 正序遍历， \(f[i]=f[i−1]+a[i]\)
因为除了长度为 1 的区间，定位任意一个区间在线段树递归过程中，一定有一次能被分成两个区间继续递归，这就是我们要找的位置。
（偷的图）例如红色区间，就会递归到这里的时候被处理。
但是如果直接递归地找到这个区间是 \(O(\log n)\) 的，但是通过人类智慧，我们发现这个区间正好就是询问的 l，r 对应的两个叶子节点它们的 LCA ！
这时候可以使用 \(O(1)LCA\) 解决问题，但是又通过人类智慧，我们发现这个节点的深度是 l 和 r 编号在 0-index 下二进制的最长公共前缀的长度。例如 001 和 011，lca 离叶子的距离是 2。
以SP1043 GSS1 - 静态最大子段和为例的代码，有一种非递归 NTT 的美感：
int n, m, a[N], H[N * 2];
struct node{int s, sf, pr, sb; // sb is max sum of subsequenceinline node operator + (const node & v) {node tmp; tmp.s = s + v.s, tmp.pr = max(pr, s + v.pr), tmp.sf = max(v.sf, v.s + sf), tmp.sb = max({sb, v.sb, sf + v.pr});return tmp;} // 注意加的顺序，没有交换律inline node (int x = 0) : s(x), sf(x), pr(x), sb(x) {}
}val[N], ct[Ln][N]; // val 是叶子节点
void bt() {For(i, 1, n) val[i - 1] = node(a[i]);For(i, 1, n * 2) H[i] = __lg(i);for(int h = 0, len = 2; len < n * 2; len <<= 1, ++ h) for(int l = 0, mid = (len >> 1) - 1, r = len - 1; mid < n - 1; l += len, mid += len, r += len) {r = min(r, n - 1);ct[h][mid] = val[mid], ct[h][mid + 1] = val[mid + 1];for(int i = mid - 1; i >= l; -- i) ct[h][i] = val[i] + ct[h][i + 1];for(int i = mid + 2; i <= r; ++ i) ct[h][i] = ct[h][i - 1] + val[i];}
} // 为了方便求 lca 节点，使用的是 0-index
inline int ask(int l, int r) {if(l == r) return a[l]; // 记得特判叶子节点-- l, -- r; return (ct[H[l ^ r]][l] + ct[H[l ^ r]][r]).sb;
}
注意：下标从 0 开始才方便找 lca