（休闲娱乐）如果忘了平衡树怎么写

WorldMachine · 2025-12-05 19:28:20 · 休闲·娱乐

鸣谢：@MornStar，算是参考文章的一点拓展。

假如我们现在忘了平衡树怎么打，但需要 A 掉平衡树板子题，咋办。

考虑二进制分组，具体地说，维护 \log_2n 个有序序列，第 i 个序列的大小要么为 0，要么为 2^i，这样空间复杂度显然为 \mathcal O(n)。

假如我们已经能维护插入，那么对于可差分信息，像可删堆那样再开一个相同的数据结构维护已删除的数即可。

查询 x 的排名时，直接在每个序列里二分即可，复杂度为 \mathcal O(\log^2n)。

查询第 k 小时，可以在外面二分一个值然后求出它的排名，复杂度为 \mathcal O(\log V\log^2n)。

如果没有删除，那么查询 x 的前驱、后继也可以直接对于每个序列分别二分，复杂度为 \mathcal O(\log^2n)；否则必须要先求出 x 的排名然后求第 k 小，复杂度为 \mathcal O(\log V\log^2 n)。

现在考虑如何支持插入。一开始新开一个只包含待插入数 x 的序列 v，然后从下标 0 开始枚举每个序列，若当前序列 a_i 为空，则将 v 放上去，结束；否则将 a_i 归并到 v 里，并继续枚举后面的 i。

每个数至多只会被归并 \mathcal O(\log n) 次，故插入的总复杂度为 \mathcal O(n\log n)。

:::success[代码实现]{open}

#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef basic_string<int> vec;
constexpr int N = 1e5 + 5, L = 17;
struct DS {
    vec a[L];
    il void insert(int x) {
        vec v(1, x);
        for (int i = 0; i < L; i++) {
            if (a[i].empty()) return a[i] = v, void(); int s = v.size();
            v += a[i], inplace_merge(v.begin(), v.begin() + s, v.end()), vec().swap(a[i]);
        }
    }
    il int qrylower(int x) {
        int ret = 0;
        for (int i = 0; i < L; i++) ret += lower_bound(a[i].begin(), a[i].end(), x) - a[i].begin();
        return ret;
    }
    il int qryupper(int x) {
        int ret = 0;
        for (int i = 0; i < L; i++) ret += upper_bound(a[i].begin(), a[i].end(), x) - a[i].begin();
        return ret;
    }
    il int count(int x) { return qryupper(x) - qrylower(x); }
};
struct MStree {
    DS a, b; int mx = INT_MIN, mn = INT_MAX;
    il void insert(int x) { a.insert(x), mx = max(mx, x), mn = min(mn, x); }
    il void erase(int x) { b.insert(x); }
    il int rank(int x) { return a.qrylower(x) - b.qrylower(x) + 1; }
    il int count(int x) { return a.count(x) - b.count(x); }
    il int kth(int k) {
        int L = mn, R = mx, mid, ret;
        while (L <= R) rank(mid = L + R >> 1) <= k ? (ret = mid, L = mid + 1) : (R = mid - 1);
        return ret;
    }
    il int prev(int x) { return kth(rank(x) - 1); }
    il int next(int x) { return kth(a.qryupper(x) - b.qryupper(x) + 1); }
} t;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    while (n--) {
        int op, x; cin >> op >> x;
        if (op == 1) t.insert(x);
        else if (op == 2) t.erase(x);
        else if (op == 3) cout << t.rank(x) << '\n';
        else if (op == 4) cout << t.kth(x) << '\n';
        else if (op == 5) cout << t.prev(x) << '\n';
        else cout << t.next(x) << '\n';
    }
}

:::

总用时 774\text{ms}，看起来常数非常小啊。

考虑平衡复杂度，改为 k 进制。

具体地说，插入时：

• 若当前序列 a_i 为空，则将 v 放上去，结束；
• 否则若 a_i 和 v 合并后大小小于 k^{i+1} 则直接把 v 合并到 a_i 上去，结束；
• 否则把 a_i 合并到 v 上去，继续后面的过程。

这样每个数会被合并 \mathcal O(k^2\log_kn)=\mathcal O\left(\dfrac{k^2\log n}{\log k}\right) 次，总复杂度为 \mathcal O\left(\dfrac{nk^2\log n}{\log k}\right)，而询问的复杂度变为 \mathcal O\left(\dfrac{\log V\log^2n}{\log k}\right)，取 k=\mathcal O(\sqrt{\log V\log n}) 即可做到最优复杂度 \mathcal O\left(\dfrac{n\log V\log^2 n}{\log\log V}\right)。

实测 k 取 10 左右最优？

:::success[代码实现]{open}

constexpr int N = 1e5 + 5, L = 5, pw[] = {1, 10, 100, 1000, 10000, 100000};
// 其余部分均相同
il void insert(int x) {
    vec v(1, x);
    for (int i = 0; i < L; i++) {
        if (a[i].empty()) return a[i] = v, void(); int s = v.size();
        if (a[i].size() + s == pw[i + 1]) v += a[i], inplace_merge(v.begin(), v.begin() + s, v.end()), vec().swap(a[i]);
        else return a[i] += v, inplace_merge(a[i].begin(), a[i].end() - s, a[i].end()), void();
    }
}

:::

总用时 539\text{ms}，没快多少其实。

事实证明让这个东西支持删除还是太为难它了，下面考虑只有插入的情况。

这样的话取 k=\mathcal O(\sqrt{\log n})，查询排名、前驱、后继等独立信息就可以做到 \mathcal O\left(\dfrac{\log^2 n}{\log\log n}\right)，目测能快个十几倍，可喜可贺。

下面开始魔怔。

考虑用这个东西来维护一些别样的信息，例如线性基这种合并复杂度比加入元素复杂度高的信息。

设加入元素复杂度为 \mathcal O(f)，合并复杂度为 \mathcal O(g)，令 \theta=\dfrac gf，考虑每次归并完之后构造如下的结构：

• 把序列按照 B 为块长分块，对整块建立猫树，这样时间复杂度为 \mathcal O\left(\dfrac{\text{size}\log\text{size}\cdot f}{B}\right)。

这样插入的总复杂度为 \mathcal O\left(\dfrac{nk^2\log^2nf}{B\log k}\right)。

随后每次询问一个值域区间 [l,r] 的信息时，找到每个序列上对应的区间，需要 \mathcal O(B) 次加入元素与 \mathcal O(1) 次合并，复杂度为 \mathcal O\left(\dfrac{\log n(\log n+Bf+g)}{\log k}\right)。

稍微平衡一下，发现 B=\mathcal O(\theta)，k=\mathcal O\left(\dfrac{\theta}{\sqrt{\log n}}\right) 时最优，复杂度为 \mathcal O\left(\dfrac{ng\log n}{\log\theta}\right)。

比如说用这个东西来维护在序列中一个位置插入一个数、查询区间线性基，可以做到 \mathcal O\left(\dfrac{nw^2\log n}{\log w}\right)，代码没写，感觉不会很快。