搬运自我和 codeforces 神仙们的一点小讨论.

首先一个共识是, 可持久化数据结构对空间十分敏感, 若把持不好容易出很大的问题.

所以这里会有一种 solution, 就是使用 stl 的 dynamical allocation (std::vector), 但是实现过的人都知道在修改时对进入 left child 还是 right child 的讨论会导致 std::vector 的内存地址发生改变, 从而导致程序挂掉. 当然我们可以用提前获取并储存递归结果之类的方法来提前取得正确的 address.

另外一条途径是使用 std::deque, 它的优点是不会在分配内存的时候挪动地址, 所以可以像写正常线段树一样编码. 而且 std::deque 的内存会更小, 缺点很明显, 效率比 std::vector 低! random case 几乎是 std::vector 的两倍.

所以需要权衡, 但是也比被提前算 memory pool 大小搞错 re 好 ?.

还有一个比较 useless 的 component, link, 可以做参考, 没有什么实际价值.

参考实现, std::vector, std::deque.