小粉兔 @ 2018-07-28 17:41:36
这是对zhu1679514458的问题：线段树数组空间开多大比较合适？的一个解答。
这里的线段树指的是，每个节点都有0或2个孩子的二叉树。
编号为x的节点的左孩子(如果存在的话)的编号为2x，右孩子的编号为2x+1。而根节点的编号一般为1。
一棵拥有x个叶子节点的线段树被称为x-线段树。
除此之外，一棵x-线段树(x>1)还需要满足其左子树为一棵\lfloor x/2\rfloor-线段树，其右子树为一棵\lceil x/2\rceil-线段树。
有上述条件可以唯一确定一棵x-线段树(x>0)的形态。
接下来要探讨的是：一棵n-线段树的节点中的最大的编号id_{\max}，与n有什么关系。因为最大的编号和在程序中实现时所用的数组大小以及使用的内存大小有密切的联系。
有人认为id_{\max}小于4n，有人认为id_{\max}不会超过5n。有人提出可以证明id_{\max}\leq 3n+1。
真相到底是什么？
① 线段树的高度和形态
$2$-线段树高度为$2$。
$3,4$-线段树高度均为$3$。
$5\sim 8$-线段树高度均为$4$。
$9\sim 16$-线段树高度均为$5$。
可以看出，一棵$x$-线段树的高度为$\lceil \log_2x\rceil +1$或等于$\lceil \log_2 2x\rceil $。
根据此，结合二叉树的简单性质，我们可以得到一个线段树$id_{\max}$的比较松的上估计：$id_{\max}\leq 2^{\lceil \log_2 2x\rceil}-1< 4n-1\leq 4n-2$。证实了$id_{\max}$小于$4n$的断言。
而观察线段树的形态可以得出另一个结论：一棵线段树除了最后一层，其他层都是满的。
据此，有人提出了另一个声称更紧的估计：$2^{\lceil \log_2 x\rceil}+n-1$。并据此计算得出$id_{\max}\leq 3n+1$的结论。然而这是**错误**的。因为这个估计依赖于一个错误的假设：线段树最后一层的节点是靠左连续的，或称“完全二叉树”的形态。
实际上，在$n=36$时，$n$-线段树的$id_{\max}$就等于$113>3n+1$。这是不满足估计的最小的$n$。
那么什么界才是精确的呢？线段树的数组到底要开多大呢？
## ② 线段树的结构
只要知道了$n$-线段树的$n$值，就能确定线段树的形态。只要知道了线段树的根节点编号，就能确定线段树的$id_{\max}$是多少。
那么任何快速地计算$id_{\max}$呢？考虑以下算法：
>若线段树为$1$-线段树，那么其$id_{\max}$为根节点编号。
>若线段树为$x$-线段树$(x>1,x\equiv 0(mod\;2))$，且根节点编号为$y$，那么其$id_{\max}$为根节点编号为$2y+1$的$x/2$-线段树的$id_{\max}$。
>若线段树为$x$-线段树$(x>1,x\equiv 1(mod\;2))$，根节点编号为$y$，且$(x+1)/2$-线段树的深度等于$(x-1)/2$-线段树的深度，那么其$id_{\max}$为根节点编号为$2y+1$的$(x-1)/2$-线段树的$id_{\max}$。
>若线段树为$x$-线段树$(x>1,x\equiv 1(mod\;2))$，根节点编号为$y$，且$(x+1)/2$-线段树的深度**不**等于$(x-1)/2$-线段树的深度，那么其$id_{\max}$为根节点编号为$2y$的$(x+1)/2$-线段树的$id_{\max}$。
不难证明上述算法可以在$\Theta(\log_2 n)$的时间复杂度内计算出正确的结果。
这是一个可接受的算法，接下来我用 c++ 语言实现了计算$id_{\max}$的函数，并用它计算了$n$与$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(10^6)$内，$id_{\max}$最大能达到$3.992\cdots$倍的$n$那么大。这的确不超出我们的预期。
------------
所以结论是什么？线段树的数组到底要开多大？
结论就是：线段树开$4$倍总没错。你也可以算出一个$n$-线段树$(n\leq k\times 10^5)$的$id_{\max}$最大能到多少。更简单且内存占用不大的方法是算出第一个比$2n$大的$2$的次幂，并把数组开到那么大。
### 其实有一种方法可以在近乎$O(1)$的时间内算出$n$-线段树的$id_{\max}$，只涉及位运算，你能想到吗？