一、题目简介

题目要求我们动态维护一个初始为空的集合 M，支持 6 种操作：

1. 插入一个数 x
2. 删除一个数 x
3. 查询一个数 x 是否在集合中
4. 查询集合大小
5. 查询 x 的前驱
6. 查询 x 的后继

其中：

• 前驱：小于 x 的最大值
• 后继：大于 x 的最小值

二、这题为什么比普通集合难

如果只是前 4 个操作，其实 Python 的 set 就够了：

s = set()
s.add(x)      # 插入
s.discard(x)  # 删除（不存在也不会报错）
x in s        # 判断是否存在
len(s)        # 集合大小

但问题在于，这题还有两个操作：

• 查前驱
• 查后继

这就意味着，我们不能只知道“某个数在不在”，还得知道：

• 排序后它左边最近的是谁
• 排序后它右边最近的是谁

所以这题本质上不是普通集合题，而是：

动态维护一个有序集合

三、先用例子理解题目本质

假设当前集合是：

{5, 10, 20}

按从小到大排好后，其实就是：

[5, 10, 20]

那么：

• 15 的前驱是 10
• 15 的后继是 20

因为：

• 小于 15 的数有 5, 10，其中最大的是 10
• 大于 15 的数有 20，其中最小的是 20

所以这题最关键的，不是“插入删除”，而是：

如何快速在有序状态下找到某个数的前驱和后继

四、为什么不能直接暴力做

题目范围：

• 操作次数 n <= 10^5
• 数值范围 0 <= x <= 10^6

如果每次查询前驱 / 后继时都这样做：

• 前驱：从 x-1 一直往左扫
• 后继：从 x+1 一直往右扫

虽然逻辑上是对的，但最坏情况下会扫很多次，可能超时。

所以我们需要一种更快的方法。

五、这题的关键突破口：值域不大

题目里还有一个很重要的信息：

0 <= x <= 10^6

这说明所有可能出现的数，其实都落在一个固定范围里。

这就给了我们一个思路：

用一个数组记录“某个数是否在集合里”

例如：

present[5] = 1   # 5 在集合中
present[10] = 1  # 10 在集合中
present[20] = 1  # 20 在集合中

其余位置为 0，表示不在集合中。

1. 用 0/1 数组表示集合

比如集合：

{2, 5, 8}

可以表示成：

值:       0 1 2 3 4 5 6 7 8
是否存在: 0 0 1 0 0 1 0 0 1

也就是：

• 2 存在
• 5 存在
• 8 存在

2. 前驱 / 后继本质上在找“附近最近的 1”

还是集合 {2, 5, 8}。

查询 6 的前驱

就是找：

小于 6 的最大值

也就是在左边看：

• 5 在不在？
• 4 在不在？
• 3 在不在？
• 2 在不在？

最近的是 5，所以前驱是 5。

查询 6 的后继

就是找：

大于 6 的最小值

也就是在右边看：

• 7 在不在？
• 8 在不在？

最近的是 8，所以后继是 8。

六、为什么还需要“更高级的结构”

如果只是用一个 present 数组，判断存在确实快：

if present[x]:
    print("YES")

但查询前驱 / 后继如果还是左右暴力扫，还是可能很慢。

所以我们需要一个结构，帮助我们快速知道：

1. 某个范围内一共有多少个数存在
2. 第 k 小的元素是谁

这个结构就是：树状数组（Fenwick Tree）

七、树状数组到底在干什么

你可以先不用死记它的定义，先把它理解成：

一个能快速维护“前缀有多少个元素”的工具

1. 什么叫前缀有多少个元素

假设当前集合是：

{2, 5, 8}

那么：

• <= 1 的元素有 0 个
• <= 2 的元素有 1 个
• <= 4 的元素有 1 个
• <= 5 的元素有 2 个
• <= 8 的元素有 3 个

这个“到某个位置为止，一共有多少个元素”，就叫前缀和。

2. 前缀和为什么有用

还是查 6 的前驱

小于 6 的元素有哪些？

• 2
• 5

一共 2 个

那就说明：

前驱就是“第 2 小”的元素

而第 2 小的元素就是 5。

查 6 的后继

小于等于 6 的元素有哪些？

• 2
• 5

一共也是 2 个

那后继就是：

第 2 + 1 = 3 小的元素

而第 3 小的元素就是 8。

