请问有人可以写一下可持久化后缀平衡树的代码或说一下它的具体思路吗?
我目前卡在了如何维护 comp 函数。(日报的那篇)
如果用 O(1) 比较点那种方法需要维护点 x 去掉首字母后的字符串所代表的节点 y。但有可能在平衡树中 x 没变但是 y 变了。那有两种方法来维护:
- 把 x 也改变。这样显然空间会炸。
- 再用一棵平衡树,存下 x 所对应的所有 y,查询时用时刻来二分到 y。这样可以保证空间 O(nlogn)。(应该没算错吧…)
但是第二种方法的缺点在于我的 comp 函数需要 O(logn) 才能定位到 y,而且重构时的点数有 O(logn) 个,每一个都要 O(logn) 来插入。那么时复为 O(nlog2n),与理论时复 O(nlogn) 不符。
那么请问我是哪个地方想错了还是维护方法出错?请大佬们说一下正确的方法。