一种紧凑的线段树存储方法

发现马老师的线段树只用两倍空间, 他说这是 <高级数据结构> 上介绍的一种奇妙的方法. 这种方法用很小的代价实时计算出线段对应的编号, 相比堆式存储, 可以省掉一个参数. 空间紧凑了, 寻址的时间缩短, 程序也跑得更快了.

秉承着 "让常数优化成为一种习惯" -_-b 学习一下, 顺便对这种方法的正确性给个证明. <高级数据结构> 上写的是错的...... 如图. 所有编号从0开始. 闭区间的左子区间是, 右子区间是, . 蓝色是中序遍历的时间戳.

中序遍历的时间戳可以这样计算: (l+r) | (l!=r), 我们用两步来说明这一点:

1. 最小编号是0. 显然.

2. 左子树的最大编号 + 1 = 根结点编号 = 右子树最小编号 - 1. 左子树的最大编号是, 右子树的最小编号是, 只需说明. 当为偶数, , 按位或后编号+1. 当为奇数, 由于是右移再左移的结果, 两者最低位相反, 其余位相等.

按照中序遍历的顺序运用数学归纳法, 得证.

所以我们用中序遍历的时间戳给线段树的结点编号.