「一本通 4.6 练习 3」普通平衡树

形式化题目

维护一个动态的多重整数集合 $S$ ，初始为空。共处理 $n$ 次操作（ $1 \leqslant n \leqslant 10^5$ ， $-10^7 \leqslant x \leqslant 10^7$ ），操作类型如下：

插入：向集合 $S$ 中加入数 $x$ 。
删除：从集合 $S$ 中移除一个数 $x$ （若有多个相同数，仅删除一个）。
查询数 $x$ 的排名：定义为集合中严格小于 $x$ 的元素个数 $+ 1$ 。
查询排名为 $x$ 的数：即查询集合从小到大排序后的第 $x$ 个数（ $1$ -indexed）。
查询数 $x$ 的前趋：求集合中严格小于 $x$ 且数值最大的数。
查询数 $x$ 的后继：求集合中严格大于 $x$ 且数值最小的数。

对于操作 $3, 4, 5, 6$ ，依次输出每项操作计算得到的答案。

正解

思路

本题是平衡树的经典模板题。在 Python 环境下，由于面向对象指针结构的递归和内存分配常数较大，手写二叉平衡树（如 Treap、Splay）极易遭遇递归爆栈或运行超时。

我们采用**分块有序表（Block List）**来实现：

结构组织：维护一个由多个列表构成的容器 blocks，满足：
- 每个子列表内部保持非降序；
- 块与块之间保持全局有序（即前一块的尾元素 $\leqslant$ 后一块的头元素）。
核心操作：
- 插入：顺序检查各块的末尾元素。若目标值 $x \leqslant$ 块尾元素，使用 bisect.insort 插入到该块内；若所有块尾都小于 $x$ ，则插入最后一个块。若单块长度膨胀超过阈值 $2B$ ，触发全局展平重构。
- 删除：定位到包含 $x$ 的块，二分定位并执行 pop，单次耗时 $O(B)$ 。
- 排名查询：遍历各块，若全块元素均 $< x$ ，累加整块长度；否则在首个尾元素 $\geqslant x$ 的块内二分计算严格小于 $x$ 的个数，总排名加 $1$ 即得。
- 第 $k$ 小查询：顺序扫描各块长度，用 $k$ 依次扣减块长，直到落在某块内部，直接通过下标取出对应元素。
- 前趋与后继：
  - 前趋：维护可能的最大前趋候选，一旦某个块的第一个元素 $\geqslant x$ ，后面所有块必然更大，即可提前剪枝。
  - 后继：跳过末尾元素 $\leqslant x$ 的块，在第一个包含更大元素的块中使用 bisect_right 取得答案。
分块平衡与重构：设定块大小基准 $B \approx 2\sqrt{n}$ 。当单块长度超过 $2B$ 时，将所有块展平后按大小 $B$ 重新划分为若干块，均摊复杂度仅为 $O(B)$ 。

graph LR
    subgraph Blocks["分块有序表结构"]
        B1["块 1: [2, 5, 8]"] --> B2["块 2: [12, 15, 19]"]
        B2 --> B3["块 3: [24, 30, 35]"]
    end

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 18:48
# update_at: 2026-09-30 18:48

import bisect
import math
import sys


def add_val(blocks: list[list[int]], block_size: int, val: int) -> None:
    """在分块有序结构中插入元素 val。"""
    for b in blocks:
        if not b or val <= b[-1]:
            bisect.insort(b, val)
            if len(b) > 2 * block_size:
                rebuild(blocks, block_size)
            return
    if not blocks:
        blocks.append([val])
    else:
        bisect.insort(blocks[-1], val)
        if len(blocks[-1]) > 2 * block_size:
            rebuild(blocks, block_size)


def remove_val(blocks: list[list[int]], block_size: int, val: int) -> None:
    """在分块有序结构中删除一个 val。"""
    for b in blocks:
        if b and val <= b[-1]:
            idx = bisect.bisect_left(b, val)
            if idx < len(b) and b[idx] == val:
                b.pop(idx)
                return


def query_rank(blocks: list[list[int]], val: int) -> int:
    """查询 val 的排名（严格小于 val 的元素个数 + 1）。"""
    smaller = 0
    for b in blocks:
        if not b:
            continue
        if b[-1] < val:
            smaller += len(b)
        else:
            smaller += bisect.bisect_left(b, val)
            break
    return smaller + 1


