社区讨论

Re：**线段树**的数组开**这么大**才是最合适的

小小粉兔管理员
学术版参与者 20已保存回复 24

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
24 条
当前快照
1 份
快照标识符
@mi6v70vq
此快照首次捕获于
2025/11/20 11:21
4 个月前
此快照最后确认于
2025/11/20 15:58
4 个月前
查看原帖
这是对zhu1679514458的问题：线段树数组空间开多大比较合适？的一个解答。
这里的线段树指的是，每个节点都有00或22个孩子的二叉树。
编号为xx的节点的左孩子(如果存在的话)的编号为2x2x，右孩子的编号为2x+12x+1。而根节点的编号一般为11。
一棵拥有xx个叶子节点的线段树被称为xx-线段树。
除此之外，一棵xx-线段树(x>1)(x>1)还需要满足其左子树为一棵⌊x/2⌋\lfloor x/2\rfloor-线段树，其右子树为一棵⌈x/2⌉\lceil x/2\rceil-线段树。
有上述条件可以唯一确定一棵xx-线段树(x>0)(x>0)的形态。
接下来要探讨的是：一棵nn-线段树的节点中的最大的编号idmax⁡id_{\max}，与nn有什么关系。因为最大的编号和在程序中实现时所用的数组大小以及使用的内存大小有密切的联系。
有人认为idmax⁡id_{\max}小于4n4n，有人认为idmax⁡id_{\max}不会超过5n5n。有人提出可以证明idmax⁡≤3n+1id_{\max}\leq 3n+1。
真相到底是什么？

① 线段树的高度和形态

11-线段树高度为11。
22-线段树高度为22。
3,43,4-线段树高度均为33。
5∼85\sim 8-线段树高度均为44。
9∼169\sim 16-线段树高度均为55。
可以看出，一棵xx-线段树的高度为⌈log⁡2x⌉+1\lceil \log_2x\rceil +1或等于⌈log⁡22x⌉\lceil \log_2 2x\rceil 。
根据此，结合二叉树的简单性质，我们可以得到一个线段树idmax⁡id_{\max}的比较松的上估计：idmax⁡≤2⌈log⁡22x⌉−1<4n−1≤4n−2id_{\max}\leq 2^{\lceil \log_2 2x\rceil}-1< 4n-1\leq 4n-2。证实了idmax⁡id_{\max}小于4n4n的断言。
而观察线段树的形态可以得出另一个结论：一棵线段树除了最后一层，其他层都是满的。
据此，有人提出了另一个声称更紧的估计：2⌈log⁡2x⌉+n−12^{\lceil \log_2 x\rceil}+n-1。并据此计算得出idmax⁡≤3n+1id_{\max}\leq 3n+1的结论。然而这是错误的。因为这个估计依赖于一个错误的假设：线段树最后一层的节点是靠左连续的，或称“完全二叉树”的形态。
实际上，在n=36n=36时，nn-线段树的idmax⁡id_{\max}就等于113>3n+1113>3n+1。这是不满足估计的最小的nn。
那么什么界才是精确的呢？线段树的数组到底要开多大呢？

② 线段树的结构

只要知道了nn-线段树的nn值，就能确定线段树的形态。只要知道了线段树的根节点编号，就能确定线段树的idmax⁡id_{\max}是多少。
那么任何快速地计算idmax⁡id_{\max}呢？考虑以下算法：
若线段树为11-线段树，那么其idmax⁡id_{\max}为根节点编号。
若线段树为xx-线段树(x>1,x≡0(mod  2))(x>1,x\equiv 0(mod\;2))，且根节点编号为yy，那么其idmax⁡id_{\max}为根节点编号为2y+12y+1的x/2x/2-线段树的idmax⁡id_{\max}。
若线段树为xx-线段树(x>1,x≡1(mod  2))(x>1,x\equiv 1(mod\;2))，根节点编号为yy，且(x+1)/2(x+1)/2-线段树的深度等于(x−1)/2(x-1)/2-线段树的深度，那么其idmax⁡id_{\max}为根节点编号为2y+12y+1的(x−1)/2(x-1)/2-线段树的idmax⁡id_{\max}。
若线段树为xx-线段树(x>1,x≡1(mod  2))(x>1,x\equiv 1(mod\;2))，根节点编号为yy，且(x+1)/2(x+1)/2-线段树的深度不等于(x−1)/2(x-1)/2-线段树的深度，那么其idmax⁡id_{\max}为根节点编号为2y2y的(x+1)/2(x+1)/2-线段树的idmax⁡id_{\max}。
不难证明上述算法可以在Θ(log⁡2n)\Theta(\log_2 n)的时间复杂度内计算出正确的结果。
这是一个可接受的算法，接下来我用 c++ 语言实现了计算idmax⁡id_{\max}的函数，并用它计算了nn与idmax⁡id_{\max}的关系：
CPP
#include<cstdio>
int Dep[100000001];
int max(int i,int j){return i>j?i:j;}
void Init(){
	Dep[1]=1;
	for(int i=2;i<=100000000;++i)
		Dep[i]=max(Dep[i>>1],Dep[i+1>>1])+1;
}
int GetNum(int RootNum,int Size){
	if(Size==1) return RootNum;
	if(!(Size&1)) return GetNum(RootNum<<1|1,Size>>1);
	if(Dep[Size>>1]!=Dep[Size+1>>1])
		return GetNum(RootNum<<1,Size+1>>1);
	return GetNum(RootNum<<1|1,Size>>1 );
}
int main(){
	Init();
	double Max=0;
	for(int i=1;i<=1000000;++i){
		int id=GetNum(1,i);
		double R=1.*id/i;
		if(R>Max) Max=R;
//		printf(" # %d : %d , %.15lf\n",i,id,R);
	} 
	printf("%.15lf\n",Max);
	return 0;
}
输出的结果是3.992197027439024，这意味着在1000000(106)1000000(10^6)内，idmax⁡id_{\max}最大能达到3.992⋯3.992\cdots倍的nn那么大。这的确不超出我们的预期。
所以结论是什么？线段树的数组到底要开多大？
结论就是：线段树开44倍总没错。你也可以算出一个nn-线段树(n≤k×105)(n\leq k\times 10^5)的idmax⁡id_{\max}最大能到多少。更简单且内存占用不大的方法是算出第一个比2n2n大的22的次幂，并把数组开到那么大。

其实有一种方法可以在近乎O(1)O(1)的时间内算出nn-线段树的idmax⁡id_{\max}，只涉及位运算，你能想到吗？

回复

共 24 条回复，欢迎继续交流。

正在加载回复...