线段树时空复杂度

常识

单点操作单 log．

序列线段树空间 4 倍常数 \(O(n)\)．

问题

大家都知道线段树区间操作是一个 log 复杂度的，但是如何证明呢？它为什么会将区间拆成 log 个区间呢？它会有几倍常数？带懒标记时有几倍常数？为什么可持久化时能下传懒标记？

区间操作

void seg(x,y,p=1,l=1,r=n){
    if(x<=l&&r<=y) return ... ;
    if(x<=mid) seg(x,y,LS);
    if(mid< y) seg(x,y,RS);
}

递归的过程不易分析，我们考虑自下往上合并来证明区间会被拆成 log 个区间．

最开始，可以认为 \([x,y]\) 的叶子都会被访问，此时区间会被拆成 \(O(n)\) 个区间．

考虑合并两个有相同父亲的点，因为可能有些节点分布在最下面一层，即第 \(k\) 层，有些分布在第 \(k-1\) 层．显然一开始在第 \(k-1\) 层的不会合并，因为它另一个兄弟节点下面必然还有一层，要不然就不是第 \(k-1\) 层而是第 \(k\) 层了，其实就是长度为 3 的线段树的形态．考虑在第 \(k\) 层的节点，显然只有两端可能不会合并，且以后再在更高层合并它们也不会合并，直接成为最终合并完的区间．注意到此时点数将最坏减少 \(n/3\)，因为只有第 \(k​\) 层的中间节点会合并．

然后继续合并处理只有第 \(k-1\) 层的点，注意此时只有第 \(k-1\) 层的点．同上，只有两段可能不会合并，并成为最终合并完的区间，此时点数将变为原来的一般．

继续一直合并下去，只会合并 log 次，每次产生 \(0/1/2\) 个最终拆分的区间那么就是 \(O(\log n)\)．

但是线段树会从根向下找到这些区间，复杂度取决一些到根的链并的长．其实这些链并主要是直径，我们关注最左和最右的拆分区间节点，它们到根的链的并会成为最外层的一圈．可以发现，在这两个点之间的关键点其实距离这条直径只有 1 的距离，也就是它们的父亲一定是链并的最外一圈的点．因为如果不是这样，就意味着该点的父亲不在最外圈，那么它另一个儿子必然存在，又因为它们都是夹在最远的关键点之间的，父亲的两个儿子必然会合并上来变成极大区间，一直会并到不能并了，也就是到了最外圈才停止．最外圈是 \(O(\log n)\) 的，有两倍常数，中间节点到直径是 \(O(\log n)\) 的，合起来是 3 倍常数 \(O(\log n)​\)．

至于懒标记，考虑最坏是每次都 pushdown 大概合起来是 时间 4 倍常数 \(O(\log n)\)．

可持久化

可持久化一下，每次 pushdown 其实也是 change，都要新建节点，每次最坏会变成 4 倍空间常数．注意到我们可能在 pushdown 时新建了一个节点，然后 change 时再复制时可能直接对着模板版本 q 复制了，之前 pushdown 的就没了．我们可以 change 前改根节点，change 时自己复制，可是会产生一堆垃圾节点浪费空间，有时在需要连续修改一个版本也会产生大量垃圾节点浪费空间．这时可以使用绝招，我们发现其实我们是复制了复制过的节点，但是我们完全没有必要复制．注意此时不能直接 change 不复制，因为路径复制时仍然可能走到之前的公共节点上．诶？那我们就只复制旧节点不久行了么！我们引入新标记，记录节点在一个阈值内才需要复制，就能很优秀地解决这个问题了．现在只做区间可持久化就是 2 倍常数了，也就是空间 6 倍常数 \(\log n\)．