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

icaijy · 2025-11-03 07:28:48 · 算法·理论

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

引入

众所周知，假如我们建线段树是很传统的非叶节点 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 这样的数，所以下文的讨论将更多在二进制下进行。

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

L=\left\lceil\frac{len}{2}\right\rceil,\qquad R=\left\lfloor\frac{len}{2}\right\rfloor.

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

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

R=2^{k-1},\qquad L=2^{k-1}+1,

所以

len=L+R=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，则一定可以写成：

x=2^{h_1}+2^{h_2}+c,\qquad 0\le c<2^{h_2},\qquad h_1>h_2.

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

在当前 len 不是 2^k+1 时，我们选择右节点。这个时候当前下标会左移一位并且加一，而 len 会向右移动一位，也就是除以 2 并向下取整。
在最开始的 h_2 次递归中，次高位的 1 仍然没有移动到最低位，因此当前 len 不可能是 100\dots0001 的形式。于是这 h_2 次递归都会选择右节点。
经过 h_2 次右移后，因为 0\le c<2^{h_2}，c 已经被完全移掉，此时
len=\left\lfloor\frac{x}{2^{h_2}}\right\rfloor=2^{h_1-h_2}+1.
现在的 len 正好是 100\dots0001 的形式，因此开始选择左节点。
接下来每选择一次左节点，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 无关。

具体来说：

f(x)={\underbrace{111\dots1}_{h_2+1\text{ 个 }1}}{\underbrace{000\dots0}_{h_1-h_2\text{ 个 }0}}1.

这个时候我们就得出了一个 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;
}

注意，此时用了不少位运算的技巧，不理解也没问题，只需要知道它模拟了上述公式即可。

数学推导证明

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

x=2^{h_1}+2^{h_2}+c,\quad 0\le c<2^{h_2},\quad h_1>h_2,

f(x)=(2^{h_2+1}-1)\cdot2^{h_1-h_2+1}+1.

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

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

所以，我们只需要研究：

\frac{(2^{h_2+1}-1)\cdot2^{h_1-h_2+1}+1}{2^{h_1}+2^{h_2}}

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

g(h_2)=\frac{(2^{h_2+1}-1)\cdot2^{h_1-h_2+1}+1}{2^{h_1}+2^{h_2}}.

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

先说结论：

固定 h_1 时，g(h_2) 在 h_2=\lfloor\frac{h_1}{2}\rfloor 时取到最大值。

严谨证明

令

A=2^{h_1}>0,\qquad B=2^{h_2}>0,

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

G(B)=\frac{4A-\frac{2A}{B}+1}{A+B}.

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

单峰性

对 B 求导：

G'(B)=\frac{2A^2+4AB-(4A+1)B^2}{B^2(A+B)^2}.

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

(4A+1)B^2-4AB-2A^2=0.

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

B^*=\frac{A(2+\sqrt{8A+6})}{4A+1}.

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

极大点位置

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

\Delta(B)=G(2B)-G(B).

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

S(B)=-(4A+1)B^2+3AB+A^2.

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

R=\frac{A(3+\sqrt{16A+13})}{2(4A+1)}.

因此，当 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：

S\left(\frac t2\right)=\frac{t^2(6t-1)}4>0,

S(t)=-t^2(3t^2-3t+1)<0.

所以

2^{m-1}=\frac t2<R<t=2^m.

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

h_2=m=\left\lfloor\frac{h_1}{2}\right\rfloor.

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

S\left(\frac t2\right)=\frac{t^2(8t^2+12t-1)}4>0,

S(t)=-t^2(4t^2-6t+1)<0.

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

2^{m-1}<R<2^m,

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

h_2=m=\left\lfloor\frac{h_1}{2}\right\rfloor.

这样，偶数与奇数情况便都严格证明完了。

最大值与上界

最后，我们就可以算一下最坏情况下是多少倍了。准确来说，我们要求的是：

\lim_{h_1\to\infty}g\left(\left\lfloor\frac{h_1}{2}\right\rfloor\right).

已知：

G(B)=\frac{4A-\frac{2A}{B}+1}{A+B}.

我们变形一下，上下同时除以 A，即有：

G(B)=\frac{4-\frac{2}{B}+\frac{1}{A}}{1+\frac{B}{A}}.

当 h_2=\lfloor\frac{h_1}{2}\rfloor 且 h_1\to\infty 时，A,B 都趋近于无穷，并且

\frac1A\to0,\qquad\frac1B\to0,\qquad\frac BA=2^{h_2-h_1}\to0.

因此：

\lim_{h_1\to\infty}g\left(\left\lfloor\frac{h_1}{2}\right\rfloor\right)=4.

另一方面，对于不是 2 的整数次幂的 x，我们有 1\le B<A，并且

4A-\frac{2A}{B}+1<4A<4(A+B),

所以 G(B)<4。当 x 是 2 的整数次幂时，f(x)=2x-1<4x 同样成立。于是对所有正整数 x 都有

f(x)<4x.

由于 f(x) 是整数，所以进一步有 f(x)\le4x-1。这说明从下标 1 开始存储时，开一个长度为 4x、合法下标为 0 到 4x-1 的数组一定足够。

结合前面构造出的趋近于 4 的数列，我们最终证明的是：

\sup_{x\in\mathbb Z^+}\frac{f(x)}x=4,

但这个上确界并不会被任何有限的 x 真正取到。

例子

整了半天，那么到底什么时候空间浪费得比较多，比较靠近四倍空间呢？如果我们需要一个例子，只需要指定一个 h_1，然后算出 h_2=\lfloor\frac{h_1}{2}\rfloor，最后算出原始的长度 x=2^{h_1}+2^{h_2} 即可，且 h_1 越大最终就越趋近于 4。

比如，指定 h_1=30，我们模拟一下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int calc(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;
}
signed main(){
    int h1=30,h2=h1/2,x=(1ll<<h1)+(1ll<<h2);
    cout<<"x="<<x<<endl;
    cout<<"4*x="<<4*x<<endl;
    cout<<"f(x)="<<calc(x)<<endl;
    cout<<fixed<<setprecision(10)<<"f(x)/x="<<(double)calc(x)/(double)x<<endl;
}

输出：

x=1073774592
4*x=4295098368
f(x)=4294901761
f(x)/x=3.9998169011

十分接近 4 了！

结语

其实本人非常非常讨厌这么繁琐的证明过程，但我真的一直很好奇线段树最差的情况是多少，因此就活成了自己最讨厌的样子写了这么一个公式满天飞的证明（笑死）。

我认真思考这个的动机其实就源于上文提到的 P6025 线段树。我发现最终得出的公式非常的不错，很可能能让我用比较代数的方法证明这个问题。

其实想要证明开 4 倍空间完全有更简单的推导。但是知道了具体是什么数会逼近四倍空间还是很有意义的！

最终感谢所有的参考资料作者，与阅读到这的你们，谢谢大家！

::::info[AI辅助提示] 本文使用了 ChatGPT 进行部分数学的推导与验算，所有 AI 的结论均由我验算过。 ::::