线段树优化空间的方法

NY_Wet · 2024-05-17 14:37:38 · 算法·理论

常规的线段树，如果不动态开点，一般需要 4n 个结点，其中 n 是维护的序列的长度。本文将介绍一种结点编号方法，只需要 2n-1 个结点，而且不用动态开点，优化了空间。

线段树是一棵二叉树，所以可以用先序遍历给结点标号，如图所示：

圆圈内的两个数字为该结点表示的区间，圆圈外的红色数字为该结点的编号。

若一个结点的编号为 p，该结点表示区间的左端点为 l，右端点为 r，则它的左儿子编号为 p+1，右儿子编号为 p+size_l+1，其中 size_l 表示左子树的大小。由于线段树的结点总数等于对应序列长度的两倍减一，所以 size_l=2\times (\lfloor \frac{l+r}{2}\rfloor-l+1)-1，整理式子，得到 p 得右儿子编号为 p+2\times (\lfloor \frac{l+r}{2}\rfloor-l+1)。

只要把结点对应的区间传入相应的函数，即可实现空间的优化。

具体实现（P3372）