一种节省空间的基于递归的线段树实现

使用先序遍历的节点访问顺序重新给左右儿子编号,大大节省了空间

自古以来,实现线段树所需要的数组空间大小有着比较激烈的争论。一种基于递归的线段树实现认为至少需要 $\mathcal {O}(4n)$ 的空间,而另一种基于直接循环的方法认为其实只需要 $2n-1$ 的空间。关于为什么基于递归的方法需要 $\mathcal {O}(4n)$ 的严格证明可以去网上搜索,或者 这里 提供了一个简易的证明方法。总的来说,基于递归的线段树实现起来更加直观,但由于 dummy node 的存在造成了空间的浪费。而基于直接循环的方法对实现的要求更高。本文介绍了一个基于递归的线段树实现,通过改变每个节点的左右儿子的编号高效的利用了空间,使得基于递归的线段树也只需要 $2n-1$ 的空间。另外,关于基于循环的线段树实现方法,可以参考 这篇博客

阅读更多