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

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

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

要回答为什么 dummy node 的存在导致了基于递归的线段树需要 $\mathcal {O}(4n)$ 的空间,我们得先了解一下传统的实现方式。

传统实现

我们考虑一个恰好为 $2^k$ 的序列,由于长度恰好为 2 次幂,因此线段树的每个节点的长度恰好是它父亲节点的一半,因此最后形成的线段树是一颗满二叉树。比如下图是一颗长度为 8 的序列组成的线段树,维护了区间 $min$ 的查询。
一颗满二叉树组成的线段树

我们还可以注意到,如果根节点的编号是 1 的话,那么对于每个非叶子节点 $x$,它的左儿子是 $2x$,右儿子是 $2x+1$。整个线段树的节点个数是 $2n-1$。我们的 build () 函数可以大致这么实现。

1
2
3
4
5
6
7
8
9
10
11
12
template<typename Container>
T build(const Container &a, int cur, int left, int right) {
if (left == right) {
return tree [cur] = a [left];
}
int mid = (left + right) >> 1; // 划分区间
int lc = cur << 1; // 左儿子的编号
int rc = cur << 1 | 1; // 右儿子的编号
T l = build (a, lc, left, mid); // 遍历左子树
T r = build (a, rc, mid + 1, right); // 遍历右子树
return tree [cur] = combine (l, r);
}

那么很自然地我们就会想到,如果对于一个长度不是 $2^k$ 的序列,上述结论是否依然成立呢?答案是显然的,很自然地,我们依然可以将每个非叶子节点的左儿子设置成 $2x$,右节点设置成 $2x+1$。那么对于一颗长度为 10 的序列组成的线段树,就会变成下图所示
非满二叉树组成的线段树

我们大致可以得出两个结论。第一,如果你去统计这颗线段树的节点个数,你会发现它依然是 $2n-1$。这个是很容易理解的,因为任何一个 $[1,n]$ 的序列,它一定有 $n-1$ 个分割点,那么要全部变成长度为 1 的叶子节点,它必然要经历 $n-1$ 次分割,加上叶子节点的个数 $n$,总节点自然就是 $2n-1$ 了。因此我们可以得出一个重要结论

长度为 $n$ 的序列会形成 $2n-1$ 个节点个数的线段树。

这个结论非常重要,之后我们还会用到,因此需要暂时把它记住。至于第二个结论,就是从图中我们发现有些节点是不存在的,比如 18-23 号节点,另外 24 和 25 号节点的编号实际上已经超过了 $2n-1$,这就是为什么本文开头提到基于递归的线段树需要 $\mathcal {O}(4n)$ 的空间的原因。

那么既然线段树的总节点树就是 $2n-1$,我们是否可以通过某种办法,把这些节点的编号重新映射一下,使得线段树中每个节点的编号都落在 $2n-1$ 内,这样我们就不需要开 $\mathcal {O}(4n)$ 的空间了,并且每个空间也能充分得到利用了,岂不美哉?

按照先序遍历重新编号节点

答案是肯定的,比如我们可以按照整棵树的节点访问顺序,也就是先序遍历的顺序给节点重新编号。
按照先序遍历进行编号的线段树

我们不再使用 $2x$ 和 $2x+1$ 给左右儿子编号了,而是使用从根节点开始,实际访问每个节点的顺序,也就是先序遍历的顺序给每个节点编号,或者再换一个说法,就是 dfs 的访问顺序。这样每个节点在数组空间中的排列就是紧密的了,那我们就只需要开 $2n-1$ 的数组大小就能完成整颗线段树的构建了。

那么说了那么多,问题来了。我在递归遍历的时候怎么求出左右儿子的编号呢?本来只要 $2x$ 和 $2x+1$ 就能很容易的求出了,现在这么一搞,我怎么知道左右儿子的编号是多少呢?难不成我还要搞一个全局计数器去记录节点编号吗?

并不需要。首先我们来看左儿子的编号,因为现在的编号顺序就是实际的访问顺序了,而左儿子恰恰就是要访问的下一个节点,那么显然,左儿子的编号就是 $x+1$ 了。那么右儿子呢?其实也很简单,我们注意到,如果左儿子划分了 $[l,r]$ 这个区间,那么实际上左儿子就是一颗划分了 $[l,r]$ 序列的子线段树。还记得之前的结论吗?$[l,r]$ 的区间长度是 $r-l+1$,划分了 $r-l+1$ 的长度会形成 $2 (r-l+1)-1$ 个节点个数。因此如果当前节点是 $x$,它的左子树就有 $2 (r-l+1)-1$ 个节点,而右儿子恰好就是左子树全部遍历完之后的下一个节点,因此右儿子的节点编号就是 $x+2 (r-l+1)-1+1$,也就是 $x+2 (r-l+1)$ 了。而 $l,r$ 这些值在我们遍历的时候都是自然维护了,所以计算左右儿子都不需要引入任何额外的变量。build () 代码如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename Container>
T build (const Container &a, int cur, int left, int right) {
if (left == right) {
return tree [cur] = a [left];
}
int mid = (left + right) >> 1;
- int lc = cur << 1;
- int rc = cur << 1 | 1;
+ int lc = cur + 1 ;
+ int rc = cur + ((mid - left + 1) << 1);
T l = build (a, lc, left, mid);
T r = build (a, rc, mid + 1, right);
return tree [cur] = combine (l, r);
}

注意到相比之前的代码,我们仅仅是修改了左右儿子的节点编号 lcrc 而已。

结论

虽然开 $4n$ 的空间实际上并不会有什么太大的影响,但使用新的节点编号方法并不会增加任何代码的复杂度,相反还能节省一半的空间,因此在我看来这种方式更加优雅。从另一个角度来说,将线段树的数组空间排列紧密化可以更好地利用局部性原理,在某种意义上对性能有一定的提升。

参考

上述思想参考了 tourist 大神的线段树代码,在此默默表示感谢。

评论