浅谈一些基于规模翻倍的对数复杂度算法

· · 算法·理论

前言

你是否有过一些类似的疑惑：

那么在此篇文章，我将介绍这些算法的时间复杂度分析的共通之处以及它们的扩展应用。

启发式合并（小并大）

提到启发式合并，它可能会代表两类算法：

此处我们讨论类似并查集按大小合并的“小并大（Small-to-Large Merge）”合并方式。顾名思义，它的做法是合并两个集合的时候，让小的集合合并到大的集合。这个算法描述起来很简单，但是复杂度却能直接从暴力降到对数级别，而且用途极广，我将使用几个例子来展示它的复杂度分析以及用途。

顺带一提：其实我个人认为“小并大”这个名字比“启发式合并”更好一点。因为前者展示出了具体的合并方式，而后者又经常用来指代 DSU on tree，导致会比较乱。

并查集合并

众所周知，如果并查集不做任何优化，合并后最差的情况是一条链，这样的高度会导致查询祖先退化为 O(n)。因此优化的思路是让高度尽可能矮。

此处讨论记录每个连通块的节点大小，合并的时候把小的连通块合并到大的连通块。就这么一个优化，即可将树高和复杂度降到 O(\log(n))。它的证明就是今天讨论的核心——翻倍。

此处我们把视角从连通块的高度换成一个节点的深度来分析。对于一个节点 v，它的深度什么时候会变化呢？答案是当合并的时候它所在的连通块挂在了另一个连通块的下面，这样显然深度会加 1。那么有没有可能有一个点在一个倒霉连通块，每次合并都是挂在别人身上导致深度一直加 1 吗？

答案是不会。这就是小并大的威力：因为一次合并操作后，由于我们把小的集合挂在大的身上，所以小连通块中点所在的新集合至少会变成原来的两倍。因为一次合并会翻倍，而集合最大的上限就是 n 个元素，那么一个元素的深度增加次数最多是 \lfloor \log_2(n) \rfloor 次，多一次就超过 n 了，显然不行。

因此，由于深度增加的次数是有限的，深度显然也是在这个对数级别。

可并堆？

例题：P3377 【模板】可并堆 1

这题的做法绝对是百花齐放。数据结构选择可以选配对堆、红黑树、斜堆甚至斐波那契堆。如果你啥也不会也能直接启动平板电视的 __gnu_pbds::priority_queue。但是如果你除了 std::priority_queue 啥也不会呢？

没错！有了小并大这个技巧，你完全不需要学以上任何一个东西。我们的解答就一句话：合并的时候把小的堆元素全部 pop 出来然后 push 进大的堆即可，代码也是很直观的：

#include <bits/stdc++.h>

using namespace std;

#define int long long

int dsu[100005],d[100005];

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq[100005];

int f(int x){

    if (dsu[x]==x) return x;

    return dsu[x]=f(dsu[x]);

}

void unite(int x,int y){

    x=f(x),y=f(y);

    if (x==y) return;

    if (pq[x].size()<pq[y].size()) swap(x,y);

    while (pq[y].size()){

        auto pqt=pq[y].top();

        pq[y].pop();

        pq[x].push(pqt);

    }

    dsu[y]=x;

}

signed main(){

    int n,q;cin>>n>>q;

    for (int i=1;i<=n;i++){

        dsu[i]=i;

        int num;cin>>num;

        pq[i].push({num,i});

    }

    while (q--){

        int op;cin>>op;

        if (op==1){

            int x,y;cin>>x>>y;

            if (!d[x]&&!d[y])

            unite(x,y);

        }

        else{

            int x;cin>>x;

            if (d[x]) cout<<-1<<endl;

            else{

                x=f(x);

                auto [num,id]=pq[x].top();

                pq[x].pop();

                d[id]=1;

                cout<<num<<endl;

            }

        }

    }

}

但是这并不代表别的可并堆都一无是处，因为小并大会带来一个额外的对数复杂度，意味着总体复杂度是 O(n\log^2(n))。

如果暂时不考虑删除操作，证明依旧是考虑一个元素：让它从一个优先队列移动到另一个优先队列的复杂度是 O(\log(n))。由于我们让小堆的元素移动到大堆里，所以移动的元素所在的集合大小会至少翻倍，也就是至多 \lfloor \log_2(n) \rfloor 次移动操作，总体也就是 O(n\log^2(n))。

:::warning[P3377 中删除操作带来的一个小问题]

P3377 本身支持删除堆顶，因此堆的大小会下降，所以严格来说，不能直接说“一个元素所在堆的大小一生只会不断翻倍”。

不过这个做法依旧可以用势能分析证明到 O(n\log^2(n))。直观地说，每次搬运小堆中的元素都会让这些元素所在堆的大小至少翻倍，因此能获得足够的势能；删除虽然会让势能下降，但每个元素最多只会被删一次，总下降量仍然只有 O(n\log n)。

