平衡树
前言
update 2025.09.28 啊?我在学习平衡树的时候居然没有写博客吗?写了一个很简略的可持久化平衡树,并且没有代码。
可持久化平衡树
参考 OI-Wiki。
一般使用 fhq 平衡树。
流程
在 split 的时候复制节点。
其他类似可持久化线段树。注意标记也要可持久化哦。
空间复杂度计算
空间复杂度 \(O(n \log n)\)。
因为单次 split 期望需要复制 \(\log n\) 个节点。
经验
例题:#SS250927C. 死にゆく季節でぼくは(season)。
代码咕咕。