线段树究竟为何要开四倍空间，什么时候要？——严格数学推导证明

引入

众所周知，假如我们建线段树是很传统的非叶节点 $i$ 有孩子 $2i, 2i+1$，则一般需要开 $4$ 倍空间保险。所有人初学线段树时肯定都铭记了这一点。

但是仔细想想总感觉非常奇怪，到底什么时候真的会干到那么大呢？或者说，到底什么长度会导致需要四倍空间呢？所以今天我们来探讨下线段树占用空间的理论值。

暴力分析

首先我们定义一个函数 $f(x)$，表示通过如下方式建立的长度为 $x$ 的线段树，所占用的最大数组下标。

注意，这里研究的是为了容纳最大数组下标需要开多长的数组，而不是线段树实际拥有多少个节点。无论如何划分，一棵拥有 $x$ 个叶节点的满二叉树都只有 $2x-1$ 个节点；真正导致我们需要开近 $4x$ 空间的，是 $i,2i,2i+1$ 这种编号方式在数组中留下的空位。

void build(int k,int l,int r)
{
    if(l==r)
    {
        //do something
        //e.g. tree[k]=a[l]
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    //do something
    //e.g. tree[k]=tree[k<<1]+tree[k<<1|1]
}

例如 $f(6)=13$，代表长度为 $6$ 的线段树，在数组存储中最大下标为 $13$，如图所示：

代码与图均来自 P6025，非常感谢此题提供的资源与帮助。

那么很显然我们可以写一个暴力枚举来计算 $f(x)$：

int f(int l,int r,int p=1){
    if (l==r) return p;
    int mid=(l+r)/2;
    return max(f(l,mid,p*2),f(mid+1,r,p*2+1));
}

思路就是每次递归取左右子树数组下标最大的那一个。

因为我们想要研究开几倍空间这个事，我们只关心 $\frac{f(x)}{x}$ 的值，写个代码看看是怎么个事：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int f(int l,int r,int p=1){
    if (l==r) return p;
    int mid=(l+r)/2;
    return max(f(l,mid,p*2),f(mid+1,r,p*2+1));
}
signed main(){
    double maxn=0;
    for (int i=1;i<=10000;i++){
        int fx=f(1,i);
        cout<<"x: "<<i<<" f(x): "<<fx<<" f(x)/x: "<<(double)fx/(double)i<<endl;
        maxn=max(maxn,(double)fx/(double)i);
    }
    cout<<maxn;
}

输出为：

...
x: 9998 f(x): 32753 f(x)/x: 3.27596
x: 9999 f(x): 32753 f(x)/x: 3.27563
x: 10000 f(x): 32753 f(x)/x: 3.2753
3.93811

可以发现老祖宗的结论还是很正确的。有不少情况下比值都在 $3$ 以上，最坏的已经达到了 $3.9$ 多了，看来开四倍空间还是非常有必要的。

但是，具体是为什么呢？有没有严格证明？

试图优化 $f(x)$

压下参数

我们发现，长度一样的子树建出来结构是一模一样的，与左右端点无关。因此我们可以把函数的 int l,int r 改成 int len，只关心长度即可。那么左右子树的长度就会变成 $\lfloor \frac{len+1}{2} \rfloor, \lfloor \frac{len}{2} \rfloor$。因为显而易见的，在 $len$ 为偶数时两子树长度相同，否则左子树会长 $1$。

int f(int len,int p=1){
    if (len==1) return p;
    return max(f((len+1)/2,p*2),f(len/2,p*2+1));
}

优化成 $O(\log_2 n)$

如果自己多画几个图，或者稍微动脑筋想一想，就会发现大多数情况下，占用最大下标的那个节点会出现在右子树。毕竟右边可是 $2i+1$ 嘛，比左子树会大点。

但是仍然有某些情况它在左子树，比如 $3$ 就是。

[1,2,3]
[1,2],[3]
[1],[2]

那么什么时候会取左子树呢？如上文所述，左子树在长度为奇数时会长 $1$，正是因为这个特性导致我们可能会选左子树。

结论是：当长度为 $2^k+1, k\in\mathbb Z^+$ 时，我们需要取左子树。这个数在二进制下为形如 $1000\dots0001$ 这样的数，所以下文的讨论将更多在二进制下进行。

证明也非常好理解。设左右子树的长度分别为

当两个子树深度相同时，最深层节点的二进制下标长度也相同，而右子树节点在当前位上是 $1$，左子树节点在当前位上是 $0$，因此最大下标肯定出现在右子树。

只有当左子树比右子树深一层时，最大下标才会出现在左子树。这个情况恰好发生在右子树已经是一个拥有 $2^{k-1}$ 个叶节点的满二叉树，而左子树在它的基础上又多出一个叶节点时。此时

所以

反过来，当 $len=2^k+1$ 时，左右子树长度确实分别为 $2^{k-1}+1$ 与 $2^{k-1}$，左子树恰好多出一层，因此一定选择左子树。这样便证明了结论。

所以我们代码可以优化成每次自己手动选择左子树右子树，且只用选一个：

int f(int len,int p=1){
    if (len==1) return p;
    if (len&1&&!((len-1)&(len-2))) return f((len+1)/2,p*2);
    return f(len/2,p*2+1);
}

优化成 $O(1)$ 数学公式

有没有办法可以把上述的过程通过公式模拟出来呢？我们先看一个计算的例子（来源：CDFLS_mao_zx 的 P6025 题解）：

当前节点下标=00000001 当前长度=1001011
当前节点下标=00000011 当前长度=0100101
当前节点下标=00000111 当前长度=0010010
当前节点下标=00001111 当前长度=0001001
当前节点下标=00011110 当前长度=0000101
当前节点下标=00111100 当前长度=0000011
当前节点下标=01111000 当前长度=0000010
当前节点下标=11110001 当前长度=0000001

我们发现，$f(x)$ 的值仅与 $x$ 在二进制下最高位与次高位有关！不过光看例子当然不能算证明，下面我们来严格推一下。

注意一下，当 $x=2^k,k\in\mathbb Z_{\ge 0}$ 时，不存在次高位的 $1$，应当特判返回 $2x-1$（此时是满二叉树）。接下来假设 $x$ 至少包含两个二进制下的 $1$。

设 $x$ 的最高位与次高位位置分别为 $h_1,h_2$，则一定可以写成：

我们模拟下递归是怎么走的：

1. 在当前 len 不是 $2^k+1$ 时，我们选择右节点。这个时候当前下标会左移一位并且加一，而 len 会向右移动一位，也就是除以 $2$ 并向下取整。
2. 在最开始的 $h_2$ 次递归中，次高位的 $1$ 仍然没有移动到最低位，因此当前 len 不可能是 $100\dots0001$ 的形式。于是这 $h_2$ 次递归都会选择右节点。
3. 经过 $h_2$ 次右移后，因为 $0\le c<2^{h_2}$，$c$ 已经被完全移掉，此时

$<span class="arithmatex"><span class="MathJax_Preview">len=\left\lfloor\frac{x}{2^{h_2}}\right\rfloor=2^{h_1-h_2}+1.</span><script type="math/tex">len=\left\lfloor\frac{x}{2^{h_2}}\right\rfloor=2^{h_1-h_2}+1.$

现在的 len 正好是 $100\dots0001$ 的形式，因此开始选择左节点。 4. 接下来每选择一次左节点，$2^q+1$ 都会变成 $2^{q-1}+1$。所以我们会连续选择 $h_1-h_2$ 次左节点，使 len 从 $2^{h_1-h_2}+1$ 变成 $2$。此时它的两个儿子都已经是叶节点，最后再选择下标更大的右儿子，递归结束。

所以整条路径一共是：先选择 $h_2$ 次右节点，再选择 $h_1-h_2$ 次左节点，最后选择一次右节点。根节点的二进制下标本身是 $1$，因此最终得出了一个形如 $1111\dots11000\dots0001$ 的数，而且整个过程确实与 $c$ 无关。

具体来说：

这个时候我们就得出了一个 $O(1)$ 的公式来求解啦！

int f(int x){
    int h1=__lg(x);
    if (x==1ll<<h1) return 2*x-1;
    x^=1ll<<h1;
    int h2=__lg(x);
    return ((1ll<<(h2+1))-1)<<(h1-h2+1)|1;
}

注意，此时用了不少位运算的技巧，不理解也没问题，只需要知道它模拟了上述公式即可。另外，我在 1ll<<(h2+1) 外面补上了括号，虽然按照 C++ 运算符优先级原来的写法也没有问题，但这样显然更不容易看岔。

数学推导证明

那么把这个函数翻译成数学语言，则是：

太完美了！那么接下来我们要看开多少倍空间的最坏情况，只需要研究 $\frac{f(x)}{x}$ 的上界即可。

已知 $c$ 不会影响 $f(x)$，所以在 $h_1,h_2$ 固定时，如果我们希望 $x$ 尽可能小、$\frac{f(x)}x$ 尽可能大，则应当取 $c=0$。

所以，我们只需要研究：

的最大值即可。把 $h_2$ 当作变量，$h_1$ 当作常量：

这里我使用 Desmos 画下函数图，发现它好像是一个单峰函数。我们希望通过这个性质推一下在什么情况下 $g(h_2)$ 会取到最大值，这个最大值是多少。

先说结论：

1. 固定 $h_1$ 时，$g(h_2)$ 在 $h_2=\lfloor\frac{h_1}{2}\rfloor$ 时取到最大值。
2. $\displaystyle\lim_{h_1\to\infty}g\left(\left\lfloor\frac{h_1}{2}\right\rfloor\right)=4$，所以 $4$ 是 $\frac{f(x)}x$ 的上确界。换句话说，$\frac{f(x)}x$ 永远不会真的等于 $4$，但可以无限接近 $4$；任何小于 $4$ 的固定倍数都不可能对所有长度保险。

严谨证明

令

并把原来的函数看成关于实数 $B$ 的函数

原来的离散函数满足 $g(h_2)=G(2^{h_2})$。

单峰性

对 $B$ 求导：

因为分母在 $B>0$ 时恒正，所以我们只关心分子。令分子为 $0$，稍微整理一下得：

该方程在 $B>0$ 上仅有一个根：

同时，$G'(B)$ 在 $0<B<B^*$ 时为正，在 $B>B^*$ 时为负。因此 $G(B)$ 在 $B^*$ 左边单调递增，右边单调递减，确实是一个单峰函数，并且只有一个最大值。

极大点位置

知道这个函数的形状如此完美后，我们来推一推 $B$ 只能取 $2$ 的整数次幂时，这个最大值取在哪。考虑差分函数：

通过比较繁琐的计算后我们可以发现，$\Delta(B)$ 的分母恒正，分子为

好消息是这仍然是一个二次函数。它在 $B>0$ 上只有一个正根：

因此，当 $0<B<R$ 时，$\Delta(B)>0$；当 $B>R$ 时，$\Delta(B)<0$。也就是说，$B$ 每次乘 $2$ 时，函数值会先增大后减小，离散最大值出现在第一个满足 $B\ge R$ 的二次幂处。下面只需要确定 $R$ 落在哪两个二次幂之间。

先考虑 $h_1=2m$。令 $t=2^m$，则 $A=t^2$。分别代入 $B=\frac t2$ 与 $B=t$：

所以

离散最大值因此取在 $B=2^m$，也就是

再考虑 $h_1=2m+1$。当 $m=0$ 时只有 $h_2=0$ 可以选择，结论显然成立。下面设 $m\ge1$，仍令 $t=2^m$，此时 $A=2t^2$。同样分别代入：

最后一个不等式在 $t=2^m\ge2$ 时显然成立。因此仍然有

$$2^{m-1}