3. 于是问题转化成了两个能力

我们只要支持：

• 快速知道“小于等于某个值的元素个数”
• 快速知道“第 k 小元素是谁”

前驱和后继就能做出来。

八、树状数组在这题里的映射关系

因为题目里 x 可以等于 0，但树状数组一般从 1 开始下标，所以我们做一个映射：

idx = x + 1

也就是说：

• 原值 0 -> 树状数组位置 1
• 原值 1 -> 树状数组位置 2
• 原值 x -> 树状数组位置 x+1

九、操作如何实现

操作 1：插入 x

如果 x 不在集合里：

• 标记它存在
• 树状数组对应位置加 1
• 集合大小加 1

操作 2：删除 x

如果 x 在集合里：

• 标记它不存在
• 树状数组对应位置减 1
• 集合大小减 1

操作 3：查询 x 是否存在

直接看 present[x+1] 是否为真即可。

操作 4：查询集合大小

直接输出维护的 size。

操作 5：查询前驱

前驱定义为：小于 x 的最大值

那先数一数：

小于 x 的元素一共有多少个

因为我们映射成了 x+1，所以“小于 x”的值对应树状数组中前 x 个位置：

cnt = prefix_sum(x)

• 如果 cnt == 0，说明没有前驱，输出 -1
• 否则，前驱就是第 cnt 小元素

操作 6：查询后继

后继定义为：大于 x 的最小值

那先数一数：

小于等于 x 的元素一共有多少个

因为原值 x 对应位置 x+1，所以：

cnt = prefix_sum(x + 1)

• 如果 cnt == size，说明没有更大的元素，输出 -1
• 否则，后继就是第 cnt + 1 小元素

十、完整 Python3 代码（class 写法）

import sys
input = sys.stdin.readline

MAX_X = 10**6 + 2


class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def prefix_sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def kth(self, k):
        """
        找到第 k 小元素对应的位置（树状数组下标）
        """
        pos = 0
        bit = 1 << (self.n.bit_length() - 1)
        while bit:
            nxt = pos + bit
            if nxt <= self.n and self.tree[nxt] < k:
                k -= self.tree[nxt]
                pos = nxt
            bit >>= 1
        return pos + 1


class Solution:
    def __init__(self):
        self.bit = Fenwick(MAX_X)
        self.present = [False] * MAX_X
        self.size = 0

    def insert(self, x):
        idx = x + 1
        if not self.present[idx]:
            self.present[idx] = True
            self.bit.add(idx, 1)
            self.size += 1

    def delete(self, x):
        idx = x + 1
        if self.present[idx]:
            self.present[idx] = False
            self.bit.add(idx, -1)
            self.size -= 1

    def query_exist(self, x):
        idx = x + 1
        print("YES" if self.present[idx] else "NO")

    def query_size(self):
        print(self.size)

    def query_predecessor(self, x):
        cnt = self.bit.prefix_sum(x)
        if cnt == 0:
            print(-1)
        else:
            idx = self.bit.kth(cnt)
            print(idx - 1)

    def query_successor(self, x):
        cnt = self.bit.prefix_sum(x + 1)
        if cnt == self.size:
            print(-1)
        else:
            idx = self.bit.kth(cnt + 1)
            print(idx - 1)


if __name__ == "__main__":
    sol = Solution()
    n = int(input())

    for _ in range(n):
        arr = list(map(int, input().split()))
        op = arr[0]

        if op == 1:
            sol.insert(arr[1])
        elif op == 2:
            sol.delete(arr[1])
        elif op == 3:
            sol.query_exist(arr[1])
        elif op == 4:
            sol.query_size()
        elif op == 5:
            sol.query_predecessor(arr[1])
        elif op == 6:
            sol.query_successor(arr[1])

十一、代码逐步讲解

1. Fenwick 类

这是树状数组的封装。

add(i, delta)

def add(self, i, delta):
    while i <= self.n:
        self.tree[i] += delta
        i += i & -i

作用：

• 在位置 i 上加上 delta
• 用于插入 / 删除时维护计数

例如：

• 插入一个数：add(idx, 1)
• 删除一个数：add(idx, -1)

prefix_sum(i)

def prefix_sum(self, i):
    s = 0
    while i > 0:
        s += self.tree[i]
        i -= i & -i
    return s

作用：

计算前 i 个位置一共有多少个元素存在

