第一章 数据结构
第一节 线性结构
1.1 【5】双端栈
1.1.1 什么是双端栈?
在理解双端栈之前,我们先回顾一下普通的栈。一个普通的栈,所有元素的插入(入栈,push)和删除(出栈,pop)都只能在同一端——也就是“栈顶”进行。
那么,一个很自然的想法是:如果我们允许栈的两端都可以进行入栈和出栈操作,会怎么样呢?这种两端都具备栈顶功能的数据结构,就是双端栈(Double-Ended Stack)。
想象一个很长的薯片筒,我们不仅可以从上面的开口放入或取出薯片,也可以打开下面的盖子,从底部放入或取出薯片。这个薯片筒就是一个典型的双端栈模型。
然而,在标准的计算机科学数据结构中,“双端栈”这个术语并不常用。其功能被一个更通用、更强大的数据结构——双端队列(Deque)——所完全覆盖。因此,通常我们将双端栈理解为双端队列的一个概念性前身。在接下来的内容中,我们将直接学习功能更全面的双端队列。
1.2 【5】双端队列
1.2.1 什么是双端队列?
双端队列(Double-Ended Queue,简称 Deque) 是一种允许在队列的头部和尾部都能进行插入和删除操作的线性数据结构。它就像一个“全能选手”,集成了栈和队列的特点。
- 如果只使用它的一端进行插入和删除,它就表现得像一个栈。
- 如果在一端进行插入,在另一端进行删除,它就表现得像一个队列。
我们可以将双端队列想象成一个两头都开放的“队伍”。新来的人可以选择排在队伍的最前面,也可以选择排在队伍的最后面;同时,队伍最前面的人可以离开,队伍最后面的人也可以“反悔”直接离开。
1.2.2 双端队列的核心操作
一个标准的双端队列通常支持以下几种核心操作:
push_back
: 在队列的尾部插入一个元素。pop_back
: 删除队列尾部的元素。push_front
: 在队列的头部插入一个元素。pop_front
: 删除队列头部的元素。front
: 获取队列头部的元素。back
: 获取队列尾部的元素。empty
: 检查队列是否为空。size
: 获取队列中元素的数量。
1.2.3 双端队列的实现
在竞赛中,我们几乎总是使用 C++ 标准模板库(STL)中提供的 std::deque
容器,因为它性能高效且使用方便。但为了深入理解其工作原理,了解如何用数组模拟双端队列是非常有帮助的。
1.2.3.1 数组模拟实现(循环数组)
我们可以使用一个数组来模拟双端队列,并设置两个指针:head
指向队头,tail
指向队尾的下一个位置。
为了避免数组存满后无法再插入元素,我们通常使用循环数组。也就是说,当指针移动到数组的末尾时,它会自动“绕回”到数组的开头。这可以通过取模运算 %
来实现。
- 初始化:
head
和tail
都指向数组中间的某个位置,以保证两边都有扩展的空间。 push_back
: 元素存入tail
指向的位置,然后tail
向后移动一位(tail = (tail + 1) % N
,其中 \(N\) 是数组大小)。push_front
:head
向前移动一位(head = (head - 1 + N) % N
),然后元素存入head
指向的位置。pop_back
:tail
向前移动一位。pop_front
:head
向后移动一位。
判断队列为空的条件是 head == tail
。判断队列为满的条件是 (tail + 1) % N == head
。
这种手写方式虽然能加深理解,但在实际比赛中,除非有特殊要求,否则不推荐,因为容易出错且效率不如 STL
。
1.2.4 C++ STL deque
代码模板
使用 STL
中的 deque
非常简单。首先需要包含头文件 <deque>
。
#include <iostream>
#include <deque> // 包含 deque 的头文件using namespace std;int main() {// 1. 创建一个 dequedeque<int> dq;// 2. 在队尾插入元素dq.push_back(10); // dq: [10]dq.push_back(20); // dq: [10, 20]// 3. 在队头插入元素dq.push_front(5); // dq: [5, 10, 20]dq.push_front(1); // dq: [1, 5, 10, 20]// 4. 查看队头和队尾元素cout << "队头元素是: " << dq.front() << endl; // 输出 1cout << "队尾元素是: " << dq.back() << endl; // 输出 20// 5. 获取队列大小cout << "队列大小是: " << dq.size() << endl; // 输出 4// 6. 从队头删除元素dq.pop_front(); // dq: [5, 10, 20]cout << "pop_front 后队头元素是: " << dq.front() << endl; // 输出 5// 7. 从队尾删除元素dq.pop_back(); // dq: [5, 10]cout << "pop_back 后队尾元素是: " << dq.back() << endl; // 输出 10// 8. 判断队列是否为空while (!dq.empty()) {cout << "当前队头: " << dq.front() << ", 准备出队..." << endl;dq.pop_front();}if (dq.empty()) {cout << "队列现在为空。" << endl;}return 0;
}
双端队列本身的应用场景非常广泛,例如在广度优先搜索(BFS)的某些变体中,以及作为实现其他高级数据结构(如我们即将学习的单调队列)的基础。
1.3 【5】单调队列
1.3.1 什么是单调队列?
单调队列并不是一个 STL
中直接存在的数据结构,而是一种基于双端队列(deque
)实现的算法思想和数据结构。
顾名思义,单调队列内部的元素是单调的,即单调递增或单调递减。这个特性使得它非常适合解决一类经典问题:滑动窗口内的最值问题。
例如,给定一个数组和一个固定大小的窗口,当窗口在数组上从左到右滑动时,如何快速求出每个窗口内的最大值或最小值?
1.3.2 单调队列的核心思想
我们以“滑动窗口最大值”为例来剖析单调队列的精髓。
假设有一个窗口,我们需要找到其中的最大值。如果使用暴力法,每次窗口滑动时都遍历一遍窗口内的所有元素,时间复杂度会是 \(O(n \cdot k)\)(其中 \(n\) 是数组长度,\(k\) 是窗口大小),在数据量大时会超时。
单调队列能将这个过程优化到 \(O(n)\) 的时间复杂度。它是如何做到的呢?关键在于它维护了一个“有潜力”成为最大值的候选者列表。
这个列表(用双端队列实现)有两个核心规则:
- 规则一(维护单调性):当一个新元素准备从队尾入队时,它会从队尾开始,将所有比它小的元素都“踢”出队列。然后,它自己再入队。这保证了队列中的元素从队头到队尾是单调递减的。
- 规则二(维护窗口范围):队头元素永远是当前窗口内的最大值。当队头元素的位置已经滑出当前窗口的左边界时,就需要将它从队头弹出(
pop_front
)。
为什么这个方法是正确的?
思考一下规则一:假设队列中已经有元素 a
和 b
(a
在 b
前面),它们都比新来的元素 c
小。由于 c
进入窗口的时间比 a
和 b
都晚,而 c
的值又比它们大。这意味着,在未来的任何包含 c
的窗口中,a
和 b
都不可能成为最大值了(因为有 c
"压着"它们)。所以,a
和 b
就成了“没有潜力”的元素,可以被安全地从队列中移除。
这个过程保证了队列里的元素不仅值是单调递减的,它们在原数组中的下标也是单调递增的。队头的元素,就是这个单调队列中最大且最“老”的元素。
1.3.3 算法伪代码(滑动窗口最大值)
假设有一个数组 A
和窗口大小 k
。我们用 dq
来存储元素的下标。
// 伪代码:滑动窗口最大值
// 数组 A 的下标从 1 到 n
// 窗口大小为 k
// dq 是一个双端队列,存储的是数组 A 的下标function slidingWindowMax(A, n, k):创建一个空的双端队列 dq创建一个空的结果数组 ans// 遍历数组 A 的每一个元素for i from 1 to n:// 规则一:维护单调性// 当队列不为空,且队尾下标对应的元素 <= 当前元素 A[i]while dq is not empty and A[dq.back()] <= A[i]:dq.pop_back() // 弹出队尾,因为它已经没有机会成为最大值了// 将当前元素的下标加入队尾dq.push_back(i)// 规则二:维护窗口范围// 如果队头元素的下标已经超出了窗口的左边界// 当前窗口的范围是 [i - k + 1, i]if dq.front() <= i - k:dq.pop_front() // 弹出队头// 当窗口形成后(即遍历过的元素个数 >= k),开始记录答案if i >= k:// 此时队头元素就是当前窗口的最大值ans.push_back(A[dq.front()])return ans
注意:单调队列中存储的是元素的下标而不是元素的值。这是因为我们需要根据下标来判断元素是否已经滑出窗口。
1.3.4 算法流程演示
我们用一个具体的例子来走一遍流程。
数组 A = [1, 3, -1, -3, 5, 3, 6, 7]
,窗口大小 k = 3
。
i = 1
,A[1] = 1
。队列为空,1
的下标入队。dq = [1]
。i = 2
,A[2] = 3
。A[2] > A[1]
,1
出队,2
入队。dq = [2]
。i = 3
,A[3] = -1
。A[3] < A[2]
,3
直接入队。dq = [2, 3]
。- 此时窗口
[1, 3]
形成,窗口范围是[1, 3]
。队头下标是 \(2\),在窗口内。最大值为A[2] = 3
。输出 3。
- 此时窗口
i = 4
,A[4] = -3
。A[4] < A[3]
,4
直接入队。dq = [2, 3, 4]
。- 窗口
[2, 4]
形成。队头下标是 \(2\),在窗口[2, 4]
内。最大值为A[2] = 3
。输出 3。
- 窗口
i = 5
,A[5] = 5
。A[5]
比A[4]
,A[3]
,A[2]
都大,所以4, 3, 2
依次出队。5
入队。dq = [5]
。- 窗口
[3, 5]
形成。队头下标是 \(5\),在窗口[3, 5]
内。最大值为A[5] = 5
。输出 5。
- 窗口
i = 6
,A[6] = 3
。A[6] < A[5]
,6
直接入队。dq = [5, 6]
。- 窗口
[4, 6]
形成。队头下标是 \(5\),在窗口[4, 6]
内。最大值为A[5] = 5
。输出 5。
- 窗口
i = 7
,A[7] = 6
。A[7] > A[6]
,6
出队。A[7] > A[5]
,5
出队。7
入队。dq = [7]
。- 窗口
[5, 7]
形成。队头下标是 \(7\),在窗口[5, 7]
内。最大值为A[7] = 6
。输出 6。
- 窗口
i = 8
,A[8] = 7
。A[8] > A[7]
,7
出队。8
入队。dq = [8]
。- 窗口
[6, 8]
形成。队头下标是 \(8\),在窗口[6, 8]
内。最大值为A[8] = 7
。输出 7。
- 窗口
最终输出的最大值序列为:3, 3, 5, 5, 6, 7
。
1.3.5 洛谷例题与题解
题目链接: P1886 滑动窗口 /【模板】单调队列
题目描述:
给定一个长度为 \(n\) 的数组和一个大小为 \(k\) 的窗口。窗口从数组的最左端滑到最右端。你需要求出窗口在每一次滑动时,窗口中的最大值和最小值。
输入格式:
第一行包含两个整数 \(n, k\),表示数组长度和窗口大小。
第二行包含 \(n\) 个整数,表示数组的元素。
输出格式:
两行。
第一行输出,每个窗口的最小值。
第二行输出,每个窗口的最大值。
题解思路:
这道题是单调队列的模板题。我们需要分别求出滑动窗口的最小值和最大值。
- 求最小值:需要维护一个队头到队尾单调递增的队列。当新元素入队时,把队尾所有比它大的元素都踢出去。
- 求最大值:需要维护一个队头到队尾单调递减的队列。当新元素入队时,把队尾所有比它小的元素都踢出去。(这正是我们上面详细分析的过程)
我们可以写两个函数,或者在一个循环里用两个单调队列分别处理。下面给出的代码是在一个主循环中用两个队列分别完成任务。
1.3.6 C++ 代码实现
#include <iostream>
#include <vector>
#include <deque>using namespace std;const int MAXN = 1000005;int n, k;
int a[MAXN];
deque<int> min_dq, max_dq; // min_dq 存最小值的候选项,max_dq 存最大值的候选项int main() {// 读入数据cin >> n >> k;for (int i = 1; i <= n; ++i) {cin >> a[i];}// --- 求滑动窗口最小值 ---for (int i = 1; i <= n; ++i) {// 维护单调递增性:新来的元素 a[i] 从队尾把比它大的都赶走while (!min_dq.empty() && a[min_dq.back()] >= a[i]) {min_dq.pop_back();}min_dq.push_back(i); // 将当前元素下标入队// 维护窗口范围:检查队头是否已经滑出窗口if (min_dq.front() <= i - k) {min_dq.pop_front();}// 当窗口形成后(i >= k),输出结果if (i >= k) {cout << a[min_dq.front()] << " ";}}cout << endl;// --- 求滑动窗口最大值 ---for (int i = 1; i <= n; ++i) {// 维护单调递减性:新来的元素 a[i] 从队尾把比它小的都赶走while (!max_dq.empty() && a[max_dq.back()] <= a[i]) {max_dq.pop_back();}max_dq.push_back(i); // 将当前元素下标入队// 维护窗口范围:检查队头是否已经滑出窗口if (max_dq.front() <= i - k) {max_dq.pop_front();}// 当窗口形成后(i >= k),输出结果if (i >= k) {cout << a[max_dq.front()] << " ";}}cout << endl;return 0;
}
代码解释:
- 代码中,我们开了两个
deque
:min_dq
和max_dq
,都用来存储数组下标。 - 为了逻辑清晰,我们用了两个独立的循环来分别计算最小值和最大值序列。在实际比赛中,也可以将两个过程合并到一个循环中以提高一点点效率,但逻辑会稍微复杂一些。
- 求最小值部分:
while (!min_dq.empty() && a[min_dq.back()] >= a[i])
这句是核心。它保证了min_dq
中的元素对应的值是单调递增的。因为如果一个又老(下标小)又大的元素存在,它一定不会是未来任何窗口的最小值,所以可以被淘汰。 - 求最大值部分:
while (!max_dq.empty() && a[max_dq.back()] <= a[i])
这句是核心。它保证了max_dq
中的元素对应的值是单调递减的。原理同上。 if (dq.front() <= i - k)
这句是用来判断队头下标是否过期的。i
是当前窗口的右边界,那么左边界就是i - k + 1
。如果队头的下标小于等于i - k
,说明它已经在窗口之外了,必须出队。if (i >= k)
这个判断确保我们只在窗口完全形成之后才开始输出结果。
通过单调队列,我们成功地将每个元素入队一次、出队一次,使得解决滑动窗口最值问题的总时间复杂度从 \(O(n \cdot k)\) 优化到了 \(O(n)\),这是一个巨大的提升。单调队列是动态规划优化的一个重要工具,掌握它对于解决更难的算法问题至关重要。
1.4 【6】优先队列
1.4.1 什么是优先队列?
在学习优先队列之前,我们先回顾一下队列(Queue)这种数据结构。队列是一种“先进先出”(First In First Out, FIFO)的线性表。这就像在食堂排队打饭,先到窗口的人先打到饭,后到的人后打饭。所有元素在队列中的地位都是平等的,唯一的区别就是它们进入队列的顺序。
然而,在现实世界的很多场景中,元素的“地位”并非平等。例如,在医院的急诊室,医生会优先处理病情更危重的病人,而不是严格按照病人挂号的先后顺序。一位心脏病突发的病人,即使比一位只是有点轻微擦伤的病人晚到,也应该被优先救治。
为了在计算机程序中模拟这种“按优先级处理”的场景,一种新的数据结构应运而生,它就是 优先队列(Priority Queue)。
顾名思义,优先队列中的每一个元素都有一个“优先级”。在进行出队操作时,它不再遵循“先进先出”的原则,而是将当前队列中优先级最高(或最低)的元素率先弹出。
我们可以将优先队列与栈(Stack)和普通队列(Queue)进行一个简单的对比:
数据结构 | 出队原则 | 生活中的例子 |
---|---|---|
栈 (Stack) | 后进先出 (LIFO) | 叠放的盘子,最后放上去的盘子最先被取用。 |
队列 (Queue) | 先进先出 (FIFO) | 排队买票,排在最前面的人最先买到票。 |
优先队列 (Priority Queue) | 优先级最高者先出 | 医院急诊室,病情最危重的病人最先被救治。 |
因此,优先队列是一种特殊的队列,它允许我们在任何时候插入一个元素,但只能访问并移除当前优先级最高的元素。
1.1.5 优先队列的实现:二叉堆
优先队列是一个抽象的数据结构概念,它可以通过多种方式实现,例如使用有序数组、链表等。但这些实现在插入或删除操作上效率不高。在信息学竞赛中,实现优先队列最常用、最高效的数据结构是 堆(Heap),特别是 二叉堆(Binary Heap)。
1. 什么是二叉堆?
二叉堆本质上是一棵完全二叉树,并且它需要满足堆属性。
-
完全二叉树:一棵深度为 \(k\) 的二叉树,如果它的第 \(1\) 层到第 \(k-1\) 层都是满的,并且第 \(k\) 层的节点都连续地集中在左边,那么它就是一棵完全二叉树。如下图所示,它非常“丰满”且“紧凑”。
●/ \● ●/ \ / ● ● ●
-
堆属性:堆属性规定了树中父节点和子节点之间的关系。它分为两种:
- 大根堆(Max-Heap):任意一个节点的值都 大于或等于 它的所有子节点的值。因此,根节点一定是整个堆中最大的元素。
- 小根堆(Min-Heap):任意一个节点的值都 小于或等于 它的所有子节点的值。因此,根节点一定是整个堆中最小的元素。
下面的左图是一个大根堆,右图是一个小根堆。
大根堆 小根堆100 10/ \ / \70 60 20 15/ \ / / \ /20 30 50 40 50 30
在信息学竞赛中,当我们提到“优先队列”,通常默认指的是用“大根堆”实现的、取出最大元素的队列。如果需要取出最小元素,则使用“小根堆”。
2. 二叉堆的存储
二叉堆最巧妙的地方在于,尽管它是一棵树,但我们不需要使用复杂的指针来存储它。由于它是完全二叉树,我们可以非常方便地用一个一维数组来表示。
我们将树的节点从上到下、从左到右依次编号,从 \(1\) 开始。然后将编号为 \(i\) 的节点存储在数组的第 \(i\) 个位置。
节点1 (arr[1])/ \节点2(arr[2]) 节点3(arr[3])/ \ / \
arr[4] arr[5] arr[6] arr[7]
在这种存储方式下,节点之间存在着优美的数学关系:
- 对于数组中下标为 \(i\) 的节点,它的父节点的下标是 \(\lfloor i/2 \rfloor\)。
- 对于数组中下标为 \(i\) 的节点,它的左子节点的下标是 \(2 \times i\)。
- 对于数组中下标为 \(i\) 的节点,它的右子节点的下标是 \(2 \times i + 1\)。
通过这些简单的计算,我们就可以在数组中模拟出树的父子关系,极大地节省了空间和编码复杂度。
1.4.3 堆的核心操作
以大根堆为例,堆的核心操作主要有两个:向上调整(Up-Heapify)和向下调整(Down-Heapify)。这两个操作是维持堆属性的关键。
1. 插入元素 (Push)
当向堆中插入一个新元素时,为了保持完全二叉树的结构,我们首先将这个新元素放在数组的末尾,也就是树的最底层、最右边的位置。
但是,这样做很可能会破坏大根堆的属性(新元素可能比它的父节点大)。因此,我们需要进行向上调整操作。
- 向上调整 (Up-Heapify):将新插入的节点(当前节点)和它的父节点进行比较。如果当前节点的值大于父节点,就交换它们的位置。然后继续将当前节点与新的父节点比较,如此循环,直到当前节点不再大于其父节点,或者它已经到达了堆顶(根节点)的位置。这个过程就像一个“气泡”不断上浮。
伪代码:Up(index)
while (index > 1 and heap[index] > heap[index / 2])swap(heap[index], heap[index / 2])index = index / 2
2. 删除堆顶元素 (Pop)
优先队列的 pop
操作总是删除优先级最高的元素,也就是堆顶元素。但是,如果我们直接删除根节点 heap[1]
,整棵树的结构就遭到了破坏。
正确的做法是:
- 记录下堆顶元素
heap[1]
的值,这是我们要返回的结果。 - 将数组的最后一个元素(树的最底层最右边的叶子节点)移动到堆顶的位置。
- 此时,新的堆顶元素很可能小于它的子节点,破坏了大根堆的属性。因此,我们需要进行向下调整。
- 向下调整 (Down-Heapify):将新的堆顶(当前节点)与它的左右子节点中值较大的那个进行比较。如果当前节点的值小于那个较大的子节点,就交换它们的位置。然后继续将当前节点与新的子节点比较,如此循环,直到当前节点的两个子节点都比它小,或者它已经成为了叶子节点。这个过程就像一块“石头”不断下沉。
伪代码:Down(index, size)
while (2 * index <= size) // 只要存在子节点child_index = 2 * index // 左子节点// 如果右子节点存在,且比左子节点大,则目标是右子节点if (child_index + 1 <= size and heap[child_index + 1] > heap[child_index])child_index = child_index + 1// 如果当前节点比它的两个孩子都大,则调整结束if (heap[index] >= heap[child_index])breakswap(heap[index], heap[child_index])index = child_index // 继续向下调整
所有这些操作的时间复杂度都与树的高度成正比。一个包含 \(N\) 个节点的完全二叉树,其高度大约是 \(\log_2 N\)。因此,插入和删除操作的时间复杂度都是非常高效的 \(O(\log N)\)。获取堆顶元素只需访问数组第一个元素,时间复杂度为 \(O(1)\)。
1.4.4 C++ STL 中的 priority_queue
在实际的编程竞赛中,我们通常不需要手动编写一个堆。C++ 的标准模板库(STL)中已经为我们提供了一个非常方便的容器:std::priority_queue
。
要使用它,需要包含头文件 <queue>
。
1. 基本用法
#include <iostream>
#include <queue>
#include <vector>using namespace std;int main() {// 默认是大根堆priority_queue<int> max_heap;max_heap.push(30);max_heap.push(100);max_heap.push(20);cout << "大根堆的堆顶元素是: " << max_heap.top() << endl; // 输出 100max_heap.pop(); // 弹出 100cout << "弹出后,堆顶元素是: " << max_heap.top() << endl; // 输出 30return 0;
}
2. 如何定义小根堆
priority_queue
默认是大根堆。如果我们想使用小根堆(用于取出最小值),需要提供额外的模板参数。其完整定义是:
priority_queue<Type, Container, Compare>
Type
: 存储的元素类型。Container
: 实现底层堆的容器,通常是vector<Type>
。Compare
: 比较函数对象,用于决定优先级。less<Type>
表示大根堆(默认),greater<Type>
表示小根堆。
定义一个小根堆的语法如下:
// 定义一个存储 int 类型的小根堆
priority_queue<int, vector<int>, greater<int>> min_heap;min_heap.push(30);
min_heap.push(100);
min_heap.push(20);cout << "小根堆的堆顶元素是: " << min_heap.top() << endl; // 输出 20
3. 常用成员函数
函数 | 功能描述 | 时间复杂度 |
---|---|---|
push(x) |
将元素 x 插入队列 |
\(O(\log N)\) |
pop() |
弹出队首元素(优先级最高的元素) | \(O(\log N)\) |
top() |
返回队首元素的引用 | \(O(1)\) |
empty() |
判断队列是否为空 | \(O(1)\) |
size() |
返回队列中元素的个数 | \(O(1)\) |
1.4.5 洛谷例题:P3378 【模板】堆
这道题目是优先队列(堆)的模板题,完美地契合了我们刚刚学习的内容。
题目描述
给定一个序列,你需要支持以下三种操作:
- 插入一个数 \(x\)。
- 输出当前序列中最小的数。
- 删除当前序列中最小的数。
分析
题目要求我们维护一个数据集合,并能快速地插入、查询最小值、删除最小值。这正是小根堆的典型应用场景。我们直接使用 C++ STL 中的 priority_queue
就可以轻松解决。
C++ 代码模板
#include <iostream>
#include <queue>
#include <vector>// 使用 using namespace std 是为了让初学者更容易理解代码
// 在大型项目中,推荐使用 std:: 前缀
using namespace std;int main() {// 关闭同步流,加速输入输出ios_base::sync_with_stdio(false);cin.tie(NULL);int n;cin >> n;// 定义一个小根堆,因为题目要求我们处理最小值priority_queue<int, vector<int>, greater<int>> min_heap;for (int i = 1; i <= n; ++i) {int op;cin >> op;if (op == 1) {int x;cin >> x;min_heap.push(x);} else if (op == 2) {// top() 操作返回的是最小的元素cout << min_heap.top() << "\n";} else { // op == 3// pop() 操作会删除最小的元素min_heap.pop();}}return 0;
}
解题思路
- 读取操作总数 \(N\)。
- 创建一个
int
类型的小根堆min_heap
,因为我们需要对最小值进行操作。 - 循环 \(N\) 次,每次读取一个操作指令
op
。 - 如果
op
是 \(1\),就再读取一个整数 \(x\),并调用min_heap.push(x)
将其插入堆中。 - 如果
op
是 \(2\),就调用min_heap.top()
获取堆顶(即最小值)并输出。 - 如果
op
是 \(3\),就调用min_heap.pop()
删除堆顶元素。
通过这个模板题,我们可以看到 priority_queue
的强大和便捷。它将复杂的堆操作封装起来,让我们能更专注于解决问题本身的逻辑。
1.5 【6】ST表 (Sparse Table)
1.5.1 什么是 ST 表?
ST 表(Sparse Table,稀疏表)是一种用于高效解决 静态区间查询 问题的数据结构。最经典的应用是 区间最值查询(Range Maximum/Minimum Query, RMQ)。
设想这样一个问题:给定一个长度为 \(N\) 的固定数组 \(A\),接下来会有 \(M\) 次询问,每次询问会给出两个下标 \(l\) 和 \(r\),要求你回答数组 \(A\) 在区间 \([l, r]\) 内的最大值(或最小值)是多少。
- 静态:这个词非常重要,它意味着数组 \(A\) 的元素在所有查询过程中都不会被修改。如果数组元素会发生变化,ST 表就不再适用了,需要使用线段树等更复杂的数据结构。
- 区间查询:询问的对象是数组的一个连续子区间。
如果用最朴素的暴力方法,每次询问都遍历一次区间 \([l, r]\),那么单次查询的时间复杂度是 \(O(N)\),总时间复杂度是 \(O(N \times M)\)。当 \(N\) 和 \(M\) 都很大时(例如 \(10^5\)),这种方法会严重超时。
ST 表通过 \(O(N \log N)\) 的预处理,可以实现 \(O(1)\) 的单次查询。这种用预处理时间换取查询时间的思想,在算法竞赛中非常常见。
1.5.2 ST 表的核心思想:倍增
ST 表的核心思想是 倍增(Binary Lifting)。倍增是一种“以 \(2\) 的幂次划分问题”的思想。比如,我们要从点 \(A\) 跳到点 \(B\),距离为 \(13\)。我们可以先跳 \(8\) (\(2^3\)),再跳 \(4\) (\(2^2\)),再跳 \(1\) (\(2^0\)),总共 \(3\) 次就跳到了。任何一个整数都可以被拆分成若干个 \(2\) 的幂次之和,这就是倍增思想的根基。
ST 表正是利用了这一点。它通过预处理,计算出数组中所有“长度为 \(2\) 的幂次”的区间的最大值。
我们定义一个二维数组 st[i][j]
,它表示的含义是:从数组下标 \(i\) 开始,长度为 \(2^j\) 的连续区间的最大值。
也就是说:
st[i][j] = max(A[i], A[i+1], ..., A[i + 2^j - 1])
有了这个定义,我们来看看如何计算 st
数组。
-
基础情况 (Base Case):当 \(j=0\) 时,区间的长度是 \(2^0 = 1\)。所以
st[i][0]
就表示从下标 \(i\) 开始,长度为 \(1\) 的区间的最大值,这显然就是A[i]
本身。
st[i][0] = A[i]
-
递推关系 (Recurrence Relation):如何计算
st[i][j]
呢?一个长度为 \(2^j\) 的大区间,可以被精确地拆分成两个长度为 \(2^{j-1}\) 的、相邻的小区间。- 第一个小区间:从 \(i\) 开始,长度为 \(2^{j-1}\)。它的最大值是
st[i][j-1]
。 - 第二个小区间:从 \(i + 2^{j-1}\) 开始,长度为 \(2^{j-1}\)。它的最大值是
st[i + 2^(j-1)][j-1]
。
整个大区间的最大值,就是这两个小区间最大值的较大者。
于是,我们得到了 ST 表的核心递推公式:
st[i][j] = max(st[i][j-1], st[i + 2^(j-1)][j-1])
- 第一个小区间:从 \(i\) 开始,长度为 \(2^{j-1}\)。它的最大值是
通过这个公式,我们就可以构建出整个 ST 表。
1.5.3 ST 表的构建(预处理)
构建过程就是填充 st
数组。根据递推公式,我们需要先知道所有长度为 \(2^{j-1}\) 的区间的最值,才能计算长度为 \(2^j\) 的区间。所以,我们应该把 \(j\) 作为外层循环。
伪代码:Build(A, N)
// 预计算 log2 的值,可以加速查询
log_table[1] = 0
for i from 2 to N:log_table[i] = log_table[i / 2] + 1// 初始化 j=0 的情况
for i from 1 to N:st[i][0] = A[i]// j 从 1 开始,表示区间长度从 2^1=2 开始
for j from 1 up to log_table[N]:// i 的范围要保证区间 [i, i + 2^j - 1] 不越界for i from 1 up to N - (1 << j) + 1:st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1])
预处理的时间复杂度是 \(O(N \log N)\),因为外层循环 \(\log N\) 次,内层循环 \(N\) 次。空间复杂度也是 \(O(N \log N)\)。
C++ 代码模板 (构建)
// 假设 MAXN 是数组最大长度,LOGN 是 log2(MAXN) 的最大值
const int MAXN = 200005;
const int LOGN = 18; // log2(200005) 约等于 17.6int a[MAXN];
int st[MAXN][LOGN];
int log_table[MAXN];void build(int n) {// 预处理 log_tablelog_table[1] = 0;for (int i = 2; i <= n; i++) {log_table[i] = log_table[i / 2] + 1;}// 初始化 j=0for (int i = 1; i <= n; i++) {st[i][0] = a[i];}// 递推计算for (int j = 1; j <= log_table[n]; j++) {for (int i = 1; i + (1 << j) - 1 <= n; i++) {// st[i][j] = max(st[i][j-1], st[i + 2^(j-1)][j-1])st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);}}
}
1.5.4 ST 表的查询
预处理完成后,如何进行 \(O(1)\) 的查询呢?
假设我们要查询区间 \([l, r]\) 的最大值。区间长度为 len = r - l + 1
。
我们可以找到一个最大的整数 \(k\),使得 \(2^k \le \text{len}\)。这个 \(k\) 可以通过 log_table[len]
快速得到。
现在,我们考虑两个长度为 \(2^k\) 的区间:
- 第一个区间:从 \(l\) 开始,长度为 \(2^k\)。即 \([l, l+2^k-1]\)。它的最大值是
st[l][k]
。 - 第二个区间:从 \(r-2^k+1\) 开始,长度为 \(2^k\)。即 \([r-2^k+1, r]\)。它的最大值是
st[r - (1 << k) + 1][k]
。
由于我们选择的 \(k\) 满足 \(2^k \le \text{len}\),所以 \(l+2^k-1 < r+1\) 和 \(r-2^k+1 > l-1\)。这意味着这两个区间必然会覆盖整个 \([l, r]\) 区间。它们可能会在中间有重叠部分。
对于求最大值(或最小值)的操作,一个元素被重复计算多次是不会影响最终结果的(例如 max(a, b, b, c) = max(a, b, c)
)。这种性质被称为 幂等性(Idempotence)。
因此,区间 \([l, r]\) 的最大值就等于这两个覆盖区间的最大值的较大者。
查询公式:
query(l, r) = max(st[l][k], st[r - 2^k + 1][k])
其中 k = log_table[r - l + 1]
。
由于 k
的计算和数组的访问都是 \(O(1)\) 的,所以整个查询操作的时间复杂度是 \(O(1)\)。
C++ 代码模板 (查询)
int query(int l, int r) {int len = r - l + 1;int k = log_table[len];return max(st[l][k], st[r - (1 << k) + 1][k]);
}
1.5.5 洛谷例题:P3865 【模板】ST表
这道题是 RMQ 问题的标准模板,用于检验对 ST 表的掌握程度。
题目描述
给定一个长度为 \(N\) 的数列,和 \(M\) 次询问,求出每一次询问的区间 \([l, r]\) 中的最大值。
分析
这道题是静态区间最值查询,完全符合 ST 表的应用场景。我们只需要按照上面学习的步骤,先构建 ST 表,然后对于每次询问,调用查询函数即可。
C++ 完整代码
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>using namespace std;const int MAXN = 100005;
const int LOGN = 17; // log2(100005) 约等于 16.6// st[i][j] 表示从 i 开始,长度为 2^j 的区间的最大值
int st[MAXN][LOGN + 1];
int log_table[MAXN];// 预处理 log 表
void precompute_log(int n) {log_table[1] = 0;for (int i = 2; i <= n; i++) {log_table[i] = log_table[i / 2] + 1;}
}// 构建 ST 表
void build(int n) {// j=0 的情况已经在主函数读入时处理for (int j = 1; j <= LOGN; j++) {for (int i = 1; i + (1 << j) - 1 <= n; i++) {st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);}}
}// 查询 [l, r] 区间的最大值
int query(int l, int r) {int k = log_table[r - l + 1];return max(st[l][k], st[r - (1 << k) + 1][k]);
}int main() {// 加速输入输出ios_base::sync_with_stdio(false);cin.tie(NULL);int n, m;cin >> n >> m;precompute_log(n);// 读入原始数据,并初始化 st 表 j=0 的情况for (int i = 1; i <= n; i++) {cin >> st[i][0];}// O(N log N) 预处理build(n);// M 次 O(1) 查询for (int i = 1; i <= m; i++) {int l, r;cin >> l >> r;cout << query(l, r) << "\n";}return 0;
}
解题思路
- 定义好
st
数组和log_table
数组。 - 在
main
函数中,首先读入 \(N\) 和 \(M\)。 - 调用
precompute_log(n)
预先计算好所有需要的 \(\log_2\) 值,避免在查询时重复计算。 - 读入 \(N\) 个数,直接存入
st[i][0]
,完成 ST 表的基础情况初始化。 - 调用
build(n)
函数,完成整个 ST 表的预处理。 - 循环 \(M\) 次,每次读入查询区间 \([l, r]\),调用
query(l, r)
函数计算并输出结果。
ST 表是一个优雅且高效的数据结构,它将倍增思想和动态规划的预处理结合起来,是信息学竞赛中解决静态 RMQ 问题的有力武器。
第二节 集合与特殊树
2.1 【6】并查集
2.1.1 什么是并查集?
并查集(Disjoint Set Union, DSU)是一种非常精妙的树形数据结构,主要用于处理一些不相交集合(Disjoint Sets)的合并(Union)及查询(Find)问题。
想象一下,在江湖中有许多侠客,一开始每个人都自成一派。然后,一些侠客之间会结成联盟,形成一个个小门派。随着时间的推移,一些小门派之间又会合并,形成更大的门派。在这个过程中,我们经常需要关心两个问题:
\(1\). 查询(Find):某位侠客现在属于哪个门派?或者说,两位侠客是否属于同一个门派?
\(2\). 合并(Union):将两个不同的门派合并成一个。
并查集就是解决这类问题的利器。它能以接近 \(O(1)\) 的惊人效率来处理这两个操作。
2.1.2 并查集的实现原理
并查集的核心思想是用一个数组 fa
(father) 来维护一个“代表元”构成的森林。每个集合被表示为一棵树,树的根节点就是这个集合的“代表元”(或者叫“掌门人”)。
- 数据结构:我们使用一个整型数组
fa[]
。fa[i]
存储的是元素 \(i\) 的父节点。 - 规定:如果一个元素的父节点是它自己,即
fa[i] == i
,那么这个元素就是它所在集合的代表元(根节点)。
1. 初始化
最开始,每个元素都各自属于一个独立的集合。就像江湖之初,每个侠客都自成一派,自己就是自己的掌门人。所以,对于 \(1\) 到 \(n\) 的所有元素,我们初始化 fa[i] = i
。
伪代码:
procedure Initialize(n)for i from 1 to nfa[i] ← iend for
end procedure
2. 查找(Find)操作
查找操作的目标是找到一个元素所在集合的代表元。这就像去问一个侠客:“你的掌门人是谁?”如果他不是掌门人,他会指向他的“上级”,我们再去问他的“上级”,如此反复,直到找到那个“上级”就是自己的那个人,他就是最终的掌门人。
这个过程在数据结构中,就是从一个节点出发,不断地沿着父节点指针 fa
向上寻找,直到找到根节点(即 fa[x] == x
的那个节点 \(x\))为止。
伪代码 (朴素版):
function Find(x)while fa[x] ≠ xx ← fa[x]end whilereturn x
end function
3. 合并(Union)操作
合并操作是将两个元素所在的集合合并成一个。比如,我们要合并侠客 \(x\) 和侠客 \(y\) 所在的门派。
步骤很简单:
\(1\). 先分别找到 \(x\) 和 \(y\) 的掌门人,记为 root_x
和 root_y
。
\(2\). 如果他们已经是同一个掌门人 (root_x == root_y
),说明他们本就在同一个门派,无需任何操作。
\(3\). 如果他们不是同一个掌门人,那么就将一个门派并入另一个。例如,我们可以让 root_x
的掌门人变成 root_y
,即 fa[root_x] = root_y
。这样,原来所有属于 root_x
门派的成员,通过他们的查找路径,最终也都能找到 root_y
这位新的总掌门人。
伪代码 (朴素版):
procedure Union(x, y)root_x ← Find(x)root_y ← Find(y)if root_x ≠ root_y thenfa[root_x] ← root_yend if
end procedure
2.1.3 并查集的优化
上述朴素的实现方法在某些极端情况下效率会很低。例如,如果我们将 \(1, 2, 3, \dots, n\) 依次合并,可能会形成一条长长的链:fa[1]=2
, fa[2]=3
, ..., fa[n-1]=n
。此时,查找元素 \(1\) 的代表元需要一步步走到 \(n\),时间复杂度为 \(O(n)\),这显然不是我们想要的。因此,必须进行优化。
1. 路径压缩(Path Compression)
这是并查集最重要的优化。核心思想是:在查找一个元素的根节点的过程中,将这条查找路径上的所有节点都直接指向根节点。
这样做的好处是,下次再查找这些节点时,只需要一步就能找到根节点。这极大地压缩了树的高度,使其变得非常扁平。
伪代码 (路径压缩版 Find):
这个优化可以用递归非常优雅地实现。
function Find(x)if fa[x] == x thenreturn xelsefa[x] ← Find(fa[x]) // 在回溯时将沿途节点的父节点设为根节点return fa[x]end if
end function
2. 按秩合并(Union by Rank/Size)
另一个优化是在合并时进行的。当我们合并 root_x
和 root_y
两个集合时,是把 \(x\) 的树接到 \(y\) 上,还是反过来?一个启发式的想法是:总是将较小的树合并到较大的树上。这样可以有效地避免树的高度增长过快。
“大小”可以用两种方式来衡量:
- 按大小(Size)合并:用一个数组
siz[]
记录以每个节点为根的树的大小(节点数)。合并时,将节点数少的树的根节点,连接到节点数多的树的根节点上。 - 按秩(Rank)合并:用一个数组
rnk[]
记录以每个节点为根的树的高度(秩)。合并时,将高度低的树的根,连接到高度高的树的根上。
实践中,按大小合并 更为常用且实现简单。
伪代码 (按大小合并版 Union):
procedure Initialize(n)for i from 1 to nfa[i] ← isiz[i] ← 1 // 初始化每个集合大小为 1end for
end procedureprocedure Union(x, y)root_x ← Find(x)root_y ← Find(y)if root_x ≠ root_y then// 将小树合并到大树if siz[root_x] < siz[root_y] thenfa[root_x] ← root_ysiz[root_y] ← siz[root_y] + siz[root_x]elsefa[root_y] ← root_xsiz[root_x] ← siz[root_x] + siz[root_y]end ifend if
end procedure
复杂度分析
同时使用路径压缩和按秩(或按大小)合并的并查集,其单次操作的平均时间复杂度可以证明是 \(O(\alpha(n))\),其中 \(\alpha(n)\) 是反阿克曼函数。这个函数的增长速度极其缓慢,对于在宇宙中所有可观测到的原子数量级别的 \(n\),\(\alpha(n)\) 的值都不会超过 \(5\)。因此,我们可以认为其时间复杂度接近常数级别 \(O(1)\),效率极高。
2.1.4 C++ 代码模板
下面是一个包含了路径压缩和按大小合并的并查集模板。
#include <iostream>
#include <vector>using namespace std;const int MAXN = 100005; // 假设元素数量不超过 100005int fa[MAXN]; // 存储父节点
int siz[MAXN]; // 存储以该节点为根的集合的大小// 初始化 1 到 n 的并查集
void init(int n) {for (int i = 1; i <= n; ++i) {fa[i] = i;siz[i] = 1;}
}// 查找x的根节点(带路径压缩)
int find(int x) {if (fa[x] == x) {return x;}// 递归查找根节点,同时将路径上的节点直接指向根节点return fa[x] = find(fa[x]);
}// 合并x和y所在的集合(按大小合并)
void unite(int x, int y) {int root_x = find(x);int root_y = find(y);if (root_x != root_y) {// 将小集合合并到大集合if (siz[root_x] < siz[root_y]) {fa[root_x] = root_y;siz[root_y] += siz[root_x];} else {fa[root_y] = root_x;siz[root_x] += siz[root_y];}}
}// 判断x和y是否在同一个集合
bool is_same_set(int x, int y) {return find(x) == find(y);
}int main() {// 这是一个使用示例,并非完整题目代码int n = 10; // 假设有 10 个元素init(n);unite(1, 2);unite(3, 4);unite(1, 3);if (is_same_set(2, 4)) {cout << "元素2和元素4在同一个集合中。" << endl;} else {cout << "元素2和元素4不在同一个集合中。" << endl;}if (is_same_set(1, 5)) {cout << "元素1和元素5在同一个集合中。" << endl;} else {cout << "元素1和元素5不在同一个集合中。" << endl;}return 0;
}
2.1.5 洛谷例题精讲
题目:P3367 【模板】并查集
题目描述
如题,现在有 \(N\) 个元素,编号从 \(1\) 到 \(N\)。你需要进行 \(M\) 次操作,操作有两种:
\(1\). 1 x y
:将元素 \(x\) 和元素 \(y\) 所在的集合合并。
\(2\). 2 x y
:询问元素 \(x\) 和元素 \(y\) 是否在同一个集合中。
输入格式
第一行包含两个整数 \(N, M\),表示有 \(N\) 个元素和 \(M\) 次操作。
接下来 \(M\) 行,每行包含三个整数 \(Z, X, Y\)。
当 \(Z=1\) 时,将 \(X\) 和 \(Y\) 所在的集合合并。
当 \(Z=2\) 时,询问 \(X\) 和 \(Y\) 是否在同一个集合中。
输出格式
对于每个 \(Z=2\) 的操作,如果 \(X\) 和 \(Y\) 在同一个集合中,输出一行 Y
;否则输出一行 N
。
分析
这道题是并查集最直接、最经典的应用。
- \(N\) 个元素对应并查集中的 \(N\) 个节点。
- 操作
1 x y
就是调用unite(x, y)
函数。 - 操作
2 x y
就是判断find(x)
是否等于find(y)
,即调用is_same_set(x, y)
函数。
我们直接套用上面给出的带有路径压缩和按大小合并的模板即可解决。
题解代码
#include <iostream>using namespace std;const int MAXN = 10001; // 题目数据范围 N <= 10000int fa[MAXN];
int siz[MAXN]; // 按大小合并的辅助数组,本题也可不用,但好习惯void init(int n) {for (int i = 1; i <= n; ++i) {fa[i] = i;siz[i] = 1; // 即使不用按大小合并,初始化fa数组是必须的}
}int find(int x) {if (fa[x] == x) {return x;}return fa[x] = find(fa[x]); // 路径压缩
}void unite(int x, int y) {int root_x = find(x);int root_y = find(y);if (root_x != root_y) {// 直接合并,不使用按大小合并也足以通过本题fa[root_x] = root_y;}
}int main() {// 为了提高读写效率ios_base::sync_with_stdio(false);cin.tie(NULL);int n, m;cin >> n >> m;init(n);for (int i = 0; i < m; ++i) {int z, x, y;cin >> z >> x >> y;if (z == 1) {unite(x, y);} else { // z == 2if (find(x) == find(y)) {cout << "Y" << '\n';} else {cout << "N" << '\n';}}}return 0;
}
2.2 【6】二叉堆
2.2.1 什么是二叉堆?
二叉堆(Binary Heap)是一种特殊的树形数据结构。尽管它的名字里有“二叉”二字,但它通常不是用指针链接的二叉树来实现的,而是用数组来实现。二叉堆是一个满足以下两个性质的完全二叉树:
\(1\). 结构性:它必须是一棵完全二叉树。完全二叉树指的是,除了最后一层外,其他各层节点数都达到最大,并且最后一层的节点都连续集中在左侧。这个性质使得它能被高效地存储在数组中。
\(2\). 堆序性(Heap Property):树中任意一个节点的值都必须不大于(或不小于)其所有子节点的值。
* 如果任意节点的值都不大于其子节点的值,我们称之为小根堆(Min-Heap)。堆顶元素是整个堆中的最小值。
* 如果任意节点的值都不小于其子节点的值,我们称之为大根堆(Max-Heap)。堆顶元素是整个堆中的最大值。
二叉堆最常见的应用是实现优先队列(Priority Queue),它允许我们快速地插入一个元素,并快速地查询和删除当前集合中的最值(最大值或最小值)。
2.2.2 二叉堆的实现原理
1. 数组存储
由于二叉堆是完全二叉树,我们可以用一个数组来存储它,而不需要指针。节点之间的父子关系可以通过数组下标的计算来确定。通常我们选择从下标 \(1\) 开始存储,这样关系会非常简洁:
- 节点 \(i\) 的父节点是 \(\lfloor i/2 \rfloor\)。
- 节点 \(i\) 的左子节点是 \(2 \times i\)。
- 节点 \(i\) 的右子节点是 \(2 \times i + 1\)。
2. 核心操作
我们以小根堆为例来讲解其核心操作。大根堆的原理完全对称。
-
插入元素(push)
- 将新元素放到数组的末尾(即完全二叉树最后一个位置的后面)。
- 新元素可能会破坏堆序性。因此,需要将它与它的父节点比较。如果它比父节点小,就交换它们的位置。
- 重复这个过程,不断地将该元素向上“调整”,直到它不再小于其父节点,或者它已经到达了堆顶(下标为 \(1\) 的位置)。这个过程称为上浮(sift-up)。
-
删除堆顶元素(pop)
- 堆顶元素(数组下标为 \(1\) 的元素)是最小值,我们想删除它。
- 为了保持完全二叉树的结构,我们不能直接删除堆顶。正确的做法是:将数组的最后一个元素移动到堆顶的位置,并让堆的大小减 \(1\)。
- 此时,新的堆顶元素很可能不满足堆序性(它可能比它的子节点大)。
- 我们需要将这个新的堆顶元素向下“调整”。将它与它的左右子节点中较小的一个进行比较。如果它比这个较小的子节点大,就交换它们的位置。
- 重复这个过程,不断地将该元素向下“调整”,直到它的所有子节点都比它大,或者它已经成为叶子节点。这个过程称为下沉(sift-down)。
复杂度分析
二叉堆是一棵近似平衡的二叉树,其高度为 \(O(\log n)\)。无论是上浮还是下沉操作,元素移动的距离最多就是树的高度。因此,插入和删除操作的时间复杂度都是 \(O(\log n)\)。获取堆顶元素(最值)的操作,只需要访问数组的第一个元素,时间复杂度为 \(O(1)\)。
2.2.3 C++ 代码模板
下面是一个手写的小根堆模板。
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;const int MAXN = 1000005;int h[MAXN]; // 数组模拟堆,从下标1开始
int heap_size = 0; // 堆中元素的数量// 上浮操作,调整位置idx的元素
void sift_up(int idx) {// 当idx不是根节点(idx > 1) 且 当前节点比父节点小while (idx > 1 && h[idx] < h[idx / 2]) {swap(h[idx], h[idx / 2]);idx /= 2; // 继续向上看}
}// 下沉操作,调整位置idx的元素
void sift_down(int idx) {while (2 * idx <= heap_size) { // 保证idx有左孩子int son = 2 * idx; // son先指向左孩子// 如果右孩子存在,且比左孩子更小,则son指向右孩子if (son + 1 <= heap_size && h[son + 1] < h[son]) {son++;}// 如果当前节点比它的两个孩子中较小的那个还要小,则满足堆序性,停止下沉if (h[idx] <= h[son]) {break;}// 否则,交换并继续下沉swap(h[idx], h[son]);idx = son;}
}// 插入一个元素
void push(int val) {heap_size++;h[heap_size] = val;sift_up(heap_size);
}// 删除堆顶元素
void pop() {if (heap_size == 0) return; // 堆为空h[1] = h[heap_size]; // 将最后一个元素移到堆顶heap_size--;sift_down(1); // 对新的堆顶执行下沉操作
}// 获取堆顶元素
int top() {if (heap_size > 0) {return h[1];}return -1; // 表示堆为空
}// 检查堆是否为空
bool empty() {return heap_size == 0;
}int main() {// 使用示例push(30);push(10);push(20);push(5);while (!empty()) {cout << top() << " ";pop();}// 输出应为: 5 10 20 30cout << endl;return 0;
}
提示:在 C++ 的 STL(标准模板库)中,已经提供了 priority_queue
容器,它底层就是用二叉堆实现的。在竞赛中,为了快速开发,可以直接使用 priority_queue
。但理解并能手写二叉堆是信息学学习中非常重要的一环。
#include <queue> // 使用STL中的priority_queue
// priority_queue<int> max_heap; // 默认是大根堆
// priority_queue<int, vector<int>, greater<int>> min_heap; // 小根堆
2.2.4 洛谷例题精讲
题目:P3378 【模板】堆
题目描述
你需要实现一个数据结构,支持以下 \(3\) 种操作:
\(1\). 1 x
:插入一个数 \(x\)。
\(2\). 2
:输出当前集合中最小的数。
\(3\). 3
:删除当前集合中最小的数。
输入格式
第一行一个整数 \(N\),表示操作的总数。
接下来 \(N\) 行,每行包含 \(1\) 或 \(2\) 个整数,表示一个操作。
输出格式
对于每个操作 \(2\),输出一个对应的答案。
分析
这道题完美地对应了小根堆的三个基本操作:
- 操作
1 x
:对应堆的push(x)
操作。 - 操作
2
:对应堆的top()
操作。 - 操作
3
:对应堆的pop()
操作。
因此,我们可以直接使用手写的二叉堆模板或者 STL 中的 priority_queue
来解决。
题解代码 (使用手写模板)
#include <iostream>
#include <algorithm>using namespace std;const int MAXN = 1000005;int h[MAXN];
int heap_size = 0;void sift_up(int idx) {while (idx > 1 && h[idx] < h[idx / 2]) {swap(h[idx], h[idx / 2]);idx /= 2;}
}void sift_down(int idx) {while (2 * idx <= heap_size) {int son = 2 * idx;if (son + 1 <= heap_size && h[son + 1] < h[son]) {son++;}if (h[idx] <= h[son]) {break;}swap(h[idx], h[son]);idx = son;}
}void push(int val) {heap_size++;h[heap_size] = val;sift_up(heap_size);
}void pop() {if (heap_size > 0) {h[1] = h[heap_size];heap_size--;sift_down(1);}
}int top() {if (heap_size > 0) {return h[1];}return -1; // 题目保证操作合法,不会在空堆时查询
}int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);int n;cin >> n;for (int i = 0; i < n; ++i) {int op;cin >> op;if (op == 1) {int x;cin >> x;push(x);} else if (op == 2) {cout << top() << '\n';} else { // op == 3pop();}}return 0;
}
2.3 【6】树状数组
2.3.1 什么是树状数组?
树状数组(Binary Indexed Tree, BIT),又称芬威克树(Fenwick Tree),是一种能够高效地完成以下两种操作的数据结构:
\(1\). 单点修改:给序列中的某一个元素加上一个值(更新)。
\(2\). 区间查询:查询序列中某一个前缀的和(例如,从第 \(1\) 个元素到第 \(k\) 个元素的和)。
如果用普通数组来处理,单点修改是 \(O(1)\),但查询前缀和是 \(O(n)\);如果用前缀和数组,查询是 \(O(1)\),但每次单点修改都需要更新后续所有前缀和,是 \(O(n)\)。树状数组则可以将这两种操作的时间复杂度都优化到 \(O(\log n)\)。
树状数组的思想非常巧妙,它通过一种特殊的二进制划分,让每个节点管理一个特定长度的区间,从而实现了对数级的效率。
2.3.2 树状数组的实现原理
1. lowbit
操作
树状数组的精髓在于 lowbit
操作。lowbit(x)
函数返回 \(x\) 的二进制表示中,最低位的 \(1\) 以及它后面的所有 \(0\) 组成的数。例如:
- \(x = 6\),二进制是
110
。最低位的 \(1\) 在第二位,所以lowbit(6)
是10
(二进制),即 \(2\)。 - \(x = 12\),二进制是
1100
。最低位的 \(1\) 在第三位,所以lowbit(12)
是100
(二进制),即 \(4\)。
在计算机中,利用位运算可以非常快速地计算 lowbit
:
lowbit(x) = x & (-x)
这是一个基于补码表示的位运算技巧。
2. 树状数组的结构
我们用一个数组 C[]
来表示树状数组。C[x]
存储的是原数组 A
中一个特定区间的和。这个区间是 (x - lowbit(x), x]
,即从 x - lowbit(x) + 1
到 x
,长度为 lowbit(x)
。
例如:
C[1]
管辖A[1]
。C[2]
管辖A[2]
和A[1]
。区间是(2-lowbit(2), 2]
即(0, 2]
。C[3]
管辖A[3]
。C[4]
管辖A[1]
到A[4]
。区间是(4-lowbit(4), 4]
即(0, 4]
。C[6]
管辖A[5]
到A[6]
。区间是(6-lowbit(6), 6]
即(4, 6]
。
3. 单点修改(add)
当我们要给原数组的 A[x]
加上一个值 k
时,我们需要更新所有管辖了 A[x]
的 C
数组的节点。
哪些节点管辖了 A[x]
呢?可以发现,需要更新的节点是 C[x]
, C[x + lowbit(x)]
, C[x + lowbit(x) + lowbit(x + lowbit(x))]
, ...
所以,修改操作就是从 \(x\) 开始,不断地 x = x + lowbit(x)
,并对相应的 C[x]
加上 k
,直到 \(x\) 超出数组范围。
伪代码:
procedure Add(x, k)while x ≤ nC[x] ← C[x] + kx ← x + lowbit(x)end while
end procedure
4. 前缀和查询(query)
当我们要查询前缀和 Sum(x)
,即 A[1] + A[2] + ... + A[x]
时,我们可以通过组合 C
数组中的若干个节点来得到。
Sum(x) = C[x] + C[x - lowbit(x)] + C[x - lowbit(x) - lowbit(x - lowbit(x))] + ...
查询操作就是从 \(x\) 开始,不断地 x = x - lowbit(x)
,累加 C[x]
的值,直到 \(x\) 变成 \(0\)。
伪代码:
function Query(x)sum ← 0while x > 0sum ← sum + C[x]x ← x - lowbit(x)end whilereturn sum
end function
复杂度分析
由于每次 add
或 query
操作,x
的二进制表示中至少会消去一个最低位的 \(1\),而 \(n\) 的二进制表示最多有 \(\log n\) 位,所以这两个操作的时间复杂度都是 \(O(\log n)\)。
区间和查询
如果要查询区间 [L, R]
的和,可以利用前缀和的思想,结果为 Query(R) - Query(L - 1)
。
2.3.3 C++ 代码模板
#include <iostream>using namespace std;const int MAXN = 500005;int n; // 数组大小
long long c[MAXN]; // 树状数组,注意数据范围可能需要long long// lowbit函数
int lowbit(int x) {return x & (-x);
}// 单点增加:给A[x]增加k
void add(int x, int k) {while (x <= n) {c[x] += k;x += lowbit(x);}
}// 前缀和查询:查询A[1]到A[x]的和
long long query(int x) {long long sum = 0;while (x > 0) {sum += c[x];x -= lowbit(x);}return sum;
}int main() {// 使用示例n = 10;// 假设原数组 A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}// 初始化树状数组for (int i = 1; i <= n; ++i) {int val;// 假设这里能读到原数组的值// cin >> val;val = i;add(i, val);}// 查询前5个数的和 (1+2+3+4+5 = 15)cout << "Sum of first 5 elements: " << query(5) << endl;// 给第3个数加上5 (A[3]从3变为8)add(3, 5);// 再次查询前5个数的和 (1+2+8+4+5 = 20)cout << "Sum of first 5 elements after update: " << query(5) << endl;// 查询区间[3, 7]的和// A数组现在是 {1, 2, 8, 4, 5, 6, 7, 8, 9, 10}// Sum[3,7] = 8+4+5+6+7 = 30// query(7) - query(2)cout << "Sum of range [3, 7]: " << query(7) - query(2) << endl;return 0;
}
2.3.4 洛谷例题精讲
题目:P3374 【模板】树状数组 1
题目描述
已知一个数列,你需要进行下面两种操作:
\(1\). 1 x k
:将第 \(x\) 个数加上 \(k\)。
\(2\). 2 x y
:输出区间 [x, y]
内每个数的和。
输入格式
第一行包含两个整数 \(N, M\),分别表示该数列数字的个数和操作的总个数。
第二行包含 \(N\) 个用空格分隔的整数,其中第 \(i\) 个数字表示数列第 \(i\) 项的初始值。
接下来 \(M\) 行每行包含 \(3\) 个整数,表示一个操作。
分析
这道题是树状数组的直接应用。
- 初始化:题目给出了初始数列。我们可以遍历一遍初始数列,对每个数
A[i]
,调用一次add(i, A[i])
来构建树状数组。 - 操作
1 x k
:这对应了树状数组的单点修改,直接调用add(x, k)
即可。 - 操作
2 x y
:这对应了树状数组的区间查询,结果为query(y) - query(x - 1)
。
题解代码
#include <iostream>using namespace std;const int MAXN = 500005;int n, m;
long long c[MAXN];int lowbit(int x) {return x & (-x);
}void add(int x, int k) {while (x <= n) {c[x] += k;x += lowbit(x);}
}long long query(int x) {long long sum = 0;while (x > 0) {sum += c[x];x -= lowbit(x);}return sum;
}int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);cin >> n >> m;// 初始化树状数组for (int i = 1; i <= n; ++i) {int val;cin >> val;add(i, val);}for (int i = 0; i < m; ++i) {int op, x, y;cin >> op >> x >> y;if (op == 1) {add(x, y); // y在这里是增量k} else { // op == 2cout << query(y) - query(x - 1) << '\n';}}return 0;
}
2.4 【6】线段树
2.4.1 什么是线段树?
在程序设计竞赛中,我们经常会遇到一类关于 区间(Interval) 的问题。例如,给定一个序列,要求你反复地对序列中的某一个区间进行操作(比如求和、求最大值),或者修改序列中某个元素的值。
如果序列的长度是 \(N\) ,每次查询的区间长度是 \(M\) 。一个朴素的想法是,每次查询都用一个循环遍历区间 [L, R]
,时间复杂度为 \(O(M)\) 。如果需要修改,就直接修改数组中的值,时间复杂度为 \(O(1)\)。但如果查询次数非常多,比如达到 \(Q\) 次,总时间复杂度可能高达 \(O(Q \times N)\),这在 \(N\) 和 \(Q\) 都很大(例如 \(10^5\))时是无法接受的。
线段树(Segment Tree)是一种专门用于解决这类问题的二叉树结构。它能够在 \(O(\log N)\) 的时间内完成区间查询和单点修改,极大地提高了效率。
顾名思义,线段树是用来存放“线段”或“区间”信息的树。它的每个节点都代表了原始序列中的一个区间。
2.4.2 线段树的结构
线段树是一棵完美的二叉树(Complete Binary Tree)。
- 根节点代表整个序列的区间,例如
[1, N]
。 - 树中的每一个非叶子节点
[L, R]
,它的左子节点代表的区间是[L, M]
,右子节点代表的区间是[M+1, R]
,其中 \(M = \lfloor \frac{L+R}{2} \rfloor\) (即 \(L\) 和 \(R\) 的中点,向下取整)。这种“一分为二”的思想,是分治法(Divide and Conquer)的体现。 - 叶子节点代表长度为 1 的区间,即
[i, i]
,它存储了原始序列中第 \(i\) 个元素的值。
如何存储线段树?
由于线段树是一棵完美的二叉树,所以它非常适合用一个数组来存储。类似堆的存储方式:
- 根节点的编号为 1。
- 对于编号为 \(p\) 的节点,它的左子节点编号为 \(2p\)(或写作
p << 1
),右子节点编号为 \(2p+1\)(或写作p << 1 | 1
)。
空间大小:一个长度为 \(N\) 的序列,构建出的线段树大约需要 \(4N\) 的存储空间。这是一个经验性的结论,可以确保在 \(N\) 的任何取值下,树的节点都不会超出数组范围。
2.4.3 线段树的核心操作
线段树主要有三个核心操作:建树(Build)、查询(Query)、修改(Update)。下面我们以最常见的“区间求和”为例进行讲解。
1. 建树 (Build)
建树是一个递归的过程。从根节点(代表区间 [1, N]
)开始:
- 如果当前区间
[L, R]
的长度为 1(即 \(L=R\)),说明到达了叶子节点。该节点的值就等于原始序列中A[L]
的值。 - 如果 \(L \neq R\),则递归地为左子区间
[L, M]
和右子区间[M+1, R]
建树。当左右子树都建好后,当前节点的值就等于它两个子节点的值之和。
【伪代码】
BUILD(p, L, R)// p 是当前节点编号,[L, R] 是它代表的区间IF L == R THENtree[p] = A[L]RETURNEND IFM = (L + R) / 2BUILD(2*p, L, M) // 递归建左子树BUILD(2*p+1, M+1, R) // 递归建右子树tree[p] = tree[2*p] + tree[2*p+1] // 用子节点信息更新当前节点
2. 单点修改 (Update)
当需要修改序列中第 idx
个元素的值为 val
时,也需要一个递归过程来更新树中所有包含这个点信息的节点。
- 从根节点开始查找。
- 如果当前节点
[L, R]
代表的区间包含了idx
,则继续向下。判断idx
是在左子区间[L, M]
还是右子区间[M+1, R]
,然后递归地进入相应的子树进行修改。 - 当递归到达叶子节点
[idx, idx]
时,直接修改它的值。 - 在递归返回的过程中,沿途更新所有祖先节点的值(等于其左右孩子节点值之和)。
【伪代码】
UPDATE(p, L, R, idx, val)// p: 当前节点编号, [L,R]: 当前区间// idx: 要修改的元素下标, val: 新的值IF L == R THENtree[p] = valRETURNEND IFM = (L + R) / 2IF idx <= M THENUPDATE(2*p, L, M, idx, val) // idx 在左子区间ELSEUPDATE(2*p+1, M+1, R, idx, val) // idx 在右子区间END IFtree[p] = tree[2*p] + tree[2*p+1] // 回溯时更新父节点
3. 区间查询 (Query)
这是线段树最精髓的操作。当要查询区间 [queryL, queryR]
的和时:
- 从根节点开始。
- 若当前节点
p
代表的区间[L, R]
完全被查询区间[queryL, queryR]
包含,即queryL <= L
且R <= queryR
,那么这个节点的值就是我们需要的一部分,直接返回tree[p]
。 - 若当前区间与查询区间没有交集,则返回一个不影响结果的初始值(对于求和,是0)。
- 若当前区间与查询区间有部分交集,则问题无法在当前层解决。需要递归地到它的左右子节点去查询,并将左右子树返回的结果合并(相加)。
【伪代码】
QUERY(p, L, R, queryL, queryR)// p: 当前节点, [L,R]: 当前区间// [queryL, queryR]: 目标查询区间// 1. 完全包含IF queryL <= L AND R <= queryR THENRETURN tree[p]END IF// 2. (隐式) 无交集的情况会在下面递归中处理,最终返回 0M = (L + R) / 2sum = 0// 3. 部分交集,需要递归IF queryL <= M THEN // 左子树与查询区间有交集sum = sum + QUERY(2*p, L, M, queryL, queryR)END IFIF queryR > M THEN // 右子树与查询区间有交集sum = sum + QUERY(2*p+1, M+1, R, queryL, queryR)END IFRETURN sum
这三个操作的时间复杂度都是 \(O(\log N)\),因为树的高度是 \(O(\log N)\),每次操作都类似在树上从根走到叶子的过程。
2.4.4 进阶:懒惰标记(Lazy Propagation)
上面的修改操作是“单点修改”。如果我们需要对一个区间进行修改,比如将 [L, R]
内的每个数都加上 val
,怎么办?
如果对区间内的每个点都进行一次单点修改,时间复杂度会退化到 \(O(N \log N)\),优势尽失。
这时就需要懒惰标记(Lazy Propagation)。
核心思想:如果要修改的区间 [updateL, updateR]
恰好完全覆盖了当前节点 p
代表的区间 [L, R]
,我们不去递归修改它的子孙节点,而是在当前节点 p
上打一个“标记”(tag)。这个标记代表“该节点的所有子孙节点都需要进行某个修改,但我先不下去,等需要的时候再说”。
具体操作:
-
修改 (Range Update):
- 当修改区间完全覆盖当前节点区间时,更新当前节点的值(例如,区间和
tree[p] += (R - L + 1) * val
),并给它打上懒惰标记(例如,tag[p] += val
)。然后直接返回。 - 否则,在递归到子节点之前,先要下放(Push Down)当前节点的懒惰标记。
- 当修改区间完全覆盖当前节点区间时,更新当前节点的值(例如,区间和
-
下放标记 (Push Down):
- 检查当前节点
p
是否有懒惰标记。 - 如果有,将这个标记应用到它的左右两个子节点上。
- 更新左子节点的值和标记:
tree[2p] += ...
,tag[2p] += ...
- 更新右子节点的值和标记:
tree[2p+1] += ...
,tag[2p+1] += ...
- 更新左子节点的值和标记:
- 清除当前节点
p
的懒惰标记。
- 检查当前节点
-
查询 (Range Query):
- 在递归查询的过程中,每次进入一个节点的子节点前,都必须先执行下放标记的操作,以确保子节点的信息是正确的。
通过懒惰标记,区间修改的时间复杂度也优化到了 \(O(\log N)\)。
2.4.5 C++ 代码模板
下面是一个支持区间加法和区间求和的线段树模板。
#include <iostream>
#include <vector>using namespace std;const int MAXN = 100005;long long a[MAXN]; // 原始数组,下标从1开始
long long tree[MAXN * 4]; // 线段树数组
long long tag[MAXN * 4]; // 懒惰标记数组
int n; // 元素个数// 用子节点信息更新父节点
void push_up(int p) {tree[p] = tree[p * 2] + tree[p * 2 + 1];
}// 下放懒惰标记
void push_down(int p, int l, int r) {if (tag[p] != 0) {int mid = (l + r) / 2;// 更新左子节点的值和标记tree[p * 2] += tag[p] * (mid - l + 1);tag[p * 2] += tag[p];// 更新右子节点的值和标记tree[p * 2 + 1] += tag[p] * (r - (mid + 1) + 1);tag[p * 2 + 1] += tag[p];// 清除当前节点的标记tag[p] = 0;}
}// 建树
void build(int p, int l, int r) {if (l == r) {tree[p] = a[l];return;}int mid = (l + r) / 2;build(p * 2, l, mid);build(p * 2 + 1, mid + 1, r);push_up(p);
}// 区间修改:将区间 [update_l, update_r] 内的数都加上 val
void update(int p, int l, int r, int update_l, int update_r, int val) {if (update_l <= l && r <= update_r) { // 完全覆盖tree[p] += (long long)(r - l + 1) * val;tag[p] += val;return;}push_down(p, l, r); // 准备访问子节点,先下放标记int mid = (l + r) / 2;if (update_l <= mid) {update(p * 2, l, mid, update_l, update_r, val);}if (update_r > mid) {update(p * 2 + 1, mid + 1, r, update_l, update_r, val);}push_up(p); // 用更新后的子节点信息更新自己
}// 区间查询:查询区间 [query_l, query_r] 的和
long long query(int p, int l, int r, int query_l, int query_r) {if (query_l <= l && r <= query_r) { // 完全覆盖return tree[p];}push_down(p, l, r); // 准备访问子节点,先下放标记int mid = (l + r) / 2;long long sum = 0;if (query_l <= mid) {sum += query(p * 2, l, mid, query_l, query_r);}if (query_r > mid) {sum += query(p * 2 + 1, mid + 1, r, query_l, query_r);}return sum;
}int main() {// 使用示例int m; // 操作次数cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> a[i];}build(1, 1, n);for (int i = 0; i < m; ++i) {int type;cin >> type;if (type == 1) { // 区间修改int l, r, val;cin >> l >> r >> val;update(1, 1, n, l, r, val);} else { // 区间查询int l, r;cin >> l >> r;cout << query(1, 1, n, l, r) << endl;}}return 0;
}
2.4.6 例题与解析
【例题】洛谷 P3372 【模板】线段树 1
题目描述:已知一个数列,你需要进行下面两种操作:
- 将某区间
[x, y]
每个数加上k
。 - 求出某区间
[x, y]
的和。
输入格式:第一行包含两个整数 \(N, M\),分别表示数列的长度和操作的个数。第二行包含 \(N\) 个整数,表示初始数列。接下来 \(M\) 行,每行包含三或四个整数,表示一个操作。
解题思路:
这道题是线段树带有懒惰标记的模板题。
- 我们需要维护一个区间和。
- 操作1是区间修改(区间加法)。
- 操作2是区间查询(区间求和)。
可以直接使用上一节提供的C++代码模板来解决。将输入数据读入后,先调用build
函数建树,然后根据操作类型调用update
或query
函数即可。
2.5 【6】字典树(Trie)
2.5.1 什么是字典树?
字典树,又称 Trie 树、前缀树(Prefix Tree),是一种专门用于高效地存储和检索字符串集合的数据结构。它的核心思想是利用字符串的公共前缀来节省存储空间和查询时间。
想象一下查英文字典的过程:要找单词 apple
,你会先翻到 'a' 开头的部分,再找 'ap',然后 'app',以此类推。字典树的组织方式与此非常相似。
Trie 树可以解决以下问题:
- 快速判断一个单词是否出现在一个单词集合中。
- 快速查找一个集合中有多少个单词以某个字符串为前缀。
- ……以及很多其它与字符串前缀相关的问题。
2.5.2 字典树的结构
Trie 树是一棵多叉树,它的结构特点如下:
- 根节点不代表任何字符。
- 从根节点到任意一个节点的路径上,经过的字符连接起来,就是该节点所代表的字符串(前缀)。
- 每个节点的所有子节点所代表的字符都不同。
- 为了区分一个前缀是否也是一个完整的单词,节点上通常会有一个标记(例如
is_end
)。
例如,我们有单词集合 {"cat", "car", "catch", "dog", "do"}
,构建出的 Trie 树如下:
(root)/ \c d| |a o/ \ |t* r* g*|c|h*
(带 *
号的节点表示一个单词的结尾)
从图中可以看出:
- 路径
root -> c -> a -> t
对应字符串 "cat"。节点t
被标记为单词结尾。 "ca"
是"cat"
,"car"
,"catch"
的公共前缀,所以它们共享从root
到a
的路径。
如何存储 Trie 树?
最常见的方式是用一个二维数组 trie[N][C]
,其中 N
是可能的最大节点数,C
是字符集的大小(例如,小写英文字母是 26)。
trie[p][ch]
存储的是节点p
通过字符ch
连接到的子节点的编号。如果值为 0,表示不存在这个子节点。- 需要一个计数器
idx
来分配新的节点编号,idx
从 1 开始。 - 另外还需要一个数组,如
end_count[N]
,来记录以节点p
结尾的单词有多少个。
2.5.3 字典树的核心操作
1. 插入 (Insert)
将一个字符串插入到 Trie 树中,过程如下:
- 从根节点开始,当前节点指针
p = root
(通常root=0
或1
)。 - 遍历字符串的每一个字符
ch
。 - 检查当前节点
p
是否有指向ch
的子节点,即trie[p][ch]
是否存在。- 如果不存在,就创建一个新的节点
newNode
,并令trie[p][ch] = newNode
。 - 然后,将指针移动到这个子节点:
p = trie[p][ch]
。
- 如果不存在,就创建一个新的节点
- 字符串遍历结束后,在最后的节点
p
上打上单词结尾标记,例如end_count[p]++
。
【伪代码】
INSERT(str)p = ROOTFOR ch IN str DOIF trie[p][ch] IS NULL THENnewNode = GET_NEW_NODE()trie[p][ch] = newNodeEND IFp = trie[p][ch]END FORend_count[p] = end_count[p] + 1
2. 查询 (Search)
查询一个字符串是否在集合中,过程与插入类似:
- 从根节点开始,
p = root
。 - 遍历查询字符串的每一个字符
ch
。 - 检查
trie[p][ch]
是否存在。- 如果不存在,说明这个单词肯定不在集合中,直接返回
false
。 - 如果存在,移动到子节点
p = trie[p][ch]
。
- 如果不存在,说明这个单词肯定不在集合中,直接返回
- 字符串遍历结束后,检查当前节点
p
的单词结尾标记end_count[p]
是否大于 0。如果是,则单词存在,返回true
;否则,它只是一个前缀,返回false
。
【伪代码】
SEARCH(str)p = ROOTFOR ch IN str DOIF trie[p][ch] IS NULL THENRETURN falseEND IFp = trie[p][ch]END FORRETURN (end_count[p] > 0)
Trie 树的插入和查询操作,时间复杂度都只与字符串的长度 \(L\) 有关,为 \(O(L)\),与集合中单词的总数无关,效率非常高。
2.5.4 C++ 代码模板
下面是一个用于存储和查询小写英文字母字符串的 Trie 树模板。
#include <iostream>
#include <string>
#include <vector>using namespace std;const int MAX_NODES = 100005; // 估算最大节点数(字符串总长)
const int CHARSET_SIZE = 26; // 字符集大小int trie[MAX_NODES][CHARSET_SIZE];
int end_count[MAX_NODES];
int node_count; // 已使用的节点数量// 初始化Trie树
void init() {// C++中全局数组默认初始化为0,这里可以省略memset// memset(trie, 0, sizeof(trie));// memset(end_count, 0, sizeof(end_count));node_count = 1; // 0号节点作为根节点
}// 插入字符串
void insert(const string& s) {int p = 0; // 从根节点开始for (char ch : s) {int c = ch - 'a'; // 将字符映射到 0-25if (trie[p][c] == 0) {trie[p][c] = node_count++;}p = trie[p][c];}end_count[p]++;
}// 查询字符串
bool search(const string& s) {int p = 0;for (char ch : s) {int c = ch - 'a';if (trie[p][c] == 0) {return false;}p = trie[p][c];}return end_count[p] > 0;
}int main() {init();int n;cin >> n;for (int i = 0; i < n; ++i) {string s;cin >> s;insert(s);}int m;cin >> m;for (int i = 0; i < m; ++i) {string s;cin >> s;if (search(s)) {cout << "YES" << endl;} else {cout << "NO" << endl;}}return 0;
}
2.5.5 例题与解析
【例题】洛谷 P2580 于是他错误的点名开始了
题目描述:给定一个名字列表,然后进行若干次点名。对于每次点名:
- 如果名字在列表中,且是第一次被点到,输出 "OK"。
- 如果名字在列表中,但之前已经被点到过,输出 "REPEAT"。
- 如果名字不在列表中,输出 "WRONG"。
解题思路:
这道题是 Trie 树的典型应用。我们可以用 end_count
数组来记录状态,而不仅仅是单词的结尾。
end_count[p] = 0
:表示从根到p
的路径不是一个完整的名字。end_count[p] = 1
:表示这是一个合法的名字,且从未被点到过。end_count[p] = 2
:表示这是一个合法的名字,且已经被点到过。
具体步骤:
- 建树:读入所有名字,插入到 Trie 树中。对于插入的每个名字,将其最终节点的
end_count
值设为 1。 - 查询:对于每次点名,在 Trie 树中查询这个名字。
- 在查询路径中,如果中途发现没有路可走(
trie[p][c] == 0
),说明名字不存在,输出 "WRONG"。 - 如果路径走完了,到达节点
p
:- 检查
end_count[p]
的值。如果为 0,说明这个名字只是某个更长名字的前缀,而不是一个合法的名字,输出 "WRONG"。 - 如果为 1,说明是第一次点到,输出 "OK",并把
end_count[p]
修改为 2。 - 如果为 2,说明是重复点名,输出 "REPEAT"。
- 检查
- 在查询路径中,如果中途发现没有路可走(
这个方法完美地利用了 Trie 树的节点信息来存储和更新状态,高效地解决了问题。
2.6 【7】笛卡尔树
2.6.1 什么是笛卡尔树?
笛卡尔树(Cartesian Tree)是一种特殊的二叉树,它同时满足两种性质:堆的性质和二叉搜索树的性质。但这里的“二叉搜索树”性质是针对数组下标而言的。
给定一个序列(通常要求元素值互不相同),其笛卡尔树定义如下:
- 树中的每个节点包含一个
(key, value)
对,通常key
是元素在原序列中的下标,value
是元素的值。 - 堆性质 (Heap Property):如果以
value
为标准,它是一个小根堆(Min-Heap)。也就是说,任意一个节点的value
都小于或等于它子节点的value
。 - 二叉搜索树性质 (BST Property):如果以
key
(即下标) 为标准,它是一棵二叉搜索树。也就是说,对于任意节点,其左子树中所有节点的key
都小于它自身的key
,其右子树中所有节点的key
都大于它自身的key
。
综合起来:
- 树的根节点是原序列中
value
最小的那个元素。 - 根节点的左子树由原序列中在该最小元素左边的所有元素构成。
- 根节点的右子树由原序列中在该最小元素右边的所有元素构成。
- 左右子树本身也都是笛卡尔树,这个定义是递归的。
例如,对于序列 A = {3, 1, 4, 5, 9, 2, 6}
(下标从1到7),其笛卡尔树如下:
- 序列中最小值是 1 (下标2)。所以 (2, 1) 是根。
- 在 1 左边的元素是 {3} (下标1),构成左子树。
- 在 1 右边的元素是 {4, 5, 9, 2, 6} (下标3-7),构成右子树。
- 对于右子树 {4, 5, 9, 2, 6},最小值是 2 (下标6)。所以 (6, 2) 是 (2, 1) 的右孩子。
- ... 以此类推,最终构建的树如下:
(2, 1)/ \(1, 3) (6, 2)/ \(4, 4) (7, 6)/ \(3, 5) (5, 9)
重要性质:
- 一个序列的笛卡尔树,在元素值互不相同的情况下,是唯一的。
- 树的中序遍历结果,恰好是原序列的下标序列。例如上图的中序遍历结果是 {1, 2, 3, 4, 5, 6, 7}。
2.6.2 笛卡尔树的构造
-
朴素构造法 ( \(O(N^2)\) ):
直接根据定义递归构造。每次在当前区间[L, R]
内找到最小值的下标min_idx
,创建节点,然后递归构造[L, min_idx-1]
作为左子树,[min_idx+1, R]
作为右子树。每次查找最小值需要 \(O(N)\),效率很低。 -
高效构造法 ( \(O(N)\) ):
我们可以使用一个单调栈来在线性时间内完成建树。
思路是:按顺序(从左到右)遍历原序列的每个元素,并动态地维护树的“右链”(从根节点一直往右子节点走形成的路径)。这个右链上的节点,它们的value
是单调递增的。算法流程:
- 维护一个单调栈,栈中存放已构建好的树的节点,且从栈底到栈顶,节点的
value
严格递增。 - 依次遍历序列中的每个元素
A[i]
,为它创建一个新节点curr
。 - 核心步骤:比较
curr
和栈顶元素stk.top()
的value
。- 如果栈顶元素的
value
大于curr
的value
,说明栈顶元素不再能维持右链的单调性。它应该成为curr
的左孩子(因为它下标更小,值更大)。于是,不断地将栈顶元素弹出,并让最后一个弹出的元素成为curr
的左孩子。 - 当循环结束时(栈为空或栈顶元素
value
小于curr
的value
),此时的curr
节点找到了它在树中的位置。
- 如果栈顶元素的
- 如果此时栈不为空,那么栈顶元素
stk.top()
就是curr
的父节点。curr
应该成为stk.top()
的右孩子(因为curr
的下标更大)。 - 将
curr
压入栈中。
用一个例子来模拟
A = {3, 1, 4, 5, 9, 2, 6}
:- i=1, val=3:栈空,节点1入栈。
stk: {1}
- i=2, val=1:
val(1)=3 > val(2)=1
。弹出1。节点2的左孩子是1。栈空。节点2入栈。stk: {2}
- i=3, val=4:
val(2)=1 < val(4)=4
。节点4成为节点2的右孩子。节点4入栈。stk: {2, 4}
- i=4, val=5:
val(4)=4 < val(5)=5
。节点5成为节点4的右孩子。节点5入栈。stk: {2, 4, 5}
- i=5, val=9:
val(5)=5 < val(9)=9
。节点9成为节点5的右孩子。节点9入栈。stk: {2, 4, 5, 9}
- i=6, val=2:
val(9)=9 > val(2)=2
,弹9。val(5)=5 > val(2)=2
,弹5。val(4)=4 > val(2)=2
,弹4。最后弹出的4成为节点2的左孩子。此时栈顶是2,val(2)=1 < val(2)=2
。节点2成为节点6的右孩子。节点6入栈。stk: {2, 6}
- i=7, val=6:
val(6)=2 < val(6)=6
。节点6成为节点7的右孩子。节点7入栈。stk: {2, 6, 7}
最终,栈中从底到顶为
2, 6, 7
,这就是树的右链。整个树的根是栈中所有元素最终的父节点,也就是 2。 - 维护一个单调栈,栈中存放已构建好的树的节点,且从栈底到栈顶,节点的
2.6.3 C++ 代码模板
#include <iostream>
#include <vector>
#include <stack>using namespace std;const int MAXN = 1000005;struct Node {int val;int l_child, r_child;
};Node tree[MAXN];
int val[MAXN];
int l_child[MAXN], r_child[MAXN];
int n;int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);cin >> n;for (int i = 1; i <= n; ++i) {cin >> val[i];}stack<int> s;for (int i = 1; i <= n; ++i) {int last_pop = 0;// 当栈不空且栈顶元素值大于当前元素值while (!s.empty() && val[s.top()] > val[i]) {last_pop = s.top();s.pop();}if (!s.empty()) {// 栈顶是父节点,当前节点是其右孩子r_child[s.top()] = i;}// 最后一个弹出的节点是当前节点的左孩子l_child[i] = last_pop;s.push(i);}// 找到根节点(没有父节点的节点)// 在这个建树方法中,根是整个序列中最小值的下标// 或者可以通过一个 parent 数组来找,谁的 parent 是 0 谁就是根// P5854 模板题的输出要求比较特殊,需要计算哈希值long long ans1 = 0, ans2 = 0;for(int i = 1; i <= n; ++i) {ans1 ^= (long long)i * (l_child[i] + 1);ans2 ^= (long long)i * (r_child[i] + 1);}cout << ans1 << " " << ans2 << endl;return 0;
}
2.6.4 例题与解析
【例题】洛谷 P5854 【模板】笛卡尔树
题目描述:给定一个 \(1 \dots N\) 的排列,构建其笛卡尔树。你需要分别输出每个节点的左儿子和右儿子。
解题思路:
这道题就是笛卡尔树的模板题。题目给定的是一个排列,保证了元素值(也就是权值)互不相同。我们只需要按照 \(O(N)\) 的单调栈方法构建笛卡尔树即可。
代码实现细节:
- 用两个数组
l_child[]
和r_child[]
来存储每个节点的左右儿子编号。 - 遍历 \(1 \dots N\),对于每个节点
i
:- 维护一个单调栈。
while
循环找到它正确的左孩子(last_pop
)。- 栈中剩下的栈顶元素是它的父节点,所以它自己是父节点的右孩子。
- 将自己入栈。
- 遍历结束后,
l_child
和r_child
数组就存储了整棵树的结构。 - 题目的输出要求是对左右孩子编号进行异或加密,只需要按照公式计算即可。上面的代码模板就是针对这道题的解法。
笛卡尔树的应用:
笛卡尔树最强大的应用之一是解决区间最值查询 (RMQ, Range Minimum/Maximum Query) 问题。
序列中任意一个区间 [L, R]
的最小值,就是原序列中下标在 [L, R]
内的这些节点,在笛卡尔树中的最近公共祖先 (LCA, Lowest Common Ancestor)。
因此,RMQ 问题可以转化为树上的 LCA 问题,而 LCA 问题有非常成熟的 \(O(N \log N)\) 预处理、\(O(1)\) 查询的算法(例如基于ST表的算法)。这使得笛卡尔树成为解决某些复杂问题的基础。
2.7 【8】平衡树:AVL、Treap、Splay
在之前的学习中,我们已经掌握了二叉搜索树(Binary Search Tree, BST)。我们知道,二叉搜索树在理想情况下,也就是“形态匀称”的情况下,其查找、插入和删除操作的时间复杂度都是 \(O(\log n)\),效率非常高。
但是,二叉搜索树有一个致命的弱点:它的形态完全依赖于插入元素的顺序。如果插入的元素是随机的,那么它有很大概率会是一棵比较“平衡”的树。但如果插入的元素是提前排好序的(例如,依次插入 1, 2, 3, 4, 5),那么这棵二叉搜索树就会退化成一条链。
在这种情况下,树的高度为 \(n\),所有的操作时间复杂度都会退化到 \(O(n)\),这与暴力枚举的效率无异,失去了数据结构的优势。
为了解决这个问题,科学家们发明了一系列能够在进行插入和删除操作时,通过一些巧妙的变换来自动维持树的形态平衡的数据结构,它们被统称为平衡二叉搜索树(Self-Balancing Binary Search Tree),简称平衡树。
平衡树的核心思想是:在对树进行修改,可能导致其不平衡时,通过一种叫做旋转(Rotation)的操作来局部调整树的结构,使其重新恢复平衡,同时保持二叉搜索树的性质不变。这个过程就像一个杂技演员,在不断有人跳上他叠的椅子时,他会不断调整自己的姿势来保持整体的平衡。
本章,我们将学习三种最经典、最常用的平衡树:AVL 树、Treap 和 Splay 树。它们用不同的策略来维护平衡,各有优劣。
2.7.1 AVL 树
AVL 树是最早被发明的自平衡二叉搜索树。它的名字来源于其两位发明者 G. M. Adelson-Velsky 和 E. M. Landis 的姓氏首字母。
2.7.1.1 AVL 树的平衡策略
AVL 树的平衡策略非常严格甚至有些“暴力”:它要求树中任何一个节点的左子树和右子树的高度差的绝对值不能超过 1。
定义:平衡因子(Balance Factor)
某个节点的平衡因子被定义为:它的右子树的高度减去它的左子树的高度。
\(BalanceFactor(node) = Height(node \to right) - Height(node \to left)\)
那么,AVL 树的性质可以描述为:对于树中的任意节点
node
,其平衡因子的取值只能是 -1、0 或 1。
- 当平衡因子为 -1 时,说明左子树比右子树高 1。
- 当平衡因子为 0 时,说明左右子树等高。
- 当平衡因子为 1 时,说明右子树比左子树高 1。
如果一个节点的平衡因子的绝对值变成了 2,我们就称这个节点失衡(Unbalanced),并且需要通过旋转操作来修复它。
2.7.1.2 核心操作:旋转
旋转是所有平衡树调整形态的原子操作。它可以在不破坏二叉搜索树性质的前提下,改变节点的父子关系,从而降低树的高度。旋转分为两种:左旋(Left Rotation) 和 右旋(Right Rotation)。
1. 右旋 (Right Rotation)
假设节点 p
是失衡节点,它的左孩子是 c
。对 p
进行右旋,意味着将 c
“提”上来成为新的根节点,而 p
则“降”下去成为 c
的右孩子。
-
操作过程(以
p
为轴心右旋):p
的左孩子c
成为新的根。p
成为c
的右孩子。c
原来的右子树,现在成为p
的左子树。
-
性质观察:
- 旋转前,中序遍历的结果是
T1 -> c -> T2 -> p -> T3
。 - 旋转后,中序遍历的结果是
T1 -> c -> T2 -> p -> T3
。 - 中序遍历序列不变,所以它仍然是一棵二叉搜索树!但是树的结构改变了,高度也可能随之改变。
- 旋转前,中序遍历的结果是
2. 左旋 (Left Rotation)
左旋是右旋的镜像操作。假设节点 p
是失衡节点,它的右孩子是 c
。对 p
进行左旋,意味着将 c
“提”上来,p
“降”下去成为 c
的左孩子。
- 操作过程(以
p
为轴心左旋):p
的右孩子c
成为新的根。p
成为c
的左孩子。c
原来的左子树(上图中的T2
)现在成为p
的右子树。
2.7.1.3 AVL 树的四种失衡情况与调整
当我们在 AVL 树中插入一个新节点后,可能会导致从插入点到根节点的路径上某些祖先节点的平衡因子绝对值变为 2。我们只需要找到离插入点最近的那个失衡节点,对它进行调整即可。失衡的情况可以分为四种:
1. LL 型(左-左)
- 成因:在新节点插入到失衡节点
p
的左子树c
的左子树中,导致p
失衡。 - 调整:对失衡节点
p
进行一次右旋。
2. RR 型(右-右)
- 成因:在新节点插入到失衡节点
p
的右子树c
的右子树中,导致p
失衡。 - 调整:对失衡节点
p
进行一次左旋。
3. LR 型(左-右)
- 成因:在新节点插入到失衡节点
p
的左子树c
的右子树中,导致p
失衡。 - 调整:这种稍微复杂,需要两次旋转。
- 先对
p
的左孩子c
进行一次左旋。(把它变成 LL 型) - 再对
p
本身进行一次右旋。
- 先对
4. RL 型(右-左)
- 成因:在新节点插入到失衡节点
p
的右子树c
的左子树中,导致p
失衡。 - 调整:与 LR 型对称。
- 先对
p
的右孩子c
进行一次右旋。(把它变成 RR 型) - 再对
p
本身进行一次左旋。
- 先对
2.7.1.4 AVL 树的伪代码与实现
节点结构
struct Node {int val; // 节点的值int height; // 以当前节点为根的子树的高度Node *left, *right; // 左右孩子指针
};
插入操作伪代码
function insert(node, value):if node is null:return create_new_node(value)if value < node.val:node.left = insert(node.left, value)else if value > node.val:node.right = insert(node.right, value)else: // 值已存在,不插入return node// 1. 更新高度update_height(node)// 2. 获取平衡因子,检查是否失衡balance = get_balance_factor(node)// 3. 如果失衡,进行旋转调整 (四种情况)// LL Caseif balance < -1 and value < node.left.val:return right_rotate(node)// RR Caseif balance > 1 and value > node.right.val:return left_rotate(node)// LR Caseif balance < -1 and value > node.left.val:node.left = left_rotate(node.left)return right_rotate(node)// RL Caseif balance > 1 and value < node.right.val:node.right = right_rotate(node.right)return left_rotate(node)// 4. 如果未失衡,直接返回当前节点return node
2.7.1.5 优缺点分析
- 优点:由于其严格的平衡限制,AVL 树的高度被严格控制在 \(O(\log n)\),因此其查找性能非常稳定且高效。
- 缺点:为了维持这种严格的平衡,插入和删除操作可能需要进行多次旋转(尽管最多两次),导致这些操作的常数因子较大,实现也相对复杂。
在实际应用和竞赛中,由于其实现的复杂性,AVL 树并不如接下来要讲的 Treap 和 Splay 常用。但理解它的平衡思想是学习其他平衡树的基础。
2.7.2 Treap
Treap 是一种非常有趣的平衡树,它的名字是 Tree (树) 和 Heap (堆) 的合成词。它巧妙地利用了“随机化”来大概率地维持树的平衡,代码实现比 AVL 树简单得多。
2.7.2.1 Treap 的双重性质
Treap 的每个节点除了存储一个键值 val
之外,还额外存储一个随机生成的优先级 priority
。Treap 这棵树需要同时满足两个性质:
- 关于键值
val
,它是一棵二叉搜索树(BST):- 对于任意节点,其左子树中所有节点的
val
都小于该节点的val
。 - 其右子树中所有节点的
val
都大于该节点的val
。
- 对于任意节点,其左子树中所有节点的
- 关于优先级
priority
,它是一个大根堆(Max-Heap):- 对于任意节点,其
priority
都大于等于它左右孩子的priority
。 - 即父节点的优先级总是最高的。
- 对于任意节点,其
一个重要的结论:当一棵树上所有节点的键值 val
和优先级 priority
都确定后,如果这棵树同时满足 BST 和堆的性质,那么它的形态是唯一确定的。
正是因为优先级是随机赋予的,我们就可以认为这棵树的结构是“随机”的,从而在概率上期望树的高度为 \(O(\log n)\),避免了退化成链的情况。
2.7.2.2 Treap 的核心操作
Treap 维持平衡的方式完全依赖于旋转操作,但其触发旋转的条件比 AVL 树简单得多:当且仅当一个节点的优先级小于其子节点的优先级时(即违反了堆性质),才需要进行旋转。
1. 插入 (Insert)
- 第一步:忽略优先级,像普通二叉搜索树一样,根据键值
val
找到合适的位置,插入一个新节点。为这个新节点随机赋予一个优先级priority
。 - 第二步:检查新插入的节点是否满足堆性质。如果它的优先级比其父节点大,就违反了堆性质。此时,通过旋转来修复它。
- 如果该节点是其父节点的左孩子,就对父节点进行右旋。
- 如果该节点是其父节点的右孩子,就对父节点进行左旋。
- 这个过程就像在大根堆中插入元素后的“上浮”操作,不断旋转,直到该节点的父节点优先级比它大,或者它自己成为根节点为止。
2. 删除 (Delete)
删除一个节点比插入稍微麻烦一点,因为我们不能直接删除一个内部节点,那样会破坏树的结构。
- 第一步:在树中找到要删除的节点。
- 第二步:通过旋转,将这个要删除的节点“下沉”到叶子节点的位置。
- 比较其左右孩子的优先级。选择优先级较大的那个孩子进行旋转。
- 如果左孩子优先级大,就对当前节点进行右旋(把它作为右孩子换下去)。
- 如果右孩子优先级大,就对当前节点进行左旋(把它作为左孩子换下去)。
- 重复这个过程,直到要删除的节点成为一个叶子节点。
- 第三步:当要删除的节点成为叶子节点后,直接删除它。
2.7.2.3 Treap 的 C++ 实现模板
Treap 的实现通常采用指针方式,并且经常会把左右孩子 lson
, rson
写成一个数组 ch[2]
,这样在旋转时代码可以写得更简洁。
#include <iostream>
#include <cstdlib> // For rand()
#include <ctime> // For srand()using namespace std;// 建议在程序开始时调用 srand(time(0)) 来初始化随机数种子struct Node {int val; // BST 的键值int priority; // 堆的优先级int size; // 子树大小(用于查询排名等)Node *ch[2]; // ch[0] 是左孩子, ch[1] 是右孩子Node(int v) {val = v;priority = rand();size = 1;ch[0] = ch[1] = nullptr;}
};// 更新节点 size 信息
void pushup(Node* p) {p->size = 1;if (p->ch[0]) p->size += p->ch[0]->size;if (p->ch[1]) p->size += p->ch[1]->size;
}// 旋转操作 (d=0 右旋, d=1 左旋)
// d=0: 将 p 的左孩子(ch[0]) 旋上来
// d=1: 将 p 的右孩子(ch[1]) 旋上来
void rotate(Node* &p, int d) {Node* k = p->ch[d^1]; // d=0, k=p->ch[1]; d=1, k=p->ch[0]p->ch[d^1] = k->ch[d];k->ch[d] = p;pushup(p);pushup(k);p = k;
}// 插入操作
void insert(Node* &p, int val) {if (!p) {p = new Node(val);return;}if (val == p->val) return; // 假设不插入重复值int d = (val > p->val); // d=0 插入左子树, d=1 插入右子树insert(p->ch[d], val);// 维护堆性质if (p->ch[d]->priority > p->priority) {rotate(p, d^1); // 如果右孩子(d=1)优先级大,需要左旋(d^1=0)// 如果左孩子(d=0)优先级大,需要右旋(d^1=1)// 这里有个小技巧,可以思考一下}pushup(p);
}// 删除操作
void remove(Node* &p, int val) {if (!p) return;if (val < p->val) {remove(p->ch[0], val);} else if (val > p->val) {remove(p->ch[1], val);} else { // 找到了要删除的节点 pif (!p->ch[0] && !p->ch[1]) { // 叶子节点delete p;p = nullptr;} else if (!p->ch[0]) { // 只有右孩子Node* k = p;p = p->ch[1];delete k;} else if (!p->ch[1]) { // 只有左孩子Node* k = p;p = p->ch[0];delete k;} else { // 有两个孩子int d = (p->ch[0]->priority < p->ch[1]->priority); // 哪个孩子优先级大,就把它旋上来rotate(p, d);remove(p->ch[d], val); // 继续在旋转下去的子树中删除}}if (p) pushup(p);
}
注意:rotate(p, d)
中 d
的含义是“哪个方向的孩子不动”。例如 d=0
时,p
的左孩子 p->ch[0]
和右子树 p->ch[1]->ch[1]
保持父子关系不变,所以是右旋。思考一下 d
和 d^1
的对应关系,这是 Treap 代码简洁的关键。
2.7.2.4 例题讲解:【洛谷 P3369】【模板】普通平衡树
这道题要求我们实现一个数据结构,支持插入、删除、查询排名、查询数值、找前驱、找后继等操作。这是平衡树的经典模板题,用 Treap 来实现非常合适。
除了上面讲的插入和删除,我们还需要实现其他几个查询功能。这些功能都利用了二叉搜索树的性质以及我们维护的 size
信息。
- 查询 x 的排名:从根节点开始,如果 x 小于当前节点值,就往左走;如果 x 大于当前节点值,答案加上左子树的
size
和 1(当前节点),然后往右走;如果相等,答案就加上左子树的size
再加 1。 - 查询排名为 k 的数:从根节点开始,比较 k 和左子树的
size
。如果 k 小于等于左子树size
,就往左走;如果 k 大于左子树size
+ 1,就从 k 中减去左子树size
+ 1,然后往右走;否则,当前节点就是答案。 - 找前驱:比 x 小的数中最大的那个。在树中查找 x,沿途经过的节点值如果小于 x,就可能是答案,记录下来。最后一次记录的值就是前驱。
- 找后继:比 x 大的数中最小的那个。与找前驱类似。
完整的题解代码较长,但核心就是上面 Treap 模板的扩展。Treap 代码短、思路清晰,是竞赛中性价比非常高的选择。
2.7.3 Splay 树
Splay 树,又称伸展树,是另一种高效的平衡二叉搜索树。它与 AVL 和 Treap 的思想完全不同。它不通过特定的“平衡因子”或“优先级”来维持平衡,而是遵循一个非常朴素的原则:每次访问一个节点后,都通过一系列旋转将这个节点移动到树的根部。
这个核心操作被称为伸展(Splay)。
2.7.3.1 Splay 的神奇之处:局部性原理
Splay 树的设计基于一个经验性的假设,叫做局部性原理(Locality of Reference)。这个原理指的是,在很多应用场景中,刚刚被访问过的数据,在接下来有很大概率会再次被访问。
Splay 树将最近访问的节点移动到根,就是为了让下一次对它的访问变得极快(\(O(1)\))。虽然单次操作的最坏情况复杂度可能是 \(O(n)\)(例如,访问一个深度最深的节点,然后把它旋转到根),但 Splay 树有一个非常强大的性质:均摊复杂度(Amortized Complexity)。
均摊复杂度:简单来说,虽然某一次操作可能很慢,但它会为后续的操作“铺路”,使得后续操作变快。将一系列操作的总时间除以操作次数,得到的平均时间复杂度是稳定的。Splay 树的所有操作的均摊时间复杂度都是 \(O(\log n)\)。对于初学者,我们不需要深入证明,只需记住这个结论。
2.7.3.2 核心操作:伸展 (Splay)
伸展操作就是将指定节点 x
旋转到根。这个过程不是简单地一路单旋上去,否则仍然可能形成链。Splay 的精髓在于它的双层旋转。假设要伸展的节点是 x
,它的父亲是 p
,祖父是 g
。根据 x, p, g
的相对位置,分为三种情况:
1. Zig (单旋)
- 情况:
p
就是根节点。 - 操作:如果
x
是p
的左孩子,就右旋p
;如果x
是p
的右孩子,就左旋p
。
2. Zig-Zig (一字型)
- 情况:
x
和p
都是左孩子(或都是右孩子)。 - 操作:先旋转父亲
p
,再旋转自己x
。例如,g-p-x
是一条左斜链,那么先右旋g
,再右旋p
。
3. Zig-Zag (之字型)
- 情况:
x
是右孩子而p
是左孩子(或反之)。 - 操作:连续旋转自己
x
两次。例如,x
是p
的右孩子,p
是g
的左孩子。那么先对p
左旋,再对g
右旋。
Splay 操作流程:只要 x
还不是根节点,就反复执行上述三种情况之一,直到 x
成为根。
2.7.3.3 Splay 树的基本操作
Splay 树的所有操作都围绕 splay
函数展开。
-
插入 (Insert):
- 像普通 BST 一样插入新节点。
- 对新插入的节点执行
splay
操作,将其移动到根。
-
查找 (Find):
- 像普通 BST 一样查找目标节点。
- 如果找到了,对该节点执行
splay
操作。如果没找到,对最后访问到的那个节点执行splay
操作。
-
删除 (Delete):
- 首先查找要删除的值,并将其
splay
到根。假设现在的根是x
。 - 此时
x
的左子树中的所有值都比x
小,右子树所有值都比x
大。 - 将
x
的左子树和右子树断开。 - 在
x
的左子树中,找到值最大的那个节点(也就是左子树的根一直往右走到底),我们称之为max_left
。 - 对
max_left
执行splay
操作,使其成为左子树的新根。 - 此时,
max_left
一定没有右孩子。将x
原来的右子树,连接为max_left
的右孩子。 - 最后,删除节点
x
,新的树根就是max_left
。
- 首先查找要删除的值,并将其
2.7.3.4 Splay 树的 C++ 实现模板
Splay 树的实现通常不用递归,而是用 while
循环自底向上进行旋转,这样更高效。
#include <iostream>
#include <algorithm>using namespace std;struct Node {int val;int size;Node *ch[2]; // ch[0] left, ch[1] rightNode *fa; // parent pointerNode(int v, Node* f) {val = v;size = 1;ch[0] = ch[1] = nullptr;fa = f;}
};Node* root;void pushup(Node* p) {p->size = 1;if (p->ch[0]) p->size += p->ch[0]->size;if (p->ch[1]) p->size += p->ch[1]->size;
}// d=0: 左孩子, d=1: 右孩子
// get(x) 判断 x 是其父节点的哪个孩子
int get(Node* p) {return p == p->fa->ch[1];
}void rotate(Node* p) {Node *f = p->fa, *gf = f->fa;int d = get(p);// 连接 gf 和 pif (gf) gf->ch[get(f)] = p;p->fa = gf;// 连接 f 和 p 的子树f->ch[d] = p->ch[d^1];if (p->ch[d^1]) p->ch[d^1]->fa = f;// 连接 p 和 fp->ch[d^1] = f;f->fa = p;pushup(f);pushup(p);
}void splay(Node* p, Node* goal = nullptr) {while (p->fa != goal) {Node *f = p->fa, *gf = f->fa;if (gf != goal) { // 如果有祖父节点,判断 zig-zig or zig-zagif (get(p) == get(f)) { // zig-zigrotate(f);} else { // zig-zagrotate(p);}}rotate(p);}if (goal == nullptr) { // 如果目标是根,更新 root 指针root = p;}
}
注意:这里的 Splay 代码是一个更常见的竞赛模板写法。splay(p, goal)
的意思是将 p
旋转到 goal
的下方。当 goal
为 nullptr
时,就是将 p
旋转到根。这种写法在处理区间操作时非常有用。
2.7.3.5 Splay 的应用
Splay 树非常灵活,除了能完成普通平衡树的所有操作外,它的 splay
操作能方便地将任意节点置于根,这使得它在处理需要区间合并、分裂等操作的场景时特别强大。例如,文艺平衡树(洛谷 P3391)就是 Splay 的一个经典应用,通过 Splay 维护一个序列,可以实现区间翻转等复杂操作。
2.7.3.6 总结与对比
特性 | AVL 树 | Treap | Splay 树 |
---|---|---|---|
平衡策略 | 严格高度限制(平衡因子) | 随机优先级(堆性质) | 访问后伸展到根 |
时间复杂度 | 所有操作严格 \(O(\log n)\) | 所有操作期望 \(O(\log n)\) | 所有操作均摊 \(O(\log n)\) |
实现难度 | 复杂,情况讨论多 | 简单,代码短小 | 中等,旋转逻辑需要清晰 |
空间开销 | 每个节点需存 height |
每个节点需存 priority |
每个节点需存 parent 指针 |
常数 | 较大(旋转频繁) | 较小 | 较小(但splay操作长) |
适用场景 | 查找密集,修改较少 | 绝大多数平衡树场景 | 有区间操作,或数据访问有局部性 |
对于初学者和信息学竞赛选手来说,Treap 是最需要优先掌握的平衡树,因为它足够应对大多数模板题,且代码简单不易出错。Splay 树功能更强大,是进阶选手必须掌握的利器。而 AVL 树,则更多地作为理解平衡思想的经典案例出现在数据结构的教材中。
第三节 哈希表
在信息学竞赛中,经常会遇到需要在庞大的数据集中快速查找、统计或判断某个元素是否存在的问题。如果数据范围非常大,例如,需要判断一个范围在 1 到 10 亿之间的数字是否出现过,直接开一个大小为 10 亿的数组来记录是不现实的,因为它会占用巨量的内存空间。
为了解决这类问题,信息学家们设计了一种巧妙的工具——哈希算法(Hash Algorithm)。
哈希算法的核心思想是映射与压缩。它可以将任意长度的输入(可能是一个巨大的数字、一个长字符串,甚至更复杂的数据结构),通过一个特定的哈希函数(Hash Function),转换成一个固定长度的、通常是较小的数值,这个数值被称为哈希值(Hash Value)。
可以把哈希函数想象成一个神奇的“搅拌机”。无论你放进去的是什么水果(苹果、香蕉、西瓜),它都能输出一杯固定大小的果汁。即使是两种非常相似的水果,榨出来的果汁也可能看起来天差地别。哈希算法的目标就是让不同的输入(不同的水果)能够生成不同的哈希值(不同口味的果汁)。通过比较哈希值,我们就能快速地判断原始输入是否可能相同。
本章将详细介绍数值和字符串的哈希函数构造方法,以及一个不可避免的问题——哈希冲突及其处理方法。
3.1 【5】数值哈希函数构造
3.1.1 什么是数值哈希函数?
数值哈希函数处理的是数字。它的任务是,将一个取值范围可能非常大的整数,映射到一个相对较小的、可以用作数组下标的范围内。
例如,班级里有 50 名学生,他们的学号可能是从 20240001
到 20249999
之间任意的 50 个数字。如果我们想快速查询某个学号的学生是否存在,可以开一个大小为 10000 的数组,但这太浪费空间了。我们希望将这些巨大的学号,映射到 0
到 49
(或者 1
到 50
)这样的小范围里,方便我们用一个大小为 50 的数组来存储信息。这个将大学号映射到小下标的“规则”,就是数值哈希函数。
一个好的数值哈希函数应该具备两个特点:
- 计算简单:函数本身的计算过程不能太复杂,否则就失去了“快速”的意义。
- 分布均匀:应尽可能地将不同的数字映射到不同的位置,减少“多个不同学号被映射到同一个位置”的情况。这种情况被称为哈希冲突(Hash Collision)。
3.1.2 常见的数值哈希构造方法
在各种构造方法中,除留余数法(Division Method) 是最常用也是最简单的一种。
它的思想非常直接:选择一个合适的正整数 \(M\) ,对于任意的数值关键字 \(key\) ,其哈希值 \(H(key)\) 计算公式为:
\(H(key) = key \pmod M\)
这里的 \(\pmod M\) 就是取 \(key\) 除以 \(M\) 的余数。例如,如果 \(M=100\) ,那么学号 20240321
的哈希值就是 \(20240321 \pmod {100} = 21\)。这样,一个巨大的学号就被映射到了 0
到 99
的范围内。
如何选择 \(M\) ?
\(M\) 的选择至关重要,它直接影响到哈希冲突的概率。一个经验法则是:\(M\) 应该选择一个不小于哈希表大小(即你需要的数组大小)的质数。
为什么是质数?举个例子,假设我们要存储的学号末尾数字都是偶数,如果我们选择 \(M=10\) ,那么 \(key \pmod {10}\) 的结果也都是偶数,哈希值 1, 3, 5, 7, 9
这些位置就永远不会被用到,而 0, 2, 4, 6, 8
这些位置的冲突概率就大大增加了。但如果我们选择一个质数,比如 \(M=97\) ,那么即使是规律性很强的输入数据,计算出的哈希值也会在 0
到 96
之间分布得更加均匀,从而有效减少冲突。
3.1.3 伪代码与C++代码模板
算法伪代码:
function Numeric_Hash(key, M):// key: 输入的数值// M: 模数,通常是一个质数return key mod M
C++ 代码模板:
#include <iostream>using namespace std;// M 通常选择一个质数,例如 100003
const int M = 100003; /*** @brief 计算数值的哈希值* @param key 输入的整数* @return key 对 M 取模后的哈希值*/
int get_hash(int key) {// 为了防止 key 是负数,C++ 的负数取模结果可能也是负数// 通过 (key % M + M) % M 的方式确保结果为非负数return (key % M + M) % M;
}int main() {int student_id = 20240321;int hash_value = get_hash(student_id);// 学号 20240321 对应的哈希值为:20240321 % 100003 = 20182cout << "学号 " << student_id << " 的哈希值是: " << hash_value << endl;return 0;
}
3.2 【6】字符串哈希函数构造
3.2.1 字符串哈希的挑战
数值哈希处理的是数字,但我们更常遇到的是字符串。如何将一个字符串,比如 "hello"
或者 "luogu"
,也转换成一个数字,从而可以对它进行存储和比较呢?
计算机本身就是用数字(ASCII码或Unicode码)来存储字符的。例如,在ASCII码中,'a'
是 97,'b'
是 98,等等。一个很自然的想法是,我们可以把字符串看作一个特殊的“数字”。
3.2.2 核心方法:P进制哈希
我们可以借鉴P进制的思想来构造字符串的哈希函数。一个十进制数 \(123\) 可以表示为 \(1 \times 10^2 + 2 \times 10^1 + 3 \times 10^0\)。类似地,我们可以将一个字符串看作一个 P进制 数,其中字符串的每个字符就是这个P进制数的每一位上的“数值”,而 \(P\) 是我们选择的基数。
对于一个字符串 \(S = s_1s_2s_3...s_n\) ,其哈希函数可以定义为:
\(H(S) = (s_1 \times P^{n-1} + s_2 \times P^{n-2} + \dots + s_n \times P^0) \pmod M\)
其中,\(s_i\) 是字符串第 \(i\) 个字符的整数表示(例如ASCII码),\(P\) 是一个选定的基数,\(M\) 是一个选定的模数。
如何选择 \(P\) 和 \(M\)?
为了让哈希函数的效果更好,即冲突概率更低,\(P\) 和 \(M\) 的选择需要满足一些经验规则:
- 基数 \(P\):应该选择一个质数,且这个质数要大于所有可能出现的字符的种类数。例如,如果字符串只包含小写字母,那么字符种类是 26。我们可以选择一个比 26 大的质数,比如 131 或者 13331。这些数字在实践中被证明效果很好。
- 模数 \(M\):应该选择一个足够大的质数,以减小哈希冲突的概率。这个数的大小通常要能存放在一个
long long
类型的变量中。常用的模数有 \(10^9+7\)、\(10^9+9\)、\(998244353\) 等。
一个特别的技巧:自然溢出
在信息学竞赛中,为了追求极致的效率和代码的简洁性,选手们常常使用一种被称为“自然溢出”的技巧。具体做法是,选择一个 unsigned long long
类型来存储哈希值,它的取值范围是 \([0, 2^{64}-1]\)。在计算哈希值的过程中,不进行任何取模操作。当计算结果超过 unsigned long long
的最大值时,它会自动“溢出”,效果等价于对 \(2^{64}\) 取模。这种方法省去了取模运算的时间,且由于 \(2^{64}\) 是一个巨大的合数,其哈希效果在实践中也相当不错。
3.2.3 快速计算子串哈希:前缀哈希法
如果我们需要频繁计算一个长字符串中任意子串的哈希值,每次都从头遍历子串来计算会非常慢。这时,我们可以使用前缀哈希法来优化。
我们预处理出两个数组:
h
数组:h[i]
存储字符串 \(S\) 前 \(i\) 个字符组成的前缀 \(S[1..i]\) 的哈希值。p
数组:p[i]
存储 \(P^i \pmod M\) 的值。
h
数组的递推公式为:\(h[i] = (h[i-1] \times P + s_i) \pmod M\)。
现在,假设我们想求子串 \(S[l..r]\) (从第 \(l\) 个字符到第 \(r\) 个字符)的哈希值。
- 前缀 \(S[1..r]\) 的哈希值是 \(h[r]\)。
- 前缀 \(S[1..l-1]\) 的哈希值是 \(h[l-1]\)。
观察哈希值的计算公式, \(h[r]\) 相当于 \(S[1..l-1]\) 这部分对应的数值“左移”了 \(r-(l-1)\) 位,也就是乘以了 \(P^{r-l+1}\) ,然后加上了 \(S[l..r]\) 对应的数值。
所以,我们可以得到:
\(h[r] \equiv h[l-1] \times P^{r-l+1} + H(S[l..r]) \pmod M\)
通过移项,我们得到计算子串 \(S[l..r]\) 哈希值的公式:
\(H(S[l..r]) = (h[r] - h[l-1] \times P^{r-l+1}) \pmod M\)
注意,在计算减法取模时,结果可能会是负数。为了保证结果非负,我们应该使用 (a - b % M + M) % M
的形式。如果使用 unsigned long long
自然溢出,则可以直接相减。
3.2.4 伪代码与C++代码模板
算法伪代码:
// --- 预处理 ---
function Precompute_Hash(S, n, P, M):h[0] = 0p[0] = 1for i from 1 to n:p[i] = (p[i-1] * P) mod Mh[i] = (h[i-1] * P + S[i]) mod M// --- 查询子串哈希 ---
function Get_Substring_Hash(l, r):// 计算 S[l..r] 的哈希值len = r - l + 1hash_val = (h[r] - h[l-1] * p[len] % M + M) % Mreturn hash_val
C++ 代码模板 (采用 unsigned long long
自然溢出):
#include <iostream>
#include <string>
#include <vector>using namespace std;typedef unsigned long long ULL;const int N = 1000010; // 字符串最大长度
const int P = 131; // 基数 PULL h[N]; // h[i] 存储字符串前 i 个字符的哈希值
ULL p[N]; // p[i] 存储 P 的 i 次方/*** @brief 计算字符串 s 从下标 l 到 r 的子串的哈希值* @param l 子串左端点 (1-based)* @param r 子串右端点 (1-based)* @return 子串的哈希值*/
ULL get_hash(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1];
}int main() {ios::sync_with_stdio(false);cin.tie(0);string s;cin >> s;int n = s.length();// 预处理 p 数组和 h 数组p[0] = 1;for (int i = 1; i <= n; ++i) {p[i] = p[i - 1] * P;// 注意字符串下标从 0 开始,而我们习惯从 1 开始处理h[i] = h[i - 1] * P + s[i - 1]; }// 示例:查询 "abacaba" 中 "aca" 的哈希值// "aca" 是原串的第 3 到 5 个字符// 假设 s = "abacaba"int l = 3, r = 5;cout << "子串 " << s.substr(l - 1, r - l + 1) << " 的哈希值是: " << get_hash(l, r) << endl;// 示例:比较两个子串是否相同// 比较 S[1..3] ("aba") 和 S[5..7] ("aba")if (get_hash(1, 3) == get_hash(5, 7)) {cout << "子串 S[1..3] 和 S[5..7] 相同" << endl;}return 0;
}
3.2.5 洛谷例题与题解
题目:P3370 【模板】字符串哈希
题目大意:
给定 \(N\) 个字符串,询问其中有多少个不同的字符串。
解题思路:
这是字符串哈希最经典的应用。我们可以依次读入每个字符串,计算出它的哈希值。然后,将这些哈希值存入一个数据结构中,最后统计这个数据结构里有多少个不重复的元素即可。
为了方便地统计不重复元素的个数,我们可以:
- 将所有计算出的哈希值存入一个数组。
- 对这个数组进行排序。
- 使用
std::unique
函数(或手动遍历)来统计排序后数组中不重复的元素个数。
C++ 题解代码:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>using namespace std;typedef unsigned long long ULL;const int P = 131; // 基数// 计算单个字符串的哈希值
ULL calculate_string_hash(const string& s) {ULL hash_value = 0;for (char c : s) {hash_value = hash_value * P + c;}return hash_value;
}int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;vector<ULL> hash_values;for (int i = 0; i < n; ++i) {string str;cin >> str;hash_values.push_back(calculate_string_hash(str));}// 排序sort(hash_values.begin(), hash_values.end());// 使用 unique 函数去重,它会返回去重后最后一个元素的下一个位置// 两个指针的差值就是不重复元素的个数int unique_count = unique(hash_values.begin(), hash_values.end()) - hash_values.begin();cout << unique_count << endl;return 0;
}
3.3 【6】哈希冲突的常用处理方法
3.3.1 什么是哈希冲突?
哈希函数的目标是为每个不同的输入生成一个唯一的哈希值。然而,由于哈希值的范围(由模数 \(M\) 决定)通常远小于输入的可能范围,根据抽屉原理,不可避免地会出现两个或多个不同的输入(\(key_1 \neq key_2\))却得到了相同的哈希值(\(H(key_1) = H(key_2)\))的情况。这种情况就叫做哈希冲突。
可以把哈希表想象成一个旅馆,每个房间有一个编号(哈希值)。哈希冲突就像来了两个不相识的客人,却被分配了同一个房间。旅馆管理员(我们的程序)必须有办法处理这种情况,让两个客人都能住下。
处理哈希冲突的方法有很多,这里介绍两种最经典的方法:拉链法和开放定址法。同时,介绍一种有效降低冲突概率的方法:双哈希。
3.3.2 方法一:拉链法 (Chaining)
拉链法,又称链地址法,是处理哈希冲突最常用的方法。
核心思想:
将哈希表(通常是一个数组)的每个位置都看作一个“桶”或“槽位”。这个桶里不是直接存储一个元素,而是存储一个链表(或者动态数组 std::vector
)的头节点。所有哈希值相同的元素,都被依次放入对应位置的链表中。
工作流程:
- 插入元素 \(key\):
- 计算 \(key\) 的哈希值 \(h = H(key)\)。
- 在哈希表数组的第 \(h\) 个位置,找到对应的链表。
- 将元素 \(key\) 添加到这个链表的末尾。
- 查找元素 \(key\):
- 计算 \(key\) 的哈希值 \(h = H(key)\)。
- 在哈希表数组的第 \(h\) 个位置,找到对应的链表。
- 遍历这个链表,逐一检查链表中的元素是否与要查找的 \(key\) 相等。如果找到,则查找成功;如果遍历完整个链表都未找到,则查找失败。
伪代码:
// HashTable 是一个数组,每个元素是一个链表
HashTable table[M];function Insert(key):h = H(key)// 在 table[h] 对应的链表中查找 key 是否已存在,避免重复插入// ...// 如果不存在,将 key 插入到 table[h] 链表的头部或尾部function Find(key):h = H(key)// 遍历 table[h] 对应的链表for each element in table[h]:if element == key:return true // 找到了return false // 没找到
C++ 代码模板 (使用 std::vector
)
#include <iostream>
#include <vector>
#include <string>using namespace std;const int M = 100003; // 选择一个质数作为哈希表的大小
vector<string> hashTable[M];// 简单的字符串哈希函数
int get_hash(const string& s) {long long hash_value = 0;const int P = 131;for (char c : s) {hash_value = (hash_value * P + c) % M;}return (int)hash_value;
}// 插入
void insert(const string& s) {int h = get_hash(s);// 简单起见,这里允许重复插入// 严谨的实现会先查找是否存在hashTable[h].push_back(s);
}// 查找
bool find(const string& s) {int h = get_hash(s);for (const string& str_in_list : hashTable[h]) {if (str_in_list == s) {return true;}}return false;
}int main() {insert("apple");insert("banana");insert("apply"); // 假设 "apply" 和 "apple" 哈希冲突if (find("apple")) {cout << "找到了 apple" << endl;}if (find("orange")) {cout << "找到了 orange" << endl;} else {cout << "没有找到 orange" << endl;}return 0;
}
3.3.3 方法二:开放定址法 (Open Addressing)
开放定址法的核心思想是:如果计算出的哈希位置 \(h\) 已经被占用了,那就按照某种规则去寻找下一个可用的空位置。
工作流程(以最简单的线性探测为例):
- 插入元素 \(key\):
- 计算初始哈希位置 \(h_0 = H(key)\)。
- 如果
table[h0]
是空的,则将 \(key\) 放入该位置。 - 如果
table[h0]
已被占用,则尝试下一个位置 \(h_1 = (h_0 + 1) \pmod M\)。 - 如果
table[h1]
仍被占用,则继续尝试 \(h_2 = (h_0 + 2) \pmod M\), \(h_3 = (h_0 + 3) \pmod M\) ...... 直到找到一个空位。
- 查找元素 \(key\):
- 计算初始哈希位置 \(h_0 = H(key)\)。
- 检查
table[h0]
的元素。- 如果是 \(key\),则查找成功。
- 如果为空,则说明 \(key\) 不存在,查找失败。
- 如果是一个不等于 \(key\) 的其他元素,说明发生了冲突,继续探测下一个位置 \(h_1 = (h_0 + 1) \pmod M\),重复此过程。
开放定址法相比于拉链法,没有链表的额外开销,但它容易产生“聚集”现象,即连续的位置都被占满,导致后续元素的插入和查找需要探测很长的距离,影响效率。
3.3.4 方法三:双哈希(降低冲突概率)
双哈希并不是一种处理冲突的结构性方法,而是一种从根源上极大地降低冲突概率的技巧,在信息学竞赛中尤为常用,特别是在字符串哈希中。
核心思想:
为同一个字符串计算两个不同的哈希值。我们可以选择两组不同的基数和模数(例如,\(\{P_1, M_1\}\) 和 \(\{P_2, M_2\}\)),分别计算出 \(hash_1\) 和 \(hash_2\)。
只有当两个字符串的 \(hash_1\) 和 \(hash_2\) 都相等时,我们才认为这两个字符串是相同的。
为什么有效?
假设使用单哈希时,两个不同字符串发生冲突的概率是 \(\frac{1}{M}\)。这是一个很小的概率。那么,如果使用两组独立的哈希函数,它们同时发生冲突的概率就是 \((\frac{1}{M})^2 = \frac{1}{M^2}\),这个概率变得微乎其微。
例如,如果 \(M \approx 10^9\),那么冲突概率大约是 \(10^{-9}\)。而双哈希的冲突概率大约是 \(10^{-18}\),在绝大多数信息学竞赛的数据范围内,可以认为这几乎不可能发生冲突。
C++ 代码模板 (字符串双哈希)
#include <iostream>
#include <string>
#include <utility> // for std::pairusing namespace std;typedef unsigned long long ULL;
typedef long long LL;
typedef pair<LL, LL> PII;// 哈希函数1
const int P1 = 131, M1 = 1e9 + 7;
// 哈希函数2
const int P2 = 13331, M2 = 998244353;// 计算字符串 s 的双哈希值
PII get_double_hash(const string& s) {LL h1 = 0, h2 = 0;for (char c : s) {h1 = (h1 * P1 + c) % M1;h2 = (h2 * P2 + c) % M2;}return {h1, h2};
}int main() {string s1 = "luogu";string s2 = "luogu";string s3 = "google";PII hash1 = get_double_hash(s1);PII hash2 = get_double_hash(s2);PII hash3 = get_double_hash(s3);if (hash1 == hash2) {cout << "'" << s1 << "' 和 '" << s2 << "' 的双哈希值相同。" << endl;}if (hash1 != hash3) {cout << "'" << s1 << "' 和 '" << s3 << "' 的双哈希值不同。" << endl;cout << "Hash1: (" << hash1.first << ", " << hash1.second << ")" << endl;cout << "Hash3: (" << hash3.first << ", " << hash3.second << ")" << endl;}return 0;
}
在解决类似洛谷 P3370 的问题时,如果担心单哈希会被特殊数据卡掉(即出题人故意构造冲突数据),使用双哈希或三哈希是一种非常稳妥的策略。