所以这道题本身的复杂度结论依旧成立，只是证明比最纯的小并大稍微多一步。

:::

DSU on tree？点分治？线段树合并？不如我的小并大

叠甲：笔者并不是说小并大永远比这些树上算法好用，很多题其实都能用很多种方法做出来，只是某些情况某个会更好用一点。

例题：P3605 [USACO17JAN] Promotion Counting P

这题解法很多很多。如果您很有实力的话，第一步可能就会往 DFS 序、线段树合并或者是各种数据结构（平衡树、可持久化线段树等）方向想。但对于萌新来说最直观的解法肯定是把子树下真正的信息维护出来，然后从中找出答案。而这种方法有可能实现吗？可以的！不过由于这里需要按秩查找，单纯的 std::set 并不支持，这里我们使用平板电视的 __gnu_pbds::tree 来维护信息。

#include <bits/extc++.h>
#define int long long
using namespace std;
using namespace __gnu_pbds;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
vector<int> adj[100005];
int a[100005];
int ans[100005];
void merge(oset &s, oset &s2)
{
    if (s.size() < s2.size())
        s.swap(s2);
    for (int i : s2)
        s.insert(i);
}
void dfs(int x, oset &ret)
{
    ret.insert(a[x]);
    for (int i : adj[x])
    {
        oset c;
        dfs(i, c);
        merge(ret, c);
    }
    ans[x] = ret.size() - ret.order_of_key(a[x] + 1);
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 2; i <= n; i++)
    {
        int p;
        cin >> p;
        adj[p].push_back(i);
    }
    oset arst;
    dfs(1, arst);
    for (int i = 1; i <= n; i++)
        cout << ans[i] << "\n";
}

复杂度证明的话可以考虑一个节点所在的集合大小变化，依旧每次会至少翻倍，所以每个元素最多被移动 O(\log(n)) 次。每次插入 PBDS 的复杂度是 O(\log(n))，所以总复杂度为 O(n\log^2(n))。

关于实现的温馨提示

由于小并大是合并集合，这个集合可以是很多的数据结构。但由于我们需要用到很多 swap 操作，请务必确认 swap 的时间复杂度。

尤其是 PBDS，建议优先使用成员函数 a.swap(b)。

总结

当碰到需要维护集合且需要合并的情况下，可以考虑小并大。尤其是在树上问题需要维护子树信息的，除了 DSU on tree、点分治等算法，小并大通常也可以 AC，注意分析好时间复杂度即可。

重链剖分

复杂度

此处假设读者已经有了部分重链剖分的基础，若完全不会建议先了解一下。

众所周知，重链剖分中从一个点跳到根最多只会跨 O(\log(n)) 次轻边。初学者可能很难体会到这一点，因为重链剖分说实话维护的东西很多，第一次见肯定会觉得算法比较“重”，那它为啥不仅跳的次数是 O(\log(n))，而且常数还挺快的呢？

对于时间复杂度的分析，我们发现一次跳链相当于当前点要从重链的头往上走一步。那么这意味着什么呢？还是翻倍！

假设我们当前在重链的头 v，而它的父亲是 p。由于 v 不是 p 的重儿子，设 p 的重儿子为 h，那么根据定义有

size[h]\ge size[v].

所以

size[p]\ge 1+size[h]+size[v]>2size[v].

那么这相当于往上一走，当前子树大小至少翻倍！

这点就和小并大的复杂度分析很像了，它切换的上限就是 O(\log(n))。而且由于树的儿子可能很多，所以很多情况下切换后子树大小远远不止翻倍，还会加上不少别的轻儿子，导致这个 O(\log(n)) 的上限其实也不一定容易卡满。

需要注意的是，严格来说这里证明的是“一条根路径上最多跨 O(\log(n)) 条轻边 / 被拆成 O(\log(n)) 段重链”。如果每一段上还需要做一次线段树查询，那么一次路径操作通常是 O(\log^2(n))。

DSU on tree

这个技巧经常被称之为“树上启发式合并”，在此简单复习下具体的技巧：

  1. 先递归所有轻儿子，把轻儿子的答案全部算出来。
  2. 递归重儿子，算出重儿子的答案，并且保留重儿子的子树信息，让当前节点复用这个信息。
  3. 暴力把所有轻儿子的合并到当前点，这样就能知道当前点的答案了。

不知道大家有没有感觉这个算法非常的暴力，但是它的复杂度确实是 O(n\log(n)) 的（不算数据结构带来的复杂度）。凭什么呢？

此处就用到了重链剖分的同款思想。

考虑一个点 v 会被步骤 3 访问几次。每次能访问到它的祖先 p，都意味着 v 在 p 的某个轻儿子子树中。换句话说，每多被这样访问一次，从 v 往上走就至少要跨过一条新的轻边。