kth(k)

def kth(self, k):
    pos = 0
    bit = 1 << (self.n.bit_length() - 1)
    while bit:
        nxt = pos + bit
        if nxt <= self.n and self.tree[nxt] < k:
            k -= self.tree[nxt]
            pos = nxt
        bit >>= 1
    return pos + 1

作用：

找到第 k 小元素所在的位置

这是树状数组中一个经典技巧。你现在可以先把它当成“模板函数”，重点先知道它的用途即可。

2. present 数组

self.present = [False] * MAX_X

作用：

• 快速判断某个数是否存在
• 防止重复插入
• 防止删除不存在的元素

3. size

self.size = 0

作用：

• 直接维护集合大小
• 这样查询大小时可以 O(1) 输出

十二、简单写法（不写 class）

如果你想写得更直接一点，也可以这样写。

import sys
input = sys.stdin.readline

MAX_X = 10**6 + 2
tree = [0] * (MAX_X + 1)
present = [False] * MAX_X
size = 0


def add(i, delta):
    while i <= MAX_X:
        tree[i] += delta
        i += i & -i


def prefix_sum(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s


def kth(k):
    pos = 0
    bit = 1 << (MAX_X.bit_length() - 1)
    while bit:
        nxt = pos + bit
        if nxt <= MAX_X and tree[nxt] < k:
            k -= tree[nxt]
            pos = nxt
        bit >>= 1
    return pos + 1


n = int(input())
for _ in range(n):
    arr = list(map(int, input().split()))
    op = arr[0]

    if op == 1:
        x = arr[1]
        idx = x + 1
        if not present[idx]:
            present[idx] = True
            add(idx, 1)
            size += 1

    elif op == 2:
        x = arr[1]
        idx = x + 1
        if present[idx]:
            present[idx] = False
            add(idx, -1)
            size -= 1

    elif op == 3:
        x = arr[1]
        idx = x + 1
        print("YES" if present[idx] else "NO")

    elif op == 4:
        print(size)

    elif op == 5:
        x = arr[1]
        cnt = prefix_sum(x)
        if cnt == 0:
            print(-1)
        else:
            print(kth(cnt) - 1)

    elif op == 6:
        x = arr[1]
        cnt = prefix_sum(x + 1)
        if cnt == size:
            print(-1)
        else:
            print(kth(cnt + 1) - 1)

十三、易错点总结

易错点 1：树状数组下标从 1 开始

题目中的 x 可能等于 0，所以必须映射：

idx = x + 1

否则原值 0 就没法放进树状数组。

易错点 2：插入时要判重

集合不允许重复元素，所以：

if not present[idx]:

只有原本不存在时，才能插入。

易错点 3：删除时要先判断是否存在

如果 x 本来就不在集合里，应该忽略，而不是直接减掉。

if present[idx]:

易错点 4：前驱和后继的“严格小于 / 严格大于”不要搞混

前驱

前驱是 < x

所以统计的是：

cnt = prefix_sum(x)

后继

后继是 > x

所以先统计 <= x 的数量：

cnt = prefix_sum(x + 1)

然后去找下一个。

易错点 5：kth 找到的是树状数组位置，不是原值

因为我们做过映射：

idx = x + 1

所以最后输出原值时要减回来：

print(idx - 1)

十四、复杂度分析

设值域大小为 V = 10^6。

每次操作：

• 插入：O(log V)
• 删除：O(log V)
• 查询存在：O(1)
• 查询大小：O(1)
• 查询前驱：O(log V)
• 查询后继：O(log V)

总复杂度：

O(n log 10^6)

对于 n <= 10^5，完全可以通过。

十五、总结

这题看起来叫“集合操作”，但真正难点不在集合，而在于：

集合需要保持有序，并支持前驱 / 后继查询

因为普通 set 做不了这个，所以我们需要：

• present 数组：记录某个数是否存在
• 树状数组：维护前缀有多少个元素
• kth：快速找第 k 小元素

这样就能把前驱和后继问题转化为：

• 前驱 = 第 cnt 小元素
• 后继 = 第 cnt + 1 小元素

十六、最后一句话版理解

这题你可以这样记：

树状数组不是在存集合本身，而是在帮我们快速回答：前面一共有多少个数。

而一旦知道了“前面有几个数”，前驱和后继就能转成“第几小元素”的问题。