def query_kth(blocks: list[list[int]], k: int) -> int:
    """查询排名为 k（即第 k 小，1-indexed）的数。"""
    cur = k
    for b in blocks:
        if cur <= len(b):
            return b[cur - 1]
        cur -= len(b)
    return -1


def query_prev(blocks: list[list[int]], val: int) -> int:
    """求小于 val 且最大的数（前趋）。"""
    ans = -float('inf')
    for b in blocks:
        if not b or b[0] >= val:
            break
        if b[-1] < val:
            ans = b[-1]
        else:
            idx = bisect.bisect_left(b, val)
            if idx > 0:
                ans = b[idx - 1]
            break
    return int(ans)


def query_next(blocks: list[list[int]], val: int) -> int:
    """求大于 val 且最小的数（后继）。"""
    for b in blocks:
        if not b or b[-1] <= val:
            continue
        idx = bisect.bisect_right(b, val)
        if idx < len(b):
            return b[idx]
    return -1


def rebuild(blocks: list[list[int]], block_size: int) -> None:
    """重构分块以维持块大小均匀。"""
    flattened: list[int] = [x for b in blocks for x in b]
    blocks.clear()
    for i in range(0, len(flattened), block_size):
        blocks.append(flattened[i:i + block_size])


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        n = next(data)
    except StopIteration:
        return

    block_size = max(100, int(math.isqrt(n) * 2))
    blocks: list[list[int]] = []
    out: list[int] = []

    for _ in range(n):
        opt = next(data)
        x = next(data)
        if opt == 1:
            add_val(blocks, block_size, x)
        elif opt == 2:
            remove_val(blocks, block_size, x)
        elif opt == 3:
            out.append(query_rank(blocks, x))
        elif opt == 4:
            out.append(query_kth(blocks, x))
        elif opt == 5:
            out.append(query_prev(blocks, x))
        elif opt == 6:
            out.append(query_next(blocks, x))

    sys.stdout.write('\n'.join(map(str, out)) + '\n')


if __name__ == '__main__':
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:58
 * update_at: 2026-10-05 08:58
 */
// main.cpp：普通平衡树，用分块有序表实现（对应题解的主算法）。
// 结构约定：blocks 中每个子列表内部非降序，块间整体有序，
// 即前一块的最大值 <= 后一块的最小值。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

typedef long long ll;

vector<vector<ll> > blocks; // blocks[i] 为一个有序块，块内非降序
ll block_size;              // 基准块大小 B，单块超过 2B 时整体重构

// 把所有块展平后按 block_size 重新均匀划分，用于插入膨胀后的平衡。
void rebuild_blocks() {
    vector<ll> flat;
    for (int i = 0; i < (int)blocks.size(); i++) {
        for (int j = 0; j < (int)blocks[i].size(); j++) {
            flat.push_back(blocks[i][j]);
        }
    }
    blocks.clear();
    for (int i = 0; i < (int)flat.size(); i += block_size) {
        vector<ll> part;
        for (int j = i; j < (int)flat.size() && j < i + block_size; j++) {
            part.push_back(flat[j]);
        }
        blocks.push_back(part);
    }
}

// 插入 val：找到第一个尾元素 >= val 的块插入，找不到就插入最后一块。
void insert_val(ll val) {
    if (blocks.empty()) {
        vector<ll> part;
        part.push_back(val);
        blocks.push_back(part);
        return;
    }
    for (int i = 0; i < (int)blocks.size(); i++) {
        vector<ll> &b = blocks[i];
        if (b.empty()) {
            continue;
        }
        if (val <= b[b.size() - 1]) {
            vector<ll>::iterator pos = lower_bound(b.begin(), b.end(), val);
            b.insert(pos, val);
            if ((ll)b.size() > 2 * block_size) {
                rebuild_blocks();
            }
            return;
        }
    }
    // 所有块的尾元素都小于 val，直接放入最后一块
    vector<ll> &last = blocks[blocks.size() - 1];
    vector<ll>::iterator pos = lower_bound(last.begin(), last.end(), val);
    last.insert(pos, val);
    if ((ll)last.size() > 2 * block_size) {
        rebuild_blocks();
    }
}