而一条根路径上的轻边数量是 O(\log(n))，所以一个点最多只会被步骤 3 额外访问 O(\log(n)) 次。所有点加起来就是 O(n\log(n))。

总的来说，所谓的“树上启发式合并”和“启发式合并”虽然复杂度分析差不多，但是前者更多是在利用 Heavy-Light 的轻重儿子结构。除了复杂度分析很像以外，和小并大关系并不大，希望大家能理清楚它们之间的关系。

二进制分组

这个思想我感觉非常符合本文的主题，但这个技巧本人认为相当鸡肋，经常能被更好的数据结构代替，用途相对受限。

例题：P5076 【深基16.例7】普通二叉树（简化版）

注意：仅用于演示二进制分组，这种题平衡树肯定是比二进制分组好的。

二进制分组的思路是把一个有 n 个元素的集合按照 n 的每个二进制位拆解成若干个大小为 2^k 的块，这些块内存储着信息（可能是经过排序的）。

插入元素后像做二进制加法一样不断地向前进位，进位就等同于合并下一位与当前的集合。

时间复杂度分析则是显然的：由于合并是线性的，每个元素最多往前移动 \lfloor \log_2(n) \rfloor 次，插入也就是均摊 O(\log(n))。

按照这种方式插入后，我们相当于把当前集合拆成了 O(\log(n)) 个已经排好序的集合，这样就能在此基础上进行各种查询操作了，此处就与二进制分组本身无关了。

参考代码：

#include <bits/stdc++.h>
using namespace std;
vector<int> v[30];
int cnt;
void ins(int x)
{
    cnt++;
    v[0].push_back(x);
    sort(v[0].begin(), v[0].end());
    for (int i = 0; 1 << i <= cnt; i++)
    {
        if (v[i].size() > 1 << i)
        {
            vector<int> tmp(v[i].size() + v[i + 1].size());
            merge(v[i + 1].begin(), v[i + 1].end(), v[i].begin(), v[i].end(), tmp.begin());
            v[i + 1].swap(tmp);
            v[i].clear();
        }
        else
            break;
    }
}
int rnk(int x)
{
    int ans = 0;
    for (int i = 0; 1 << i <= cnt; i++)
        ans += lower_bound(v[i].begin(), v[i].end(), x) - v[i].begin();
    return ans + 1;
}
int pre(int x)
{
    int ans = -2147483647;
    for (int i = 0; 1 << i <= cnt; i++)
    {
        auto it = lower_bound(v[i].begin(), v[i].end(), x);
        if (it == v[i].begin())
            continue;
        ans = max(ans, *prev(it));
    }
    return ans;
}
int suc(int x)
{
    int ans = 2147483647;
    for (int i = 0; 1 << i <= cnt; i++)
    {
        auto it = upper_bound(v[i].begin(), v[i].end(), x);
        if (it == v[i].end())
            continue;
        ans = min(ans, *it);
    }
    return ans;
}
signed main()
{
    int q;
    cin >> q;
    while (q--)
    {
        int op, x;
        cin >> op >> x;
        if (op == 1)
            cout << rnk(x) << endl;
        if (op == 2)
        {
            int l = -1e9 - 5, r = 1e9 + 5;
            while (l + 1 != r)
            {
                int mid = (l + r) / 2;
                if (rnk(mid) <= x)
                    l = mid;
                else
                    r = mid;
            }
            cout << l << endl;
        }
        if (op == 3)
            cout << pre(x) << endl;
        if (op == 4)
            cout << suc(x) << endl;
        if (op == 5)
            ins(x);
    }
}

总结

以上是我总结出的三大类依靠“翻倍”思想的对数复杂度算法。很多初学者都会认为对数复杂度与“减半”有关，但其实“翻倍”也是很重要的一点。

这类算法很多时候需要均摊分析，关注每个小元素一生会贡献多少次，而不是只看单次操作的最坏代价，所以这种复杂度相对比较难第一眼发现。

希望我的文章能让大家更好地理解这些依靠“翻倍”得到对数复杂度的算法。

顺带一提，我的初衷其实是想要更加推广一下启发式合并（小并大）的思想，因为这个思想其实我认为非常重要，涵盖了很多“翻倍”导致的对数算法情况，且适用性其实较广。尽管大多数时候都有别的算法可以替代，但依旧可以作为一个“万金油”算法来考虑。

:::info[AI 辅助声明]

本文主体结构、核心观点、主要算法思路与代码均由作者自行完成。

ChatGPT 用于检索并核对洛谷 Markdown / LaTeX 排版规范、检查复杂度分析中的技术性问题，并对少量存在歧义或明显病句的文字进行了修改。所有修改均由作者人工审核后采用。

:::