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