// 删除一个 val：定位到可能含 val 的块，二分找到后删除一个。
void remove_val(ll val) {
    for (int i = 0; i < (int)blocks.size(); i++) {
        vector<ll> &b = blocks[i];
        if (b.empty()) {
            continue;
        }
        if (val <= b[b.size() - 1]) {
            vector<ll>::iterator pos = lower_bound(b.begin(), b.end(), val);
            if (pos != b.end() && *pos == val) {
                b.erase(pos);
            }
            return;
        }
    }
}

// 查询 val 的排名：严格小于 val 的个数 + 1。
ll query_rank(ll val) {
    ll smaller = 0;
    for (int i = 0; i < (int)blocks.size(); i++) {
        vector<ll> &b = blocks[i];
        if (b.empty()) {
            continue;
        }
        if (b[b.size() - 1] < val) {
            smaller += (ll)b.size(); // 整块都比 val 小
        } else {
            smaller += lower_bound(b.begin(), b.end(), val) - b.begin();
            break; // 后面的块只会更大，无需继续统计
        }
    }
    return smaller + 1;
}

// 查询第 k 小（k 从 1 开始）的数。
ll query_kth(ll k) {
    ll cur = k;
    for (int i = 0; i < (int)blocks.size(); i++) {
        vector<ll> &b = blocks[i];
        if (cur <= (ll)b.size()) {
            return b[cur - 1];
        }
        cur -= (ll)b.size();
    }
    return -1;
}

// 查询前趋：小于 val 且最大的数。
ll query_prev(ll val) {
    int found = 0;
    ll ans = 0;
    for (int i = 0; i < (int)blocks.size(); i++) {
        vector<ll> &b = blocks[i];
        if (b.empty()) {
            continue;
        }
        if (b[0] >= val) {
            break; // 该块及之后所有元素都 >= val
        }
        if (b[b.size() - 1] < val) {
            ans = b[b.size() - 1]; // 整块都是候选，取块内最大
            found = 1;
        } else {
            vector<ll>::iterator pos = lower_bound(b.begin(), b.end(), val);
            if (pos != b.begin()) {
                ans = *(pos - 1);
                found = 1;
            }
            break;
        }
    }
    if (!found) {
        return -1; // 题目保证前驱存在，这里只作兜底
    }
    return ans;
}

// 查询后继：大于 val 且最小的数。
ll query_next_val(ll val) {
    for (int i = 0; i < (int)blocks.size(); i++) {
        vector<ll> &b = blocks[i];
        if (b.empty()) {
            continue;
        }
        if (b[b.size() - 1] <= val) {
            continue; // 整块都 <= val，不是后继
        }
        vector<ll>::iterator pos = upper_bound(b.begin(), b.end(), val);
        if (pos != b.end()) {
            return *pos;
        }
    }
    return -1; // 题目保证后继存在，这里只作兜底
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n;
    if (!(cin >> n)) {
        return 0;
    }
    block_size = 2 * (ll)sqrt((double)n) + 10; // 取 B ≈ 2√n，兼顾块内与块间代价

    for (ll i = 0; i < n; i++) {
        ll opt;
        ll x;
        cin >> opt >> x;
        if (opt == 1) {
            insert_val(x);
        } else if (opt == 2) {
            remove_val(x);
        } else if (opt == 3) {
            cout << query_rank(x) << '\n';
        } else if (opt == 4) {
            cout << query_kth(x) << '\n';
        } else if (opt == 5) {
            cout << query_prev(x) << '\n';
        } else if (opt == 6) {
            cout << query_next_val(x) << '\n';
        }
    }
    return 0;
}

复杂度

时间复杂度：令块大小 $B = \Theta(\sqrt{n})$ ，总块数为 $O(n / B)$ 。单次插入、删除、查询排名、前趋与后继均由 $O(n / B)$ 次块间定位及 $O(B)$ 的块内二分与位移构成；平摊重构复杂度为 $O(B)$ 。单次操作平摊复杂度为 $O(\sqrt{n})$ ，总时间复杂度为 $O(n\sqrt{n})$ 。在 Python 中得益于内置 C 底层操作，性能极优。
空间复杂度：存储集合中所有的元素，总空间复杂度为 $O(n)$ 。

总结

在处理值域较大或动态有序集合问题时，分块有序表兼顾了简单性与高效性，在高级语言中配合标准库二分能发挥出极强的常数优势。

「一本通 4.6 练习 3」普通平衡树

目录

形式化题目

正解

思路

代码

复杂度

总结