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

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

引入

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

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

暴力分析

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

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}+1, k \in \mathbb{Z}^+ 时我们需要取左子树。这个数在二进制下为形如 1000\dots0001 这样的数，所以下文的讨论将更多在二进制下进行。

证明也非常好理解。当两个子树深度相同的时候我们肯定会取右子树。但当右子树已经是满二叉树了，没地了，这时假如我们把长度加 1，这就会导致左子树长度加 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+1}, k \in \mathbb{Z} 时，不存在次高位的 1，应当特判返回 2x-1（此时是满二叉树）。接下来分析认为 x 至少包含两个二进制下的 1

其实很好理解。我们模拟下我们是怎么取的：

1. 当前 len 是 1，即叶节点时，直接返回。
2. 当前 len 不是 2^{k+1}+1, k \in \mathbb{Z}^+，那么就一直取右节点。这个时候会将当前下标左移一位并且加一。len 会右移一位
3. 否则我们的 1en 在二进制下就是 100\dots0001 这样的数。这个时候相当于左子树在原本满二叉树的情况下加了一。这样我们就会一直选左子树，直到儿子为叶节点。此时下标会左移一位。len 会右移一位并且加一。加一是因为此时长度肯定为奇数。

所以最终得出了一个形如 1111\dots11000\dots0001 这样的数。

假设 h_1,h_2 分别代表最高位与次高位的数。则：

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

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

数学推导证明

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

太完美了！那么接下来我们要看开多少倍空间的最坏情况，只需要求 \frac{f(x)}{x} 的最大值即可。 已知 c 不会影响 f(x) 所以如果我们希望 x 尽可能小，则 c=0。 所以，我们只需要研究：

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

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

先说结论：

严谨证明

令 A=2^{h_1}>0,\ B=2^{h_2}>0,，则：

单峰性

对 B 求导：

当它为 0 时即为函数顶点。此时我们只关心分子即可，稍微整理一下得：

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

且导数符号由正变负，故 g(B) 仅有一个极大点，可以证明函数为单峰函数，且只有一个最大值。最大值左边单调递增右边单调递减。

极大点位置

知道这个函数的形状如此完美后，我们来推一推整数的情况下这个最大值取在哪。考虑一个差分函数：

若 k 为最后一个符合 \triangle(k)>0，最终取到最值的则是 k+1。

通过比较繁琐的计算后我们可以发现 \triangle(B) 的分母恒正，分子为 -(4A+1)B^2+3AB+A^2。好消息是这仍然是一个二次函数，它的正根为：

我们有 2^{h_2-1}<R<2^{h_2}。所以，最终的 h_2 即为 \lceil\log_2R\rceil。 这里通过估算下 R 中各个元素上下界，省略掉一些常数可以计算出 R 的范围是：

因此，h_2>h_1/2-1，所以在 h_1 为偶数时 h_2=\lfloor\frac{h_1}{2}\rfloor 时取到最大值。

对于奇数的 h_1，我们设 h_1=2m+1，将其代入后，使用同样的方法估算上界，可以证明 R<2^m=2^{\lfloor\frac{h1}{2}\rfloor}。最终结论与偶数相同，h_2=\lfloor\frac{h_1}{2}\rfloor 时取到最大值。

最大值与上界

最后，我们就可以算一下最坏情况下是多少倍了。即求：

已知：

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

在极限的运算下，所有分母为 A 的数都无限趋近于 0，因此我们有：

因为 h_2=\lfloor\frac{h_1}{2}\rfloor，所以 h_2 也趋近于无穷，因此便证明了极限趋近于 4。

例子

整了半天，那么到底什么时候空间浪费的比较多，比较靠近四倍空间呢？如果我们需要一个例子，只需要指定一个 h_1，然后算出 h_2=\lfloor\frac{h1}{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 的结论均由我验算过。 ::::