一站式搞定数据结构

_2028_ · 2025-08-22 15:33:20 · 算法·理论

开坑，陆续写完。

算法可视化-usfca

算法可视化-visualgo

csacademy

写在前面

本文编者才疏学浅，有不足请指出，可以通过私信或者评论区联系我来和我进行更进一步的学术交流。编者学业繁忙，可能并不能及时对所有问题做出回复，但原则上处理时间不超过 600h。

本文宗旨并非讲解一些很难的题，而是用尽量简明的语言和丰富的引用来作为大家学数据结构时的导引。当然，这篇文章的内容并不算多高深，也并不算多精细。你可以选择 OI-Wiki 来学习，也可以选择一些模板题的题解和其他人写的学习博客。但无论如何，非常感谢你能点进来，编者也会尽己所能把自己学到的和还没学到但是了解过的东西写出来。如果有些不为人知的高科技，编者也可以在了解后补充进来。

本文中的代码仅供参考，因为来源不同，不保证为同一风格，请尽量不要通过复制这些代码尝试通过题目，只有自己理解了的东西才是真正学会了的。

引用会标注在章节底部，尽量按引用顺序排序，有侵权请联系我删除。

前言

数据结构是一个很高明且神奇的东西。

在计算机科学中，数据结构是一种数据组织、管理和存储的格式。它是相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术相关。

在算法竞赛中，运行效率和存储效率永远是绕不开的话题，我们经常需要较为优秀的时空复杂度来通过一些以朴素算法无法完成的题目。因此数据结构作为算法竞赛一个较为著名和重要的板块，值得竞赛选手花些时间进行较为深入的学习。

数据结构贯穿了每位选手的 OI 历程，从初学时的数组，栈，队列到小有所成时的线段树，平衡树，再到省队国赛时期的 LCT，K-D Tree 等等。每个人在进步的过程中都绕不开它们。作为一种组织数据的方式和工具，它们即便不能显而易见的摆在题面上，但其对众多题目解法的影响和优化是巨大的。

虽然数据结构大多时候是作为工具来对题目的解决起辅助作用，但是也有很多热爱它们的人，这些人或是普通的算法学习者，或是走在领域最前沿的研究者，或是把更多人带领进这个领域的教学者。每个人都其乐融融的思考和交流。这样浓重的学习氛围的是令我十分惊叹的。

感谢我的教练和父母带领我进入OI圈子，感谢广大选手在训练过程中对我进行的指导和留下的数不尽的学习资料，感谢noip让我见识到了原来数据结构可以如此复杂且优雅，感谢我的好兄弟 Swedish_Pigeon 教了我很多东西。

编者太菜，但仍希望为 OI 圈子做些贡献，特此写作这篇文章，在学习总结的同时分享给大家。编者不敢说能帮到大家，希望大家抱着批判性的眼光审视这篇文章，指出不足和错误，编者感激不尽。同时，编者还会尝试写一些别的板块的文章，望各位读者多多支持 qwq。

2025.8.23

~~扯了这么多没用的，该进入正文了~~

Part 1 线性数据结构

0x01 数组

定义与性质

数组是一个固定长度的存储相同数据类型的数据结构，数组中的元素被存储在一段连续的内存空间中。它是最简单的数据结构之一，大多数现代编程语言都内置数组支持。

复杂度分析

修改：单点修改 O(1)，区间修改依据情况而定。

查询：单点查询 O(1)，区间查询依据情况而定。

优势与劣势

优势：单点复杂度低，便于维护，思维难度近似为 0，可以解决非常非常多的问题。

劣势：区间复杂度较高，通常在全局下至少是 O(n^2) 的，适合解决 n \le 5000 的问题。

0x02 栈

定义与性质

栈是一种运算受限的线性表。即限定仅在表尾进行插入和删除操作的线性表。其具有后进先出（last in first out）的性质。

我们称

操作

栈只有两种基本操作：入栈和出栈。

入栈指将一个元素插入至栈顶位置。

出栈指将栈顶位置的元素移除。

实现

栈的实现通常有三种方式：顺序栈（即用数组模拟），链栈（即用链表模拟）和 STL 实现。我们通常使用顺序栈和 STL 来解决栈问题，这里给出三种实现方式的关键代码。

数组模拟栈

//元素elem进栈，a为数组，top值为当前栈的栈顶位置
int push(int* a,int top,int elem){
a[++top]=elem;
return top;
}
//数据元素出栈
int pop(int * a,int top){
if (top == -1) {
    printf("空栈");
    return -1;
}
printf("弹栈元素：%d\n",a[top]);
top--;
return top;
}

链表模拟栈

//链表中的结点结构
typedef struct lineStack {
int data;
struct lineStack* next;
}LineStack;
//stack为当前的链栈，a表示入栈元素
LineStack* push(LineStack* stack, int a) {
//创建存储新元素的结点
LineStack* line = (LineStack*)malloc(sizeof(LineStack));
line->data = a;
//新结点与头结点建立逻辑关系
line->next = stack;
//更新头指针的指向
stack = line;
return stack;
}
//栈顶元素出链栈的实现函数
LineStack* pop(LineStack* stack) {
if (stack) {
    //声明一个新指针指向栈顶结点
    LineStack* p = stack;
    //更新头指针
    stack = stack->next;
    printf("出栈元素：%d ", p->data);
    if (stack) {
        printf("新栈顶元素：%d\n", stack->data);
    }
    else {
        printf("栈已空\n");
    }
    free(p);
}
else {
    printf("栈内没有元素");
    return stack;
}
return stack;
}

STL中栈的操作

在使用前需要先引用 #include<stack>头文件。该 STL 支持一些内置好的成员函数：

stack<int> st：建立一个 int 类型，名为 st 的栈。
st.push(x)：插入参数 x 到栈顶。
st.pop()：弹出栈顶。
st.empty()：返回一个布尔类型的值，表示该栈是否为空。
st.size()：返回一个 int 类型的值，表示该栈的元素数量
st.top()：返回栈顶元素的值。

我们可以使用 = 将一个栈的全部数据赋到另一个栈里。

变种：单调栈

定义

单调栈是一个存放下标对应元素有序的栈。

我们根据存放下标对应元素的顺序，可以分为两种单调栈：

单调递减栈，指的就是栈内存放下标对应元素构成的序列对应的元素单调递减。
单调递增栈，指的就是栈内存放下标对应元素构成的序列对应的元素单调递增。

一定注意，我们存放的一般是下标，而不是元素。但是作为比较的标准是下标对应的元素。

当然，我们的维护对象不一定是一个具体的数值，任何可以被维护成单调的东西都可以塞进单调栈里。

这里放一下模板题目的关键代码以供参考。

for(int i = n;i >= 1;i--)
{
    while(!st.empty() && a[st.top()] <= a[i]) st.pop();
    if(!st.empty()) f[i] = st.top();
    else f[i] = 0;
    st.push(i);
}

具体操作

在每次元素入栈时与栈顶元素进行比较，如果不满足想要维护的条件，则不入栈，反之则入栈。单调栈处理的是寻找以某个值为最小/大值的最大区间的问题，比如用于离线解决 RMQ 问题，是一个用途非常广泛的数据结构。同时，在一个东西上维护单调性也是非常重要的一种思想。

复杂度分析

栈的时间复杂度：两种基本操作均为 O(1)。

栈的空间复杂度：O(n)

单调栈的时间复杂度：在解决一个典型应用——离线RMQ问题时为 O(q\log q + q\log n)。

例题

B3614 【模板】栈

P5788 【模板】单调栈

题单 - 单调栈

0x03 队列

（一）普通队列

定义与性质

队列（queue）是一种具有「先进入队列的元素一定先出队列」性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。

操作

队列只有两种基本操作：入队和出队。

入队指将一个元素插入至队尾位置。
出队指将队头位置的元素移除。
实现

普通的队列通常有三种实现方式：数组模拟队列，双栈模拟队列和C++自带的STL。

数组模拟队列

手写情况下通常用一个数组模拟一个队列，用两个变量标记队列的首尾。
```
int q[SIZE], ql = 1, qr;
```
队列操作对应的代码如下：

插入元素：q[++qr] = x;

删除元素：ql++;

访问队首：q[ql]

访问队尾：q[qr]

清空队列：ql = 1; qr = 0;

int q[SIZE],ql = 1,qr = 0;
void push(int x){q[++qr] = x;}
void pop(){ql++;}
int get_front(){return q[ql];}
int get_back(){return q[qr];}
int get_size(){return qr-ql+1;}
void clear(){ql = 1; qr = 0;}
bool is_empty()
{
    if(get_size() < 1) return true;
    else return false;
}

双栈模拟队列

这种方法主要使用两个栈 F, S 模拟一个队列，其中 F 是队尾的栈，S 代表队首的栈，支持 push（在队尾插入），pop（在队首弹出）操作：

push：插入到栈 F 中。

pop：如果 S 非空，让 S 弹栈；否则把 F 的元素倒过来压到 S 中（其实就是一个一个弹出插入，做完后是首尾颠倒的），然后再让 S 弹栈。因为每个元素只会进入/转移/弹出一次，均摊复杂度 O(1)。

模拟的思路还是比较巧妙的，但编者实在不知道双栈模拟队列相较于数组和 STL 的优势在哪里。

stack<int> F,S;
void push(int x){F.push(x)}
void pop()
{
    if(!S.empty()) S.pop();
    else
    {
        while(!F.empty()) 
        {
            S.push(F.top());
            F.pop();
        }
        S.pop();
    }
}

STL队列

使用前要加上头文件 #include<queue>。该STL支持一些内置好的成员函数：

queue<int> q：建立一个 int 类型，名为 q 的队列。
q.push(x)：插入参数 x 到队尾。
q.pop()：弹出队首元素
q.front()：返回队首元素
q.back()：返回队尾元素
q.empty()：返回一个布尔类型的值，表示该队列是否为空。
q.size()：返回一个 int 类型的值，表示该队列的元素数量

我们可以使用 = 将一个队列的全部数据赋到另一个队列里。

例题

B3616 【模板】队列

P4829 kry loves 2048

（二）双端队列

定义与性质

双端队列是指一个可以在队首/队尾插入或删除元素的队列。相当于是栈与队列功能的结合。

操作

具体地，双端队列应该支持的操作有 4 个：

在队首插入一个元素
在队尾插入一个元素
在队首删除一个元素
在队尾删除一个元素

实现

双端队列通常有两种实现方式：数组模拟队列和 C++ 自带的 STL。数组实现与普通队列基本一致，这里不再赘述。

STL 双端队列

使用前要加上头文件 #include<deque>。该 STL 支持一些内置好的成员函数：

deque<int> q：建立一个 int 类型，名为 q 的双端队列。
q.front()：返回队首元素
q.back()：返回队尾元素
q.push_back()：在队尾插入元素
q.pop_back()：弹出队尾元素
q.push_front()：在队首插入元素
q.pop_front()：弹出队首元素
q.insert()：在指定位置前插入元素（传入迭代器和元素）
q.erase()：删除指定位置的元素（传入迭代器）
q.empty()：队列是否为空
q.size()：返回队列中元素的数量

我们可以使用 = 将一个双端队列的全部数据赋到另一个双端队列里。同时，也可以使用[]来访问容器中指定位置的元素。

例题

（三）优先队列

STL的<priority_queue>头文件中提供了priority_queue，即优先队列，因其实现与堆更相似，暂不讲述它的原理。你现在只需要知道它是一个顶部元素总是具有最高优先级的队列即可。我们这里对该 STL 的操作做简略介绍。

// 声明一个整型优先队列
priority_queue<int> pq;

// 声明一个自定义类型的优先队列，需要提供比较函数
struct compare {
    bool operator()(int a, int b) {
        return a > b; // 这里定义了顶部值为最小值的一个优先队列
    }
};
priority_queue<int, vector<int>, compare> pq_min;

pq.empty()：检查队列是否为空。
pq.size()：返回队列中的元素数量。
pq.top()：返回队列顶部的元素。
pq.push()：向队列添加一个元素。
pq.pop()：移除队列顶部的元素。

关于它的原理，可以跳转到 0x23 进一步学习。

例题

见 0x23 堆部分

（四）单调队列

引入

考虑一个问题：给出一个长度为 n 的数组，编程输出每 k 个连续的数中的最大值和最小值。

首先想到暴力，对于每个连续区间暴力求解，复杂度是 O(n \times k) 的，并不优秀。

我们发现每次遍历区间时出现了大量重复计算的部分。譬如在计算区间 [1,k] 和 [2,k+1] 时重复考虑了 [2,k]。这时我们使用单调队列可以解决这个问题。

定义与原理

顾名思义，单调队列的重点分为「单调」和「队列」。

「单调」指的是元素的「规律」——递增（或递减）。
「队列」指的是元素只能从队头和队尾进行操作。

有了上面「单调队列」的概念，很容易想到用单调队列进行优化。

要求的是每连续的 k 个数中的最大（最小）值，很明显，当一个数进入所要 "寻找" 最大值的范围中时，若这个数比其前面（先进队）的数要大，显然，前面的数会比这个数先出队且不再可能是最大值。也就是说——当满足以上条件时，可将前面的数弹出，再将该数真正放进队尾。就相当于维护了一个递减的队列，符合单调队列的定义，减少了重复的比较次数，不仅如此，由于维护出的队伍是查询范围内的且是递减的，队头必定是该查询区域内的最大值，因此输出时只需输出队头即可。

这个数据结构原理较为简单，但理解起来还是有些抽象的，推荐多阅读几篇文章或者结合题目来理解。

操作

相当于可以从队尾出队的普通队列，因此我们只需按题意需求模拟即可，没有太过复杂的操作。

实现

有数组模拟和 deque 模拟两种方式，由于 deque 常数过大，这里推荐使用数组模拟。放一下模板题关键部分的实现。

//该部分是数组模拟队列求最小值
int head = 1,tail = 0;
for(int i = 1;i <= n;i++)
{
    while(head <= tail && q[head] + k <= i) head++;
    while(head <= tail && a[i] < a[q[tail]]) tail--;
    q[++tail] = i;
    if(i >= k) printf("%d ",a[q[head]]);
}

例题

P1886 滑动窗口 /【模板】单调队列

引用 & 推荐阅读

数据结构——双端队列

C++ 容器类 <priority_queue>

单调队列：实用而好写的数据结构

（五）STL中 stack,queue 和 deque 的常数讨论

1. 双端队列 - deque

首先要理解deque，因为stack和queue默认都是基于deque实现的。

实现原理

deque（Double-Ended Queue）的设计目标是结合vector和list的优点，提供高效的随机访问以及在头尾两端的高效插入和删除。它的实现通常不是一个单一的连续内存块（像vector），也不是一个链表（像list），而是一种“分段连续”的结构。

一个典型的deque实现包含以下部分：

Map（控制中心）：一个指向指针的指针（T*），或者一个 vector<T>。这个“map”本身是一小块连续内存，它存储着指向各个“段”（chunk或block）的指针。map的大小是可以动态增长的。
段（Chunks/Blocks）：实际存储数据的地方。每个段是一个固定大小的连续数组。常见的段大小是512字节或4096字节（取决于存储的对象类型），这样可以确保一个段能很好地适配内存页。
迭代器：deque的迭代器是一个复杂的类，它至少包含四个指针：
current：指向当前迭代器所在的元素。
first：指向当前段的起始位置。
last：指向当前段的末尾（最后一个元素的下一个位置）。
node：指向map中控制当前段的那个指针。

常数分析（时间复杂度）

随机访问（operator[], at）: O(1)。虽然比vector慢，但仍然是常数时间。需要两次解引用：先通过map找到对应的段，再在段内找到对应的元素。
在头或尾插入/删除（push_front, push_back, pop_front, pop_back）: 平摊 O(1)。大部分情况下只是在一个固定大小的数组里操作，常数时间。只有在段耗尽或map耗尽需要重新分配时，那次操作的成本是O(n)，但平摊下来仍然是常数。
在中间插入/删除（insert, erase）: O(n)。需要移动元素来保持顺序。平均需要移动 n/2 个元素，效率比vector高（因为vector可能需要移动所有后续元素并重新分配），但比list的 O(1) 要差。
空间开销：比vector和list都大。因为它有map的开销和每个段可能未完全利用的空间浪费。

2.栈和队列 - stack & queue

它们俩的底层实现容器都是deque，本质就是一个限制了端口的deque。对于stack和queue，无需多想，直接使用默认版本（基于deque）。它们在绝大多数场景下都是性能最优、最安全的选择。但是，如果你需要更稳定的操作，可以使用 list 作为底层容器。

对于以 list 作为底层容器而言，有以下优势：

稳定的时间复杂度：list的所有操作（插入、删除）都是严格的O(1)时间复杂度，没有平摊概念
没有重新分配开销：与vector和deque不同，list不会因为容量不足而重新分配内存
中间插入/删除高效：如果你需要扩展栈或队列的功能（尽管这不常见），list在中间位置的操作也更高效

但是，它也有一些劣势：

内存使用：list的每个元素都有额外的指针开销（指向前后元素），因此内存使用可能比deque或vector更高。
缓存不友好：list的元素在内存中不是连续存储的，可能导致缓存命中率较低。

如果你需要频繁地在中间位置插入或删除元素（虽然这不是栈和队列的典型用法），list会更高效。所以尽量减少使用裸的deque来实现双端队列，尤其是需要大量访问中间元素的时候。下面是重定义 stack 和 queue 底层容器为 list 的方法。

std::stack<int, std::list<int>> myStack;
std::queue<int, std::list<int>> myQueue;

当然 vector也可以作为底层容器。但是 queue不能使用vector作为底层容器，因为vector没有提供pop_front()操作。

更多信息可以翻一翻官方给的文档和头文件源码来探究探究。

0x04 哈希表

（一）朴素哈希

定义与性质

哈希表又称散列表，一种以「key-value」形式存储数据的数据结构。所谓以「key-value」形式存储数据，是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值，就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组，这种数组的下标可以是很大的整数，浮点数，字符串甚至结构体。

哈希函数

要让键值对应到内存中的位置，就要为键值计算索引，也就是计算这个数据应该放到哪里。这个根据键值计算索引的函数就叫做哈希函数，也称散列函数。比如取一串数字的后四位或者数字和都是一种哈希函数。在实际的应用中，键值可能是更复杂的东西，比如浮点数、字符串、结构体等，这时候就要根据具体情况设计合适的哈希函数。哈希函数应当易于计算，并且尽量使计算出来的索引均匀分布。

能为 key 计算索引之后，我们就可以知道每个键值对应的值 value 应该放在哪里了。假设我们用数组 a 存放数据，哈希函数是 f，那键值对 (key, value) 就应该放在 a[f(key)] 上。不论键值是什么类型，范围有多大，f(key) 都是在可接受范围内的整数，可以作为数组的下标。在 OI 中，最常见的情况应该是键值为整数的情况。当键值的范围比较小的时候，可以直接把键值作为数组的下标，但当键值的范围比较大，比如以 10^9 范围内的整数作为键值的时候，就需要用到哈希表。一般把键值模一个较大的质数作为索引，也就是取 f(x)=x \bmod M 作为哈希函数。

字符串哈希

一种比较常见的情况是 key 为字符串的情况，由于不支持以字符串作为数组下标，并且将字符串转化成数字存储也可以避免多次进行字符串比较。所以在 OI 中，一般不直接把字符串作为键值，而是先算出字符串的哈希值，再把其哈希值作为键值插入到哈希表里。关于字符串的哈希值，我们一般采用进制的思想，将字符串想象成一个 127 进制的数。那么，对于每一个长度为 n 的字符串 s，就有：就有：

x = s_0 \cdot 127^0 + s_1 \cdot 127^1 + s_2 \cdot 127^2 + \dots + s_n \cdot 127^n

我们可以将得到的 x 对 2^{64}（即 unsigned long long 的最大值）取模。这样 unsigned long long 的自然溢出就等价于取模操作了。可以使操作更加方便。当然，可以构造数据做掉这个哈希函数，事实上，没有什么哈希函数能完全保证每个键值都对应不同的索引。所以我们会选择一个质数取模来避免索引重复。下面给出一个字符串哈希的关键实现源码：

//来自P3370题解，作者为皎月半洒花(id:28313)
unsigned long long hashe(char s[])
{
   int len=strlen(s);
   unsigned long long ans=0;
   for (int i=0;i<len;i++)
   ans=(ans*base+(unsigned long long)s[i])%mod+prime;
   return ans;
}

同时，为了防止键值重复，我们可以使用双哈希，即同时对两个大质数取模，只有两个大质数的模数都相等才能说这两个键值相等。

冲突

冲突无法 100\% 避免，但我们不能因为出现冲突就导致代码砰的一下炸掉，这样做除了一分不得之外没什么问题。所以这时候就需要一些方法来处理冲突。在 OI 中，最常用的方法是拉链法。

拉链法，顾名思义，在每个地方拉一条链表，也就是在每个存放数据的地方开一个链表，如果有多个键值索引到同一个地方，只用把他们都放到那个位置的链表里就行了。查询的时候需要把对应位置的链表整个扫一遍，对其中的每个数据比较其键值与查询的键值是否一致。如果索引的范围是 1\ldots M，哈希表的大小为 N，那么一次插入/查询需要进行期望 O(\frac{N}{M}) 次比较。

//这里给出OI-Wiki的实现
constexpr int SIZE = 1000000;
constexpr int M = 999997;

struct HashTable {
  struct Node {
    int next, value, key;
  } data[SIZE];

  int head[M], size;

  int f(int key) { return (key % M + M) % M; }

  int get(int key) {
    for (int p = head[f(key)]; p; p = data[p].next)
      if (data[p].key == key) return data[p].value;
    return -1;
  }

  int modify(int key, int value) {
    for (int p = head[f(key)]; p; p = data[p].next)
      if (data[p].key == key) return data[p].value = value;
  }

  int add(int key, int value) {
    if (get(key) != -1) return -1;
    data[++size] = Node{head[f(key)], value, key};
    head[f(key)] = size;
    return value;
  }
};

（二）一些有趣的哈希

加密哈希

类似于 MD5，SHA-1，SHA-2，SHA-3 一类的哈希函数都属于加密哈希。它们通常会为了极致的安全性牺牲一些效率。	算法名称	输出长度（比特）	简介
MD5	128	曾广泛用于文件完整性校验。绝对不安全。已被证明存在大量碰撞，可在短时间内被破解。	已破解，禁止用于任何安全目的。
SHA-1	160	由NSA设计，曾用于 TLS/SSL、Git 版本控制等。不安全。谷歌于2017年成功实施了碰撞攻击。	已破解，禁止用于安全目的。Git 等正在迁移。
SHA-2	224, 256, 384, 512	SHA-1的替代者，家族包括 SHA-256, SHA-512 等。目前应用最广泛的加密哈希算法。	目前安全，是行业的黄金标准。
SHA-3	224, 256, 384, 512	并非 SHA-2 的升级版，而是基于全新的 Keccak 算法设计。由 NIST 在2015年标准化。	目前安全，作为 SHA-2 的未来替代方案。
BLAKE2	最多512	比 MD5 更快且更安全，比 SHA-3、SHA-2 在某些平台上更快。被用于许多软件（如 libsodium）和加密货币。	目前安全且高效，是 MD5/SHA-1 的理想替代品。
RIPEMD-160	160	设计初衷是替代 MD4/5。不如 SHA 家族流行，但在比特币等加密货币中有特定应用。	尚未被攻破，但输出长度较短，长期来看不如 SHA-256 安全

这里我们使用 MD5 举例展示一下加密哈希的基本运作逻辑。

概述

MD5，全称 Message-Digest Algorithm 5，是一种广泛使用的加密哈希函数，由密码学家罗纳德·李维斯特于 1991 年设计，用以替代其前身 MD4。它能够接收任意长度的输入信息（“消息”），并输出一个固定长度为 128位（16字节）的哈希值，通常呈现为一个 32 位的十六进制数字字符串。

一个典型的MD5哈希值示例：d41d8cd98f00b204e9800998ecf8427e （这是空字符串 "" 的MD5值）

实现原理

第1步：填充补位 (Padding)

首先，对消息进行填充，使其长度（以比特为单位）对 512 取模后的余数等于 448。填充方法：

在消息末尾先添加一个 1。
然后添加若干个 0。
填充一直进行到满足 (Length % 512) = 448。

因此，消息的长度将被扩展至 512N + 448 比特。

第2步：附加长度信息 (Appending Length)

在填充完的消息后，再附加一个 64 位的二进制数，用来表示原始消息的长度（以比特为单位）。如果原始消息长度超过 2^{64}，则取其对 2^{64} 取模后的值。

经过第一步和第二步，整个消息的长度 now 正好是 512 比特的整数倍，为后续分块处理做好准备。

第3步：初始化缓冲区 (Initialize Buffers)

MD5 使用四个 32 位的链接变量（称为寄存器 A, B, C, D）来存储计算的中间状态和最终结果。它们初始化为以下固定的十六进制值（采用小端字节序）：

第4步：处理 512 位消息块 (Process Blocks)

将填充和附加长度后的总消息分割成若干个 512 位（64字节）的块。对于每一个块，执行以下核心操作：

分块：将当前 512 位的块再细分为 16 个 32 位的子块，记为 M[0] 到 M[15]。

四轮主循环：每一轮都对当前的数据块（B）和链接变量（A, B, C, D）进行 16 次类似的算术和逻辑运算。四轮共 64步操作。每一轮使用一个不同的非线性函数（F, G, H, I）和常数表 T[1...64]。

第一轮：函数 F：F(B,C,D) = (B ∧ C) ∨ (¬B ∧ D)

第二轮：函数 G：G(B,C,D) = (B ∧ D) ∨ (C ∧ ¬D)

第三轮：函数 H：H(B,C,D) = B ⊕ C ⊕ D

第四轮：函数 I：I(B,C,D) = C ⊕ (B ∨ ¬D)

在每一步中，都会对 A, B, C, D 进行复杂的更新，涉及加法模 2^{32}、与消息子块 M[k] 的相加、与常数 T[i] 的相加、以及循环左移位操作。

更新链接变量：处理完当前 512 位块后，将本轮计算得到的新的 A, B, C, D 分别与原来的 A, B, C, D 相加。这个结果将作为处理下一个消息块的初始链接变量。

第5步：输出当所有 512 位消息块都处理完毕后，最终链接变量 A, B, C, D 的拼接（共 128 位）就是整个输入消息的MD5哈希值。输出时，通常按照 A, B, C, D 的顺序，以小端字节序的方式转换为 32 位的十六进制字符串。

破解与安全性

MD5的辉煌是短暂的。由于其设计上的缺陷，早在 1996 年密码学家就发现了理论上的漏洞。2004 年，中国密码学家王小云教授团队发表了毁灭性的碰撞攻击，可以在数小时内在一台计算机上找到 MD5 碰撞。这说明：

抗碰撞性彻底失效：MD5 最核心的安全特性被打破。攻击者可以刻意伪造两个内容不同但哈希值相同的文件。
数字签名失效：攻击者可以生成一个正常的文件和一个恶意的文件，两者具有相同的 MD5 值。如果用户在正常的文件上签名，攻击者就可以用这个签名来“证明”恶意文件是经过用户认可的。
证书欺骗：历史上曾出现过利用 MD5 碰撞伪造 SSL 证书的重大安全事件（Flame 病毒）。

综上所述，我们在现代社会不要使用 MD5 存储 SSL/TLS 证书。但当毒瘤出题人把双哈希都卡掉（显然不太可能）的时候，比起气急败坏，我们可以使用 MD5 来使出题人的良苦用心化为泡影。这里给出由 DeepSeek 完成的 MD5 加密算法。

布谷鸟哈希（Cuckoo hash）

这是由 Rasmus Pagh 和 Flemming Friche Rodler 于 2001 年提出的哈希冲突解决方案，其名称源于算法通过替换已有元素完成插入的行为特征，类似于布谷鸟的巢寄生习性。该算法使用两个哈希函数计算键值存储位置，插入时优先选择空位，若目标位置均被占用则随机踢出现有键值并重新计算其存储位置，此过程需设置踢出次数限制以避免循环。其特点包括占用空间小、查询速度快。

算法原理

算法使用两个不同哈希函数计算对应key 的位置。

当两个哈希任意位置为空，则选择一个位置插入
当两个哈希有位置为空时，则插入到空位置
当两个哈希位置均不为空时，随机选择两者之一的位置上 key 踢出，计算踢出的 key 另一个哈希值对应的位置进行插入，转至 2 执行（即当再次插入位置为空时插入，仍旧不为空时，再踢出这个 key）

技术演进中存在多种优化策略，例如动态调整表大小、多态哈希函数及链地址法结合链表等。篇幅原因，这里不再赘述详细的优化逻辑，给出由 DeepSeek 完成的该算法代码。

注：两种哈希算法代码放在同一剪贴板。由于本文附带代码至少有 5000 行，为了使本文具有可读性，本文超过180行的代码大多放在剪贴板，该行为请大家理解。

0x05 链表

定义与性质

链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。

链表和数组都可用于存储数据。与链表不同，数组将所有元素按次序依次存储。不同的存储结构令它们有了不同的优势：

链表因其链状的结构，能方便地删除、插入数据，操作次数是 O(1)。但也因为这样，寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是 O(n)。
数组可以方便地寻找并读取数据，在随机访问中操作次数是 O(1)。但删除、插入的操作次数是 O(n) 次。

链表主要分为单向链表和双向链表，单向链表又分为普通链表和循环链表，下面分类阐述。

基本操作

建立链表

单向链表中包含数据域和指针域，其中数据域用于存放数据，指针域用来连接当前结点和下一结点。

双向链表中同样有数据域和指针域。不同之处在于，指针域有左右（或上一个、下一个）之分，用来连接上一个结点、当前结点、下一个结点。

向链表中插入数值

单向链表流程大致如下：

初始化待插入的数据 node；
将 node 的 next 指针指向 p 的下一个结点；
将 p 的 next 指针指向 node。

单向循环链表和单向链表流程差不多，将链表的头尾连接起来，链表就变成了循环链表。由于链表首尾相连，在插入数据时需要判断原链表是否为空：为空则自身循环，不为空则正常插入数据。

大致流程如下：

初始化待插入的数据 node；
判断给定链表 p 是否为空；
若为空，则将 node 的 next 指针和 p 都指向自己；
否则，将 node 的 next 指针指向 p 的下一个结点；
将 p 的 next 指针指向 node。

具体过程可参考下面图(左图为单向链表，右图为单向循环链表)：

对于双向链表来说，在向双向循环链表插入数据时，除了要判断给定链表是否为空外，还要同时修改左、右两个指针。

大致流程如下：

初始化待插入的数据 node；
判断给定链表 p 是否为空；
若为空，则将 node 的 left 和 right 指针，以及 p 都指向自己；
否则，将 node 的 left 指针指向 p;
将 node 的 right 指针指向 p 的右结点；
将 p 右结点的 left 指针指向 node；
将 p 的 right 指针指向 node。
从链表中删除数据

对于单向（循环）链表而言，设待删除结点为 p，从链表中删除它时，将 p 的下一个结点 p->next 的值覆盖给 p 即可，与此同时更新 p 的下下个结点。

流程大致如下：

将 p 下一个结点的值赋给 p，以抹掉 p->value；
新建一个临时结点 t 存放 p->next 的地址；
将 p 的 next 指针指向 p 的下下个结点，以抹掉 p->next；
删除 t。此时虽然原结点 p 的地址还在使用，删除的是原结点 p->next 的地址，但 p 的数据被 p->next 覆盖，p 名存实亡。

具体过程可参考下图：

对于双向链表而言，流程大致如下：

将 p 左结点的右指针指向 p 的右结点；
将 p 右结点的左指针指向 p 的左结点；
新建一个临时结点 t 存放 p 的地址；
将 p 的右结点地址赋给 p，以避免 p 变成悬垂指针；

删除 t。

实现

指针实现

这里给出单向循环链表和双向链表在OI-Wiki上的实现。

//单向循环链表
struct Node {
int value;
Node *next;
};
void insertNode(int i, Node *p) {
Node *node = new Node;
node->value = i;
node->next = NULL;
if (p == NULL) {
p = node;
node->next = node;
} else {
node->next = p->next;
p->next = node;
}
}
void deleteNode(Node *p) {
p->value = p->next->value;
Node *t = p->next;
p->next = p->next->next;
delete t;
}

//双向链表
struct Node {
  int value;
  Node *left;
  Node *right;
};
void insertNode(int i, Node *p) {
  Node *node = new Node;
  node->value = i;
  if (p == NULL) {
    p = node;
    node->left = node;
    node->right = node;
  } else {
    node->left = p;
    node->right = p->right;
    p->right->left = node;
    p->right = node;
  }
}
void deleteNode(Node *&p) {
  p->left->right = p->right;
  p->right->left = p->left;
  Node *t = p;
  p = p->right;
  delete t;
}

STL实现

list 是 STL 提供的双向链表数据结构。能够提供线性复杂度的随机访问，以及常数复杂度的插入和删除。list 的使用方法与 deque 基本相同，但是增删操作和访问的复杂度不同。list的增删复杂度均为 O(1)。但是随机访问（如 list[5]）在链表中不存在，必须使用迭代器遍历，最坏情况是 O(n)。list 的迭代器、长度、元素增删及修改相关的函数与 deque 相同，因此不作详细介绍。

由于 list 的实现是链表，因此它不提供随机访问的接口。若需要访问中间元素，则需要使用迭代器。

front()：返回首元素的引用。
back()：返回末尾元素的引用。

特殊的：forward_list 是 STL 提供的单向链表数据结构，相比于 list 减小了空间开销。forward_list 的使用方法与 list 几乎一致，但是迭代器只有单向的，因此其具体用法不作详细介绍。

例题

B3631 单向链表

【模板】双向链表

P10466 邻值查找

0x06 ST表

引入

时限 800ms 的前提下，对于一个 n 个数的数列，有 m 个询问，我们每次询问区间 [l,r] 中的最大值。(n \le 10^5，m \le 2 \times 10^6)

首先考虑暴力，每次询问枚举 [l,r] 进行统计，复杂度 O(nm)，对于较大的题目范围会导致 TLE 从而被出题人切掉。

但我们不能被出题人切掉，无论如何也不能 —— 某位金钩大佬

考虑使用单调队列优化暴力，每次询问顺便把同样长度的区间的答案做了并存了，如果询问的区间可以用小一些区间拼起来就直接拼，否则暴力去做，复杂度应该在 O(n\sqrt{m})左右，但空间复杂度会迅速增大到 O(n^2)，爆炸。

坏了，这时候我们发现前面学过的数据结构解决不了了，于是我们使用ST表解决问题。

定义与性质

ST 表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。我们说对于一个运算符 op，如果满足 x op x = x,则称其为可重复贡献问题。譬如最值问题和最大公约数问题是可重复贡献问题，而区间和问题和第k小问题不是可重复贡献问题。

ST 表对于询问可以做到 O(1) 的复杂度。虽然不支持修改，但是思想很好理解。所以它是一个较为简单的数据结构。

基本操作

ST 表基于倍增思想，我们考虑如何求出区间最大值。可以发现，如果按照一般的倍增流程，每次跳 2^i 步的话，询问时的复杂度仍旧是 O(\log n)，而问题的 m 是 2 \times 10^6，稍微估算发现复杂度还是不够优秀。

观察问题所求性质得到我们求的是一个具有「可重复贡献」性质的问题，即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，最终计算出的答案就是正确的。所以我们能使用至多两个预处理过的区间来覆盖询问区间，也就是说询问时的时间复杂度可以被降至 O(1)，在处理有大量询问的题目时十分有效。于是我们尝试实现该算法。

实现

令 f_{i,j} 表示区间 [i,i+2^j-1] 的最大值，容易得到 f_{i,0} = a_i。

根据定义式，第二维就相当于倍增的时候「跳了 2^j-1 步」，依据倍增的思路，写出状态转移方程：

f_{i,j}=\max {(f_{i,j-1},f_{i+2^{j-1},j-1})}

于是枚举 j 和 i 进行一轮一轮的初始化即可。

以上就是预处理部分。而对于查询，可以简单实现如下：

对于每个询问

根据上面对于「可重复贡献问题」的论证，由于最大值是「可重复贡献问题」，重叠并不会对区间最大值产生影响。又因为这两个区间完全覆盖了 $[l,r]$，可以保证答案的正确性，这里给出模板题代码。 ```cpp #include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int n,m,a[maxn],f[maxn][30]; void init(int a[]) { for(int i = 1;i <= n;i++) f[i][0] = a[i]; for(int j = 1;j <= 20;j++) for(int i = 1;i+(1<<j)-1 <= n;i++) f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } int qry(int l,int r) { int k = log2(r-l+1); return max(f[l][k],f[r-(1<<k)+1][k]); } int main() { scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) scanf("%d",&a[i]); init(a); for(int i = 1;i <= m;i++) { int l,r; scanf("%d%d",&l,&r); printf("%d\n",qry(l,r)); } return 0; } ``` #### 解决其他问题除 RMQ 以外，还有其它的「可重复贡献问题」。例如「区间按位与」、「区间按位或」、「区间 GCD」，ST 表都能高效地解决。如果分析一下，「可重复贡献问题」一般都带有某种类似 RMQ 的成分。例如「区间按位与」就是每一位取最小值，而「区间 GCD」则是每一个质因数的指数取最小值。需要注意的是，对于「区间 GCD」，ST 表的查询复杂度并没有比线段树更优（令值域为

w，ST 表的查询复杂度为 O(\log w)，而线段树为 O(\log n+\log w)，且值域一般是大于 n$ 的）。但是 ST 表的复杂度也没有比线段树更劣，并且编程复杂度方面 ST 表比线段树简单很多。

复杂度分析

对于普通的 RMQ 问题，初始化是 O(n \log n) 的，每次查询的均摊复杂度是 O(1) 的。

对于区间 GCD 问题，ST 表维护「区间 GCD」的时间复杂度为预处理 O(n(\log n+\log w)) ，单次查询 O(\log w)。如果想获取证明，请看这里。

例题

P3865 【模板】ST 表 & RMQ 问题

P2880 [USACO07JAN] Balanced Lineup G

P2471 [SCOI2007] 降雨量

0x07 跳表

我们说：

跳表被平衡树吊着打

Q : 不是哥们你学它干嘛

A : 炫技

引入

我们考虑问题：对于一个有序数列，支持两类操作。

插入/删除一个数。

在一个有序的序列中查找元素 k。

对于第一个操作，我们可以使用前文所述的链表解决。但链表的问题是不支持随机访问，每次访问一个位置都要从头开始遍历，这是十分糟糕的。复杂度约为 O(n)，显然较劣。于是考虑优化，我们是否可以通过在一个有序链表上进行二分查找呢？

定义与性质

首先观察单链表，单链表的特性就是每个元素存放下一个元素的引用。即：通过第一个元素可以找到第二个元素，通过第二个元素可以找到第三个元素，依次类推，直到找到最后一个元素。所以对于一个链表：1 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9 -> 10 -> 13 -> 16 -> 17 -> 18，我们如果想找一个元素，就只能从头开始遍历链表，直到找到我们需要找的元素。这样的效率是很低的。

那有没有办法提高链表的查找速度呢？

如上图所示，我们从链表中每两个元素抽出来，加一级索引，一级索引指向了原始链表，即：通过一级索引 7 的 down 指针可以找到原始链表的 7 。那现在怎么查找 10 这个元素呢？先在索引找 1、4、7、9，遍历到一级索引的 9 时，发现 9 的后继结点是 13，比 10 大，于是不往后找了，而是通过 9 找到原始链表的 9，然后再往后遍历找到了我们要找的 10，遍历结束。发现加了一级索引后，查找路径：1、4、7、9、10，查找结点需要遍历的元素相对少了，我们不需要对 10 之前的所有数据都遍历，查找的效率提升了。同理，增加二级索引和更多索引，就可以进一步缩短查找路径，从而提升效率。

基本操作

那代码该如何实现，才能使跳表满足上述这个样子呢？可以在每次新插入元素的时候，尽量让该元素有 1/2 的几率建立一级索引、1/4 的几率建立二级索引、1/8 的几率建立三级索引，以此类推，就能满足我们上面的条件。现在我们就需要一个概率算法帮我们把控这个 1/2、1/4、1/8 ... ，当每次有数据要插入时，先通过概率算法告诉我们这个元素需要插入到几级索引中，然后开始维护索引并把数据插入到原始链表中。

由于 1/2 的概率不一定是最优的，所以我们考虑扩展。首先，跳表的每一层都是一个有序链表，特别地，最底层是初始的有序链表。每个位于第 i 层的结点有 p 的概率出现在第 i+1 层，p 为常数。在 n 个结点的跳表中，期望包含 \frac{1}{p} 个元素的层为第 L(n) 层，易得 L(n) = \log_{\frac{1}{p}}n。

在跳表中查找，就是从第 L(n) 层开始，水平地逐个比较直至当前结点的下一个结点大于等于目标结点，然后移动至下一层。重复这个过程直至到达第一层且无法继续进行操作。此时，若下一个结点是目标结点，则成功查找；反之，则元素不存在。这样一来，查找的过程中会跳过一些没有必要的比较，所以相比于有序链表的查询，跳表的查询更快。

实现

获取结点的最大层数

模拟以 p 的概率往上加一层，最后和上限值取最小。

int randomLevel() {
  int lv = 1;
  // MAXL = 32, S = 0xFFFF, PS = S * P, P = 1 / 4
  while ((rand() & S) < PS) ++lv;
  return min(MAXL, lv);
}

查询

查询跳表中是否存在键值为 key 的结点。具体实现时，可以设置两个哨兵结点以减少边界条件的讨论。

V& find(const K& key) {
  SkipListNode<K, V>* p = head;
  // 找到该层最后一个键值小于 key 的结点，然后走向下一层
  for (int i = level; i >= 0; --i) {
    while (p->forward[i]->key < key) {
      p = p->forward[i];
    }
  }
  p = p->forward[0];  // 现在是小于，所以还需要再往后走一步
  if (p->key == key) return p->value; // 成功找到结点
  return tail->value; // 结点不存在，返回 INVALID
}

插入

插入结点 (key, value)。插入结点的过程就是先执行一遍查询的过程，中途记录新结点是要插入哪一些结点的后面，最后再执行插入。每一层最后一个键值小于 key 的结点，就是需要进行修改的结点。

void insert(const K &key, const V &value) {
  // 用于记录需要修改的结点
  SkipListNode<K, V> *update[MAXL + 1];

  SkipListNode<K, V> *p = head;
  for (int i = level; i >= 0; --i) {
    while (p->forward[i]->key < key) {
      p = p->forward[i];
    }
    // 第 i 层需要修改的结点为 p
    update[i] = p;
  }
  p = p->forward[0];

  // 若已存在则修改
  if (p->key == key) {
    p->value = value;
    return;
  }

  // 获取新结点的最大层数
  int lv = randomLevel();
  if (lv > level) {
    lv = ++level;
    update[lv] = head;
  }

  // 新建结点
  SkipListNode<K, V> *newNode = new SkipListNode<K, V>(key, value, lv);
  // 在第 0~lv 层插入新结点
  for (int i = lv; i >= 0; --i) {
    p = update[i];
    newNode->forward[i] = p->forward[i];
    p->forward[i] = newNode;
  }
  ++length;
}

删除

删除键值为 key 的结点。删除结点的过程就是先执行一遍查询的过程，中途记录要删的结点是在哪一些结点的后面，最后再执行删除。每一层最后一个键值小于 key 的结点，就是需要进行修改的结点。

bool erase(const K &key) {
  // 用于记录需要修改的结点
  SkipListNode<K, V> *update[MAXL + 1];

  SkipListNode<K, V> *p = head;
  for (int i = level; i >= 0; --i) {
    while (p->forward[i]->key < key) {
      p = p->forward[i];
    }
    // 第 i 层需要修改的结点为 p
    update[i] = p;
  }
  p = p->forward[0];

  if (p->key != key) return false; // 结点不存在

  // 从最底层开始删除
  for (int i = 0; i <= level; ++i) {
    // 如果这层没有 p 删除就完成了
    if (update[i]->forward[i] != p) {
      break;
    }

    update[i]->forward[i] = p->forward[i]; // 断开 p 的连接
  }
  delete p; // 回收空间
  while (level > 0 && head->forward[level] == tail) --level; // 删除结点可能导致最大层数减少
  --length;//维护跳表长度
  return true;
}

~~如果有佬写了数组版可以给我，毕竟大部分人还是喜欢写数组~~

随机访问的优化

访问跳表中第 k 个结点，相当于访问初始有序链表中的第 k 个结点，很明显这个操作的时间复杂度是 O(n) 的，并不足够优秀。

跳表的随机访问优化就是对每一个前向指针，再多维护这个前向指针的长度。假设 A 和 B 都是跳表中的结点，其中 A 为跳表的第 a 个结点，B 为跳表的第 b 个结点 (a < b)，且在跳表的某一层中 A 的前向指针指向B，那么这个前向指针的长度为 b - a。

现在访问跳表中的第 k 个结点，就可以从顶层开始，水平地遍历该层的链表，直到当前结点的位置加上当前结点在该层的前向指针长度大于等于 k，然后移动至下一层。重复这个过程直至到达第一层且无法继续行操作。此时，当前结点就是跳表中第 k 个结点。这样，就可以快速地访问到跳表的第 k 个元素。这个操作的时间复杂度为 O(\log n)。

复杂度分析

空间复杂度

对于一个结点而言，结点的最高层数为 i 的概率为 p^{i-1}(1 - p)。所以，跳表的期望层数为

\sum_{i>=1} ip^{i - 1}(1-p) = \frac{1}{1 - p}

且因为 p 为常数，所以跳表的期望空间复杂度为 O(n)。

在最坏的情况下，每一层有序链表等于初始有序链表，即跳表的最差空间复杂度为 O(n \log n)。

时间复杂度

从后向前分析查找路径，这个过程可以分为从最底层爬到第 L(n) 层和后续操作两个部分。在分析时，假设一个结点的具体信息在它被访问之前是未知的。

假设当前我们处于一个第 i 层的结点 x，我们并不知道 x 的最大层数和 x 左侧结点的最大层数，只知道 x 的最大层数至少为 i。如果 x 的最大层数大于 i，那么下一步应该是向上走，这种情况的概率为 p；如果 x 的最大层数等于 i，那么下一步应该是向左走，这种情况概率为 1-p。

令 C(i) 为在一个无限长度的跳表中向上爬 i 层的期望代价，那么有：

C(0) & = 0 \\ C(i) & = (1-p)(1+C(i)) + p(1+C(i-1)) \end{aligned}

解得 C(i)=\frac{i}{p}。

由此可以得出：在长度为 n 的跳表中，从最底层爬到第 L(n) 层的期望步数存在上界 \frac{L(n) - 1}{p}。

现在只需要分析爬到第 L(n) 层后还要再走多少步。易得，到了第 L(n) 层后，向左走的步数不会超过第 L(n) 层及更高层的结点数总和，而这个总和的期望为 \frac{1}{p}。所以到了第 L(n) 层后向左走的期望步数存在上界 \frac{1}{p}。同理，到了第 L(n) 层后向上走的期望步数存在上界 \frac{1}{p}。

所以，跳表查询的期望查找步数为 \frac{L(n) - 1}{p} + \frac{2}{p}，又因为 L(n)=\log_{\frac{1}{p}}n，所以跳表查询的期望时间复杂度为 O(\log n)。在最坏的情况下，每一层有序链表等于初始有序链表，查找过程相当于对最高层的有序链表进行查询，即跳表查询操作的最差时间复杂度为

插入操作和删除操作就是进行一遍查询的过程，途中记录需要修改的结点，最后完成修改。易得每一层至多只需要修改一个结点，又因为跳表期望层数为 $\log_{\frac{1}{p}}n$，所以插入和修改的期望时间复杂度也为 $O(\log n)$。 #### 例题 [P2286 [HNOI2004] 宠物收养场](https://www.luogu.com.cn/problem/P2286) #### 推荐阅读 & 引用 [浅谈玄学数据结构：跳表](https://www.luogu.com.cn/article/8vwn42j2) [【数据结构】跳表(SkipList) ](https://www.cnblogs.com/ciel717/p/16369335.html) ~~2025.8.26 写到这已经31000字了（逃）~~ # Part 2 块状数据结构要写的东西：分块（可持久化），块状链表，树分块，Sqrt Tree， ## 0x11 分块（块状数组）我们说： > 分块是一种思想 #### 引入考虑给定一个长度为 $n$ 的序列 $\{a_i\}$，需要执行 $n$ 次操作。操作分为两种： 1. 给 $a_l \sim a_r$ 之间的所有数加上 x； 2. 求 $\sum\limits_{i=l}^r a_i$。当 $n \le 5000$ 时，我们考虑 $O(n^2)$ 暴力切掉。当 $n \le 50000$ 时，我们考虑暴力会因为 TLE 被出题人切掉。 > 但我们不能被出题人切掉，无论如何也不能 —— Swedish_Pigeon 于是我们考虑如何优化。如果每次不需要重新计算重复的那些部分就好了。但是区间和问题不同于区间最值，并且还有修改操作，我们不能用ST表解决。这时，我们考虑学习ST表预处理的思想，把一个数列划分成一些块，预处理出它们每一块的和，然后对于每一块去做整体和局部的操作，于是我们发明了分块。 #### 定义与性质分块的基本思想：**通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。** 分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度。本质来讲，分块是一种重新组织数据，整体操作的暴力算法。其虽然相较于线段树和树状数组不够好,但是通用性更好，可以维护很多树状数组和线段树无法维护的信息。块状数组，即把一个数组分为几个块，块内信息整体保存，若查询时遇到两边不完整的块直接暴力查询。一般情况下，块的长度为 $O(\sqrt{n})$。 #### 基本操作要分块，首先要确定块的大小。一般来说，块的大小都为 $\sqrt n$ 。这样大小的块可以保证整个序列被分成 $\sqrt n$ 块。这样查询的时间复杂度可以达到平均。分块算法中需要记录的信息有一个块的和，一个块的左右端点。同时我们需要原数组和存储原数组元素所属块的标记数组。当然，我们需要块的数量和长度。我们将序列按每 $s$ 个元素一块进行分块，并记录每块的区间和 $b_i$。 $$\underbrace{a_1, a_2, \ldots, a_s}_{b_1}, \underbrace{a_{s+1}, \ldots, a_{2s}}_{b_2}, \dots, \underbrace{a_{(s-1) \times s+1}, \dots, a_n}_{b_{\frac{n}{s}}}$$ 最后一个块可能是不完整的（因为 $n$ 很可能不是 $s$ 的倍数），但是这对于我们的讨论来说并没有太大影响。这里给出 $13$ 个数，块长为 $4$ 的例子。 ![](https://cdn.luogu.com.cn/upload/image_hosting/a96ro3is.png) 首先看查询操作： - 若 $l$ 和 $r$ 在同一个块内，直接暴力求和即可，因为块长为 $s$，因此最坏复杂度为 $O(s)$。 - 若 $l$ 和 $r$ 不在同一个块内，则答案由三部分组成： - 以 $l$ 开头的不完整块。 - 中间几个完整块。 - 以 $r$ 结尾的不完整块。对于不完整的块，仍然采用上面暴力计算的方法，对于完整块，则直接利用已经求出的 $b_i$ 求和即可。这种情况下，最坏复杂度为 $O(\dfrac{n}{s}+s)$。譬如，在下面的图中，我们查询 $[2,9]$ 的区间和。 ![](https://cdn.luogu.com.cn/upload/image_hosting/65o8f55d.png) 接下来是修改操作： - 若 $l$ 和 $r$ 在同一个块内，直接暴力修改即可，因为块长为 $s$，因此最坏复杂度为 $O(s)$。 - 若 $l$ 和 $r$ 不在同一个块内，则需要修改三部分： - 以 $l$ 开头的不完整块。 - 中间几个完整块。 - 以 $r$ 结尾的不完整块。对于不完整的块，仍然是暴力修改每个元素的值（别忘了更新区间和 $b_i$），对于完整块，则直接修改 $b_i$ 即可。这种情况下，最坏复杂度和仍然为 $O(\dfrac{n}{s}+s)$。譬如，在下面的图中，我们为 $[4,11]$ 的所有数加上 $7$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/p7mmdhhj.png) 利用均值不等式可知，当 $\dfrac{n}{s}=s$，即 $s=\sqrt n$ 时，单次操作的时间复杂度最优，为 $O(\sqrt n)$。 #### 实现下面给出块状数组对于 P3372 的实现代码，编者码风，略显丑陋，敬请谅解。 ##### 建立块状数组决定好块长，随后计算出块的个数，按算法描述模拟建立各块即可。比起下面代码中写法，笔者更推荐把 len 作为常量放在代码顶部，便于在调试代码和卡常时修改块长。 ```cpp void build() { len = sqrt(n); num = n / len; if(n % len) num++; for(int i = 1;i <= num;i++) { l[i] = (i-1) * len + 1; r[i] = i * len; } for(int i = 1;i <= n;i++) belong[i] = (i-1) / len + 1; r[num] = n; for(int i = 1;i <= n;i++) sum[belong[i]] += a[i]; } //其中 l[i] 和 r[i] 为块的起点和终点，len 为块的大小，belong[i]表示i元素属于哪个块，sum[i]表示该块内元素的和。 ``` ##### 修改操作 ```cpp void udt(int L,int R,int k) { int lblock = belong[L],rblock = belong[R]; if(belong[L] == belong[R]) { for(int i = L;i <= R;i++) a[i] += k; sum[lblock] += (R-L+1) * k; return; } for(int i = L;i <= r[lblock];i++) a[i] += k; sum[lblock] += (r[lblock]-L+1) * k; for(int i = lblock+1;i <= rblock-1;i++) tag[i] += k; for(int i = l[rblock];i <= R;i++) a[i] += k; sum[rblock] += (R-l[rblock]+1)*k; } ``` ##### 查询操作 ```cpp int qry(int L,int R) { int ans = 0; int lblock = belong[L],rblock = belong[R]; if(belong[L] == belong[R]) { for(int i = L;i <= R;i++) ans += a[i]; ans += (R-L+1)*tag[lblock]; return ans; } for(int i = L;i <= r[belong[L]];i++) ans += a[i] + tag[lblock]; for(int i = lblock+1;i <= rblock-1;i++) ans += sum[i] + tag[i]*len; for(int i = l[belong[R]];i <= R;i++) ans += a[i] + tag[rblock]; return ans; } //很好理解 ``` #### 其他问题 ##### P2801 教主的魔法 ###### 题意两种操作： 1. 区间 $[x,y]$ 每个数都加上 $z$； 2. 查询区间 $[x,y]$ 内大于等于 $z$ 的数的个数。 ###### 题解观察到其他数据结构不太好维护，于是考虑分块。分块初始化时对于每个块排序。查询过程中对于两端的碎块暴力比较查询；对于整块可以二分查找该块内满足大于等于 $z$ 的数的个数，随后把答案加起来输出。修改过程中对于碎块来说暴力修改，然后直接把这个块重新排序；对于整块直接在查找的值上加上所有的修改标记即可。这道题是块状数组较为经典的应用，方法不唯一，希望读者可以自行完成。 #### 块状数组的复杂度分析现在我们来分析一次区间操作（修改或查询）的时间复杂度。一次操作涉及的处理部分可以分解为： - 处理两端的散块：最多有 2 个不完整的块，每个块我们最多暴力处理 $S$ 个元素。因此，这部分的时间复杂度为 $O(S)$。 - 处理中间的整块：最多有 $O(num) = O(n / S)$ 个整块。对于每个整块，我们只进行常数次操作（更新懒标记和块和）。因此，这部分的时间复杂度为 $O(n / S)$。因此，单次操作的总时间复杂度为： $T(S) = O(S) + O(\frac{n}{S})

我们的目标是选择一个合适的块大小 S，使得这个最坏情况下的时间复杂度 T(S) 尽可能小。

均值不等式（算术-几何平均不等式）指出，对于任意两个正实数 a 和 b，有：

\frac{a + b}{2} \ge \sqrt{ab}

当且仅当 a = b 时，等号成立。

我们将单次操作的时间复杂度函数 T(S) 的两个部分视为两个正数 a 和 b：令 a = S, b = \frac{n}{S}。

根据均值不等式：

\frac{S + \frac{n}{S}}{2} \ge \sqrt{S \cdot \frac{n}{S}} = \sqrt{n}

将不等式两边同时乘以 2，得到：

S + \frac{n}{S} \ge 2\sqrt{n}

这个不等式的意义在于：函数 f(S) = S + \frac{n}{S} 的最小值是 2\sqrt{n}，并且当且仅当 S = \frac{n}{S}，即 S = \sqrt{n} 时取得这个最小值。

其他题目的块状数组复杂度也可以同理计算。

例题

P3372 【模板】线段树 1

P2801 教主的魔法

P4145 上帝造题的七分钟 2 / 花神游历各国

P5356 [Ynoi Easy Round 2017] 由乃打扑克

不要见到 Ynoi 就认为它是难到离谱的，切它就完了 - Swedish_Pigeon

推荐大家做完P2801就可以试试这道 Ynoi，思路是差不多的，可以尝试加入一些优化，再卡卡常。

0x12 块状链表

0x13 树分块

0x14 可持久化块状数据结构

0x15 Sqrt Tree

写完的东西：

Part 3 树状数据结构（一）

要写的东西：并查集，Trie（压位 Trie）,堆（配对堆，左偏树），线段树（zkw，合并分裂，扫描线，树剖，可持久化，李超，猫树，吉司机），树状数组，平衡树（FHQ-Treap,替罪羊树，Splay，Treap，红黑树，AVL树，WBLT,SBT，），可持久化数据结构，划分树，笛卡尔树，Kruskal 重构树，树套树（类型很多，写到再说），K-D Tree，Link-Cut-Tree（全局平衡二叉树，ETT，Top Tree）,析合树，PQ 树，vEB树。B树、B+树、B*树，融合树——Fusion Tree

写完的东西：

0x21 并查集

引入

考虑一个问题：我们有 n 个数，维护一个集合。

查询一个数属于哪个集合。
合并两个数的所在集合。

发现别的什么数据结构都没法维护，于是我们考虑并查集。

定义与性质

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的结点表示对应集合中的元素。上图展示的就是一个并查集，包含两个集合：\{1,2,3,4,5\}，\{6,7,8\}。

并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。值得注意的是，虽然并查集可以以较优秀的复杂度实现合并与查询，但是并查集无法以较低复杂度实现集合的分离。

基本操作

顾名思义，并查集支持两种操作：

合并（Union）：合并两个元素所属集合（合并对应的树）
查询（Find）：查询某个元素所属集合（查询对应的树的根结点），这可以用于判断两个元素是否属于同一集合。

实现

初始化

初始时，每个元素都位于一个单独的集合，表示为一棵只有根结点的树。方便起见，我们将根结点的父亲设为自己。

int fa[SIZE];
for(int i = 1; i <= n; ++i) fa[i] = i;

查询

我们需要沿着树向上移动，直至找到根结点。

int find(int x)
{
    if(fa[x] == x) return x; // 已经是根结点 
    else return find(fa[x]); // 继续找 
}

但是我们观察到如果集合被组织成一条链状，且每次查询链最底部的一个元素，那么复杂度会退化到 O(nm)，非常糟糕。因此，我们需要采用一些优化。

合并

要合并两棵树，我们只需要将一棵树的根结点连到另一棵树的根结点。

void merge(int x,int y)
{
    int tx = find(x)，ty = find(y);
    if(tx == ty) return;
    fa[tx] = ty;
}

优化1：路径压缩-查询优化

查询过程中经过的每个元素都属于该集合，我们可以将其直接连到根结点以加快后续查询。

int find(int x)
{
    if(fa[x] == x) return x; // 已经是根结点 
    else return fa[x] = find(fa[x]); // 继续找 
}

优化2：按秩合并-合并优化

这里的“秩”可以指树的高度或树的结点数，不影响时间复杂度。按秩合并的主要思想是：将小的结构合并到大的结构里。这样，合并操作能劣化的结点也要少一些。

单独使用按秩合并优化也能将均摊时间复杂度优化到 O(\log n)。理论上按结点数合并慢于按高度合并。这是按高度合并的实现：

void merge(int x,int y)
{
    int tx = find(x), ty = find(y); // 查询各自的代表元素
    if(tx == ty) return; // 如果已经在同一个集合，跳过
    if(siz[ty] < siz[tx]) swap(tx, ty); // 改变合并顺序
    if(siz[tx] == siz[ty]) siz[ty] = siz[tx]+1; // 计算新的秩：如果两个集合的秩相等，那么秩加一
    // 否则秩不变 
    fa[tx] = ty;
}

复杂度分析

这里我们搬运 OI-Wiki 的证明过程

定义

阿克曼函数

这里，先给出 \alpha(n) 的定义。为了给出这个定义，先给出 A_k(j) 的定义。

定义 A_k(j) 为：

\begin{aligned} &j+1& &k=0&\\ &A_{k-1}^{j+1}(j)& &k\geq1& \end{aligned} \right.

即阿克曼函数。

这里，f^i(x) 表示将 f 连续应用在 x 上 i 次，即 f^0(x)=x，f^i(x)=f(f^{i-1}(x))。

再定义 \alpha(n) 为使得 A_{\alpha(n)}(1)\geq n 的最小整数值。注意，我们之前将它描述为 A_{\alpha(n)}(\alpha(n))\geq n，反正他们的增长速度都很慢，值都不超过 4。

基础定义

每个结点都有一个 rank。这里的 rank 不是结点个数，而是深度。结点的初始 rank 为 0，在合并的时候，如果两个结点的 rank 不同，则将 rank 小的结点合并到 rank 大的结点上，并且不更新大结点的 rank 值。否则，随机将某个结点合并到另外一个结点上，将根结点的 rank 值 +1。这里根结点的 rank 给出了该树的高度。记 x 的 rank 为

为了定义势函数，需要预先定义一个辅助函数 $level(x)$。其中，$level(x)=\max(k:rnk(fa(x))\geq A_k(rnk(x)))$。当 $rnk(x)\geq1$ 的时候，再定义一个辅助函数 $iter(x)=\max(i:rnk(fa(x))\geq A_{level(x)}^i(rnk(x))$。这些函数定义的 $x$ 都满足 $rnk(x)>0$ 且 $x$ 不是某个树的根。上面那些定义可能让你有点头晕。再理一下，对于一个 $x$ 和 $fa(x)$，如果 $rnk(x)>0$，总是可以找到一对 $i,k$ 令 $rnk(fa(x))\geq A_k^i(rnk(x))$，而 $level(x)=\max(k)$，在这个前提下，$iter(x)=\max(i)$。$level$ 描述了 $A$ 的最大迭代级数，而 $iter$ 描述了在最大迭代级数时的最大迭代次数。对于这两个函数， $level(x)$ 总是随着操作的进行而增加或不变，如果 $level(x)$ 不增加， $iter(x)$ 也只会增加或不变。并且，它们总是满足以下两个不等式： $$0\leq level(x)<\alpha(n)$$ $$1\leq iter(x)\leq rnk(x)$$ 考虑 $level(x)$、$iter(x)$ 和 $A_k^j$ 的定义，这些很容易被证明出来，就留给读者用于熟悉定义了。定义势能函数 $\Phi(S)=\sum\limits_{x\in S}\Phi(x)$，其中 $S$ 表示一整个并查集，而 $x$ 为并查集中的一个结点。定义 $\Phi(x)$ 为： $$ \Phi(x)= \begin{cases} \alpha(n)\times \mathit{rnk}(x)& \mathit{rnk}(x)=0\ \text{或}\ x\ \text{为某棵树的根结点}\\ (\alpha(n)-\mathit{level}(x))\times \mathit{rnk}(x)-iter(x)& \text{otherwise} \end{cases} $$ 然后就是通过操作引起的势能变化来证明摊还时间复杂度为 $O(\alpha(n))$ 啦。注意，这里我们讨论的 $union(x,y)$ 操作保证了 $x$ 和 $y$ 都是某个树的根，因此不需要额外执行 $find(x)$ 和 $find(y)$。可以发现，势能总是个非负数。另，在开始的时候，并查集的势能为 $0$。 ##### 证明 ###### union(x,y) 操作其花费的时间为 $O(1)$，因此我们考虑其引起的势能的变化。这里，我们假设 $rnk(x)\leq rnk(y)$，即 $x$ 被接到 $y$ 上。这样，势能增加的结点仅有 $x$（从树根变成非树根），$y$（秩可能增加）和操作前 $y$ 的子结点（父结点的秩可能增加）。我们先证明操作前 $y$ 的子结点 $c$ 的势能不可能增加，并且如果减少了，至少减少 $1$。设操作前 $c$ 的势能为 $\Phi(c)$，操作后为 $\Phi(c')$，这里 $c$ 可以是任意一个 $rnk(c)>0$ 的非根结点，操作可以是任意操作，包括下面的 find 操作。我们分三种情况讨论。 1. $iter(c)$ 和 $level(c)$ 并未增加。显然有 $\Phi(c)=\Phi(c')$。 2. $iter(c)$ 增加了，$level(c)$ 并未增加。这里 $iter(c)$ 至少增加一，即 $\Phi(c')\leq \Phi(c)-1$，势能函数减少了，并且至少减少 $1$。 3. $level(c)$ 增加了，$iter(c)$ 可能减少。但是由于 $0<iter(c)\leq rnk(c)$，$iter(c)$ 最多减少 $rnk(c)-1$，而 $level(c)$ 至少增加 $1$。由定义 $\Phi(c)=(\alpha(n)-level(c))\times rnk(c)-iter(c)$，可得 $\Phi(c')\leq\Phi(c)-1$。 4. 其他情况。由于 $rnk(c)$ 不变，$rnk(fa(c))$ 不减，所以不存在。所以，势能增加的结点仅可能是 $x$ 或 $y$。而 $x$ 从树根变成了非树根，如果 $rnk(x)=0$，则一直有 $\Phi(x)=\Phi(x')=0$。否则，一定有 $\alpha(x)\times rnk(x)\geq(\alpha(n)-level(x))\times rnk(x)-iter(x)$。即，$\Phi(x')\leq \Phi(x)$。因此，唯一势能可能增加的点就是 $y$。而 $y$ 的势能最多增加 $\alpha(n)$。因此，可得 $union$ 操作均摊后的时间复杂度为 $O(\alpha(n))$。 ###### find(a) 操作如果查找路径包含 $O(s)$ 个结点，显然其查找的时间复杂度是 $O(s)$。如果由于查找操作，没有结点的势能增加，且至少有 $s-\alpha(n)$ 个结点的势能至少减少 $1$，就可以证明 $find(a)$ 操作的时间复杂度为 $O(\alpha(n))$。为了避免混淆，这里用 $a$ 作为参数，而出现的 $x$ 都是泛指某一个并查集内的结点。首先证明没有结点的势能增加。很显然，我们在上面证明过所有非根结点的势能不增，而根结点的 $rnk$ 没有改变，所以没有结点的势能增加。接下来证明至少有 $s-\alpha(n)$ 个结点的势能至少减少 $1$。我们上面证明过了，如果 $level(x)$ 或者 $iter(x)$ 有改变的话，它们的势能至少减少 $1$。所以，只需要证明至少有 $s-\alpha(n)$ 个结点的 $level(x)$ 或者 $iter(x)$ 有改变即可。回忆一下非根结点势能的定义，$\Phi(x)=(\alpha(n)-level(x))\times rnk(x)-iter(x)$，而 $level(x)$ 和 $iter(x)$ 是使 $rnk(fa(x))\geq A_{level(x)}^{iter(x)}(rnk(x))$ 的最大数。所以，如果 $root_x$ 代表 $x$ 所处的树的根结点，只需要证明 $rnk(root_x)\geq A_{level(x)}^{iter(x)+1}(rnk(x))$ 就好了。根据 $A_k^i$ 的定义，$A_{level(x)}^{iter(x)+1}(rnk(x))=A_{level(x)}(A_{level(x)}^{iter(x)}(rnk(x)))$。注意，我们可能会用 $k(x)$ 代表 $level(x)$，$i(x)$ 代表 $iter(x)$ 以避免式子过于冗长。这里，就是 $rnk(root_x)\geq A_{k(x)}(A_{k(x)}^{i(x)}(x))$。当你看到这的时候，可能会有一种「这啥玩意」的感觉。这意味着你可能需要多看几遍，或者跳过一些内容以后再看。这里，我们需要一个外接的 $A_{k(x)}$，意味着我们可能需要再找一个点 $y$。令 $y$ 是搜索路径上在 $x$ 之后的满足 $k(y)=k(x)$ 的点，这里「搜索路径之后」相当于「是 $x$ 的祖先」。显然，不是每一个 $x$ 都有这样一个 $y$。很容易证明，没有这样的 $y$ 的 $x$ 不超过 $\alpha(n)+2$ 个。因为只有每个 $k$ 的最后一个 $x$ 和 $a$ 以及 $root_a$ 没有这样的 $y$。我们再强调一遍 $fa(x)$ 指的是路径压缩之前 $x$ 的父结点，路径压缩之后 $x$ 的父结点一律用 $root_x$ 表示。对于每个存在 $y$ 的 $x$，总是有 $rnk(y)\geq rnk(fa(x))$。同时，我们有 $rnk(fa(x))\geq A_{k(x)}^{i(x)}(rnk(x))$。由于 $k(x)=k(y)$，我们用 $k$ 来统称，即，$rnk(fa(x))\geq A_k^{i(x)}(rnk(x))$。我们需要造一个 $A_k$ 出来，所以我们可以不关注 $iter(y)$ 的值，直接使用弱化版的 $rnk(fa(y))\geq A_k(rnk(y))$。如果我们将不等式组合起来，神奇的事情就发生了。我们发现，$rnk(fa(y))\geq A_k^{i(x)+1}(rnk(x))$。也就是说，为了从 $rnk(x)$ 迭代到 $rnk(fa(y))$，至少可以迭代 $A_k$ 不少于 $i(x)+1$ 次而不超过 $rnk(fa(y))$。显然，有 $rnk(root_y)\geq rnk(fa(y))$，且 $rnk(x)$ 在路径压缩时不变。因此，我们可以得到 $rnk(root_x)\geq A_k^{i(x)+1}(rnk(x))$，也就是说 $iter(x)$ 的值至少增加 1，如果 $rnk(x)$ 没有增加，一定是 $level(x)$ 增加了。所以，$\Phi(x)$ 至少减少了 $1$。由于这样的 $x$ 结点至少有 $s-\alpha(n)-2$ 个，所以最后 $\Phi(S)$ 至少减少了 $s-\alpha(n)-2$，均摊后的时间复杂度即为 $O(\alpha(n)+2)=O(\alpha(n))$。 > 值得注意的是，对于 $n \le 2^{2^{10^{19729}}}$，都满足 $\alpha(n) < 5$。空间复杂度显然为 $O(n)$。 #### 习题 [P3367 【模板】并查集](https://www.luogu.com.cn/problem/P3367) [并查集模板题](https://www.luogu.com.cn/training/3065) #### 参考资料 & 引用 [并查集算法模拟](https://visualgo.net/zh/ufds?slide=1) [并查集应用](https://oi-wiki.org/topic/dsu-app/) ## 0x22 堆堆是一棵树，其每个结点都有一个键值，且每个结点的键值都大于等于/小于等于其父亲的键值。每个结点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。STL 中的 `priority_queue` 其实就是一个大根堆。堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。一些功能强大的堆还能（高效地）支持 merge，可持久化（也就是对任意历史版本进行查询或者操作，产生新的版本）等操作。在该章节中，我们会介绍主流的一些堆和一些几乎不会在算法竞赛中使用的高科技。 ![](https://cdn.luogu.com.cn/upload/image_hosting/y4f583bs.png) 值得注意的是：复杂度可能是均摊的，一些实现方式常数可能较大。前五种具体的复杂度可以参见OI-Wiki，第六种的复杂度均非均摊复杂度。 ### （一）二叉堆 #### 定义与基本性质（Binary Heap）二叉堆是最简单、常用的堆，是一棵符合堆的性质的完全二叉树。它可以实现 $O(\log n)$ 地插入或删除某个值，并且 $O(1)$ 地查询最大（或最小）值。由堆性质，树根存的是最大值。 ![](https://cdn.luogu.com.cn/upload/image_hosting/84exwj0k.png) 作为一棵完全二叉树，二叉堆完全可以用一个`1-index`的数组来存储，对于结点`p`，`p*2`即为左儿子，`p*2+1`即为右结点。同时，用`size`记录当前二叉堆中结点的个数。现在我们考虑如何保证二叉堆的性质不被破坏。实际上，对于一个破坏堆性质的结点，我们可以使其上浮或下沉，因为最差也不过是上浮到顶或是下沉到底，所以只需要 $O(\log n)$ 的时间就可以使其不再破坏性质。稍后我们会看到，插入和删除都只需要上浮/下沉一个结点。 #### 基本操作 ##### 上浮很简单，不断与父结点比较，如果比父结点大（以大根堆为例，下同）就与之交换，直到不大于父结点或成为根结点为止。 ##### 下沉类似地，不断与较大的子结点比较，如果比它小就与之交换，直到不小于任何子结点或成为叶子结点为止。之所以要与较大的子结点比较，是为了保证交换上来的结点比两个子结点都大。 ##### 插入插入操作是指向二叉堆中插入一个元素，要保证插入后也是一棵完全二叉树。最简单的方法就是，最下一层最右边的叶子之后插入。如果最下一层已满，就新增一层。如果插入之后不满足堆性质，则上浮，直到符合堆性质为止。可以证明，插入之后向上调整后，没有其他结点会不满足堆性质。 ##### 删除删除操作指删除堆中最大的元素，即删除根结点。但是如果直接删除，则变成了两个堆，难以处理。所以不妨考虑插入操作的逆过程，设法将根结点移到最后一个结点，然后直接删掉。然而实际上不好做，我们通常采用的方法是，把根结点和最后一个结点直接交换。于是直接删掉在最后一个结点处的根结点，但是新的根结点可能不满足堆性质，此时下沉即可。可以证明，删除并向下调整后，没有其他结点不满足堆性质。 ##### 查询直接返回根结点即可。 ##### 建堆可以从一个数组 $O(n)$ 地建立堆，只需复制过来然后从底部到顶部依次下沉即可。实际上因为叶子结点不需要下沉，所以可以从 $\frac{n}{2}$ 处开始遍历。设总的往下走的层数为 $S$ ，则： ![](https://cdn.luogu.com.cn/upload/image_hosting/8kht331v.png) 因此复杂度是线性的。手写二叉堆会比 `priority_queue` 略快，可以尝试使用手写二叉堆卡常。 #### 实现 ```cpp namespace heap { #define maxheap // 如果需要小根堆，把这行注释掉即可 #ifdef maxheap #define op > #else #define op < #endif const int MAXN = 1000005; int heap[MAXN], size; void swim(int n) { for (int i = n; i > 1 && heap[i] op heap[i / 2]; i /= 2) swap(heap[i], heap[i / 2]); } int son(int n){return n * 2 + (n * 2 + 1 <= size && heap[n * 2 + 1] op heap[n * 2]);} void sink(int n) { for (int i = n, t = son(i); t <= size && heap[t] op heap[i]; i = t, t = son(i)) swap(heap[i], heap[t]); } void push(int x){heap[++size] = x; swim(size);} void pop(){swap(heap[1], heap[size--]); sink(1);} int top(){return heap[1];} void build(int A[], int n) { memcpy(heap + 1, A, sizeof(int) * n); size = n; for (int i = n / 2; i > 0; --i) sink(i); } } // namespace heap ``` #### 应用我们需要维护一个序列，支持两种操作： 1. 向序列中插入一个元素 2. 输出并删除当前序列的中位数（若序列长度为偶数，则输出较小的中位数）这个问题可以被进一步抽象成：动态维护一个序列上第 $k$ 大的数，$k$ 值可能会发生变化。对于此类问题，我们可以使用对顶堆这一技巧予以解决（可以避免写权值线段树或 BST 带来的繁琐）。对顶堆由一个大根堆与一个小根堆组成，小根堆维护大值即前 $k$ 大的值（包含第 $k$ 个），大根堆维护小值即比第 $k$ 大数小的其他数。这两个堆构成的数据结构支持以下操作： - 维护：当小根堆的大小小于 $k$ 时，不断将大根堆堆顶元素取出并插入小根堆，直到小根堆的大小等于 $k$；当小根堆的大小大于 $k$ 时，不断将小根堆堆顶元素取出并插入大根堆，直到小根堆的大小等于 $k$； - 插入元素：若插入的元素大于等于小根堆堆顶元素，则将其插入小根堆，否则将其插入大根堆，然后维护对顶堆； - 查询第 $k$ 大元素：小根堆堆顶元素即为所求； - 删除第 $k$ 大元素：删除小根堆堆顶元素，然后维护对顶堆； - $k$ 值 $+1/-1$：根据新的 $k$ 值直接维护对顶堆。显然，查询第 k 大元素的时间复杂度是 $O(1)$ 的。由于插入、删除或调整 $k$ 值后，小根堆的大小与期望的 $k$ 值最多相差 $1$，故每次维护最多只需对大根堆与小根堆中的元素进行一次调整，因此，这些操作的时间复杂度都是 $O(\log n)$ 的。 #### 推荐阅读 & 引用 [算法学习笔记(47): 二叉堆](https://zhuanlan.zhihu.com/p/187618450) [二叉堆结构和操作详解](https://www.cnblogs.com/ofnoname/p/18630871) [二叉堆](https://algo.codefather.cn/data/tree/binary-heap) ### （二）配对堆（Pairing Heap） #### 定义与性质配对堆是一个支持插入，查询/删除最小值，合并，修改元素等操作的数据结构，是一种可并堆。有速度快和结构简单的优势，但由于其为基于势能分析的均摊复杂度，无法可持久化。配对堆是一棵满足堆性质的带权多叉树（如下图），即每个结点的权值都小于或等于他的所有儿子（以小根堆为例，下同）。 ![](https://cdn.luogu.com.cn/upload/image_hosting/a0kedd1o.png) 通常我们使用儿子 - 兄弟表示法储存一个配对堆（如下图），一个结点的所有儿子结点形成一个单向链表。每个结点储存第一个儿子的指针，即链表的头结点；和他的右兄弟的指针。这种方式便于实现配对堆，也将方便复杂度分析。 ![](https://cdn.luogu.com.cn/upload/image_hosting/k19ceqwx.png) 从定义可以发现，和其他常见的堆结构相比，配对堆不维护任何额外的树大小，深度，排名等信息（二叉堆也不维护额外信息，但它是通过维持一个严格的完全二叉树结构来保证操作的复杂度），且任何一个满足堆性质的树都是一个合法的配对堆，这样简单又高度灵活的数据结构奠定了配对堆在实践中优秀效率的基础；作为对比，斐波那契堆糟糕的常数就是因为它需要维护很多额外的信息。配对堆通过一套精心设计的操作顺序来保证它的总复杂度，原论文将其称为「一种自调整的堆（Self Adjusting Heap）」。在这方面和 Splay 树（在原论文中被称作「Self Adjusting Binary Tree」）颇有相似之处。 #### 基本操作和实现 ##### 查询最小值从配对堆的定义可看出，配对堆的根结点的权值一定最小，直接返回根结点即可。 ##### 合并合并两个配对堆的操作很简单，首先令两个根结点较小的一个为新的根结点，然后将较大的根结点作为它的儿子插入进去。（见下图）需要注意的是，一个结点的儿子链表是按插入时间排序的，即最右边的结点最早成为父结点的儿子，最左边的结点最近成为父结点的儿子。 ![](https://cdn.luogu.com.cn/upload/image_hosting/5ynletxo.png) ```cpp Node* meld(Node* x, Node* y) { // 若有一个为空则直接返回另一个 if (x == nullptr) return y; if (y == nullptr) return x; if (x->v > y->v) std::swap(x, y); // swap后x为权值小的堆，y为权值大的堆 // 将y设为x的儿子 y->sibling = x->child; x->child = y; return x; // 新的根结点为 x } ``` ##### 插入合并都有了，插入就直接把新元素视为一个新的配对堆和原堆合并就行了。 ##### 删除最小值首先要提及的一点是，上文的几个操作都十分偷懒，完全没有对数据结构进行维护，所以我们需要小心设计删除最小值的操作，来保证总复杂度不出问题。根结点即为最小值，所以要删除的是根结点。考虑拿掉根结点之后会发生什么：根结点原来的所有儿子构成了一片森林；而配对堆应当是一棵树，所以我们需要通过某种顺序把这些儿子全部合并起来。一个很自然的想法是使用合并函数把儿子们从左到右挨个并在一起，这样做的话正确性是显然的，但是会导致单次操作复杂度退化到 $O(n)$。为了保证总的均摊复杂度，需要使用一个「两步走」的合并方法： 1. 把儿子们两两配成一对，用合并操作把被配成同一对的两个儿子合并到一起（见下图 1）， 2. 将新产生的堆从右往左（即老的儿子到新的儿子的方向）挨个合并在一起（见下图 2）。 ![](https://cdn.luogu.com.cn/upload/image_hosting/67wlfeqr.png) 先实现一个辅助函数 `merges`，作用是合并一个结点的所有兄弟。 ```cpp Node* merges(Node* x) { if (x == nullptr || x->sibling == nullptr) return x; // 如果该树为空或他没有下一个兄弟，就不需要合并了，return。 Node* y = x->sibling; // y 为 x 的下一个兄弟 Node* c = y->sibling; // c 是再下一个兄弟 x->sibling = y->sibling = nullptr; // 拆散 return meld(merges(c), meld(x, y)); // 核心部分 } ``` 最后一句话是该函数的核心，这句话分三部分： 1. `meld(x,y)`「配对」了 $x$ 和 $y$。 2. `merges(c)` 递归合并 $c$ 和他的兄弟们。 3. 将上面 $2$ 个操作产生的 $2$ 个新树合并。需要注意到的是，上文提到了第二步时的合并方向是有要求的（从右往左合并），该递归函数的实现已保证了这个顺序，如果读者需要自行实现迭代版本的话请务必注意保证该顺序，否则复杂度将失去保证。有了 `merges` 函数，`delete-min` 操作就显然了。 ```cpp Node* delete_min(Node* x) { Node* t = merges(x->child); delete x; // 如果需要内存回收 return t; } ``` ##### 减小一个元素的值要实现这个操作，需要给结点添加一个「父」指针，当结点有左兄弟时，其指向左兄弟而非实际的父结点；否则，指向其父结点。首先结点的定义修改为： ```cpp struct Node { LL v; int id; Node *child, *sibling; Node *father; // 新增：父指针，若该结点为根结点则指向空结点 nullptr }; ``` `meld` 操作修改为： ```cpp Node* meld(Node* x, Node* y) { if (x == nullptr) return y; if (y == nullptr) return x; if (x->v > y->v) std::swap(x, y); if (x->child != nullptr) { // 新增：维护父指针 x->child->father = y; } y->sibling = x->child; y->father = x; // 新增：维护父指针 x->child = y; return x; } ``` `merges` 操作修改为： ```cpp Node *merges(Node *x) { if (x == nullptr) return nullptr; x->father = nullptr; // 新增：维护父指针 if (x->sibling == nullptr) return x; Node *y = x->sibling, *c = y->sibling; y->father = nullptr; // 新增：维护父指针 x->sibling = y->sibling = nullptr; return meld(merges(c), meld(x, y)); } ``` 现在我们来考虑如何实现 `decrease-key` 操作。首先我们发现，当我们减少结点 $x$ 的权值之后，以 $x$ 为根的子树仍然满足配对堆性质，但 $x$ 的父亲和 $x$ 之间可能不再满足堆性质。因此我们把整棵以 $x$ 为根的子树剖出来，现在两棵树都符合配对堆性质了，然后把他们合并起来，就完成了全部操作。 ```cpp // root为堆的根，x为要操作的结点，v为新的权值，调用时需保证 v <= x->v // 返回值为新的根结点 Node *decrease_key(Node *root, Node *x, LL v) { x->v = v; // 更新权值 if (x == root) return x; // 如果 x 为根，则直接返回 // 把x从fa的子结点中剖出去，这里要分x的位置讨论一下。 if (x->father->child == x) { x->father->child = x->sibling; } else { x->father->sibling = x->sibling; } if (x->sibling != nullptr) { x->sibling->father = x->father; } x->sibling = nullptr; x->father = nullptr; return meld(root, x); // 重新合并 x 和根结点 } ``` #### 复杂度分析配对堆结构与实现简单，但时间复杂度分析并不容易。 [原论文](https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf)仅将复杂度分析到 `meld` 和 `delete-min` 操作均为均摊 $O(\log n)$，但提出猜想认为其各操作都有和斐波那契堆相同的复杂度。遗憾的是，后续发现，不维护额外信息的配对堆，在特定的操作序列下，`decrease-key` 操作的均摊复杂度下界至少为

\Omega (\log \log n)2。目前对复杂度上界比较好的估计有，Iacono 的 O(1) `meld`，O(\log n) `decrease-key`；Pettie 的 O(2^{2 \sqrt{\log \log n}})$ meld 和 decrease-key。需要注意的是，前述复杂度均为均摊复杂度，因此不能对各结果分别取最小值。

（三）左偏树（Leftist Tree）

左偏树与配对堆一样，是一种可并堆，具有堆的性质，并且可以快速合并。

定义与性质

对于一棵二叉树，我们定义 外结点 为子结点数小于两个的结点，即左儿子或右儿子是空结点的结点。一个结点 x 的距离 dist_{x} 定义为其子树中与结点 x 最近的外结点到 x 的距离。特别地，定义空结点的距离为 −1 。

左偏树的基本性质

左偏树具有 堆性质 ，即若其满足小根堆的性质，则对于每个结点 x，有 v_x \le v_{lc},v_x \le v_{rc} 。

左偏树具有左偏性质，即对于每个结点 x，有 dist_{lc} \le dist_{rc} 。

需要注意的是，\mathrm{dist} 不是深度，左偏树的深度没有保证，一条向左的链也符合左偏树的定义。

左偏树的基本结论

结点 x 的距离 dist_x = dist_{rc} + 1。
距离为 n 的左偏树至少有 2 ^ {n+1} - 1 个结点。此时该左偏树的形态是一课满二叉树。
有 n 的结点的左偏树的根节点的距离是 O(\log_2 n) 的。
基本操作

合并

左偏树最基本的操作是合并操作。

定义 merge(x,y) 为合并两棵分别以 x,y 为根结点的左偏树，其返回值为合并之后的根节点。

首先不考虑左偏性质，我们描述一下合并两个具有堆性质的树的过程。假设我们要合并的是小根堆。

若 v_x \le v_y，以 x 作为合并后的根节点；否则以 y 作为合并后的根节点。为避免讨论，若有 v_x > v_y，交换 x,y 。
将 y 与 x 的其中一个儿子合并，用合并后的根结点代替与 y 合并的儿子的位置，并返回 x。
重复以上操作，如果 x 和 y 中有一个为空结点，返回 x + y。

令 h 为树高， h_x + h_y 每次都减少了 1 ，上述过程的时间复杂度是 O(h) 的，当合并的树退化为一条链时，这样做的复杂度是 O(n) 的。要使时间复杂度更优，就要使树合并得更平衡。我们有两种方式：

每次随机选择 x 的左右儿子进行合并。
左偏树。

由于左偏树中左儿子的距离大于右儿子的距离，我们每次将 y 与 x 的右儿子合并。由于左偏树的树高是 O(\log_2 n) 的，所以单次合并的时间复杂度也是 O(\log_2 n) 的。

但是，两棵左偏树按照上述方法合并后，可能不再保持左偏树的左偏性质。在每次合并完之后，判断对结点 x 是否有 dist_{lc} \ge dist_{rc} ，若没有则交换 lc,rc ，并维护 x 的距离 dist_x = dist_{rc} + 1 ，即可维护左偏树的左偏性质。

由于合并后的树既满足堆性质又满足左偏性质，所以合并后的树仍然是左偏树。

int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(v[y]<v[x])swap(x,y);
    rc[x]=merge(rc[x],y);
    if(dist[lc[x]]<dist[rc[x]])swap(lc[x],rc[x]);
    dist[x]=dist[rc[x]]+1;
    return x;
}

插入给定值

新建一个值等于插入值的结点，将该节点与左偏树合并即可。时间复杂度 O(\log_2 n)。

求最小值

由于左偏树的堆性质，左偏树上的最小值为其根节点的值。

删除最小值

价于删除左偏树的根节点。合并根节点的左右儿子即可。记得维护已删除结点的信息。

给定一个结点，求其所在左偏树的根节点

我们可以记录每个结点的父亲结点 fa_i ，然后暴力跳父亲结点。

int findrt(int x)
{
    if(fa[x])return findrt(fa[x]);
    return x;
}

注意，虽然左偏树的距离是 O(\log_2 n)，但是左偏树的深度最大可以是 O(n) 的，种做法的复杂度也是 O(n) 的。上面的代码让你想到了什么？并查集。我们同样可以用路径压缩的方式，求一个结点所在左偏树的根节点。

int find(int x)
{
  if(rt == x) return x;
  return rt[x]=find(rt[x]);
}

使用这种写法，需要维护 rt[x] 的值。

在合并两个结点 x,y 时，令 rt[x]=rt[y]=merge(x,y) 。

在删除左偏树中的最小值时，令 rt[lc[x]]=rt[rc[x]]=rt[x]=merge(lc[x],rc[x]) ，因为 x 是之前左偏树的根节点，在路径压缩时可能有 rt 的值等于 x ，所以 rt[x] 也要指向删除后的根节点。

由于 x 已经被作为中间量使用得不成样子，如果之后还要用到结点 x ，需要新建一个值相同的结点。

路径压缩后，可以在 O(\log_2 n) 的优秀时间复杂度内找到一个点所在左偏树的根节点。

整个堆加上/减去一个值、乘上一个正数

其实可以打标记且不改变相对大小的操作都可以。

在根打上标记，删除根/合并堆（访问儿子）时下传标记即可。

实现

下面是模板题 P3377 的左偏树实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
int n,m,op,x,y;
int lc[maxn],rc[maxn],dist[maxn],rt[maxn];
bool tf[maxn];
struct node
{
    int id,v;
    bool operator<(node x)const{return v==x.v?id<x.id:v<x.v;}
}v[maxn];
int find(int x){return rt[x]==x?x:rt[x]=find(rt[x]);}
int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(v[y]<v[x])swap(x,y);
    rc[x]=merge(rc[x],y);
    if(dist[lc[x]]<dist[rc[x]])swap(lc[x],rc[x]);
    dist[x]=dist[rc[x]]+1;
    return x;
}
int main()
{
    dist[0]=-1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&v[i].v),rt[i]=i,v[i].id=i;
    while(m--)
    {
        scanf("%d%d",&op,&x);
        if(op==1)
        {
            scanf("%d",&y);
            if(tf[x]||tf[y])continue;
            x=find(x);y=find(y);
            if(x!=y)rt[x]=rt[y]=merge(x,y);
        }
        if(op==2)
        {
            if(tf[x]){printf("-1\n");continue;}
            x=find(x);
            printf("%d\n",v[x].v);
            tf[x]=true;
            rt[lc[x]]=rt[rc[x]]=rt[x]=merge(lc[x],rc[x]);
            lc[x]=rc[x]=dist[x]=0;
        }
    }
    return 0;
}

复杂度证明

先考虑 merge 的过程，每次都会使 x 或 y 向下一层，也就是说最极端的情况，就是一直选择左偏树的右节点（\mathrm{dist} 最小的节点）向下一层，此时

再考虑 `pushup` 的过程，我们令当前 `pushup` 的这个节点为 $x$，其父亲为 $y$，一个节点的「初始 $\mathrm{dist}$」为它在 `pushup` 前的 $\mathrm{dist}$。从被删除节点的父亲开始递归，有两种情况： $x$ 是 $y$ 的右儿子，此时 y 的初始 $\mathrm{dist}$ 为 $x$ 的初始 $\mathrm{dist}$ 加一。$x$ 是 $y$ 的左儿子，由于节点的 $\mathrm{dist}$ 最多减一，因此只有 $y$ 的左右儿子初始 $\mathrm{dist}$ 相等时（此时左儿子 $\mathrm{dist}$ 减一会导致左右儿子互换）才会继续递归下去，因此 y 的初始 $\mathrm{dist}$ 仍然是 $x$ 的初始 $\mathrm{dist}$ 加一。所以，我们得到，每递归一层 $x$ 的初始 $\mathrm{dist}$ 就会加一，因此最多递归 $O(\log n)$ 层。 #### 推荐阅读 & 引用 [题解 P3377 【【模板】左偏树（可并堆）】](https://www.luogu.com.cn/article/j1mqfet0) ### （四）二项堆（Binomial Heap） #### 定义与性质 ##### 二项树二项堆是二项树的集合。在了解二项堆之前，先对二项树进行介绍。二项树是一种递归定义的有序树。它的递归定义如下： 1. 二项树 $B_0$ 只有一个结点； 2. 二项树 $B_k$ 由两棵二项树 $B_{k-1}$ 组成的，其中一棵树是另一棵树根的最左孩子。如下图所示： ![](https://cdn.luogu.com.cn/upload/image_hosting/3kxiaqfm.png) 上图的 $B_0$、$B_1$、$B_2$、$B_3$、$B_4$ 都是二项树。对比前面提到的二项树的定义：$B_0$ 只有一个节点，$B_1$ 由两个 $B_0$ 所组成，$B_2$ 由两个 $B_1$ 所组成，$B_3$ 由两个 $B_2$ 所组成，$B_4$ 由两个 $B_3$ 所组成；而且，当两颗相同的二项树组成另一棵树时，其中一棵树是另一棵树的最左孩子。 ###### 二项树的性质二项树有以下性质： 1. $B_k$ 共有 $2^k$ 个节点。如上图所示，$B_0$ 有 $2^0=1$ 节点，$B_1$ 有 $2^1=2$ 个节点，$B_2$ 有 $2^2=4$个节点，... 2. $B_k$ 的高度为 $k$。 3. $B_k$ 在深度 $i$ 处恰好有 $C_k^i$ 个节点，其中 $i=0,1,2,...,k$。 4. 根的度数为k，它大于任何其它节点的度数。节点的度数是该结点拥有的子树的数目。特殊的，我们说只有 $1$ 个结点的树的高度/深度为 $0$。 ##### 二项堆的介绍二项堆和之前所讲的堆(二叉堆、左倾堆、斜堆)一样，也是用于实现优先队列的。二项堆是指满足以下性质的二项树的集合： 1. 每棵二项树都满足最小堆性质。即，父节点的关键字 $\le$ 它的孩子的关键字。 2. 不能有两棵或以上的二项树具有相同的度数(包括度数为 $0$ )。换句话说，具有度数 $k$ 的二项树有 $0$ 个或 $1$ 个。 ![](https://cdn.luogu.com.cn/upload/image_hosting/c0oc3qkh.png) 上图就是一棵二项堆，它由二项树 $B_0$、$B_2$ 和 $B_3$ 组成。对比二项堆的定义： 1. 二项树 $B_0$、$B_2$、$B_3$都是最小堆； 2. 二项堆不包含相同度数的二项树。二项堆的第 $1$ 个性质保证了二项堆的最小节点就是某个二项树的根节点，第 $2$ 个性质则说明结点数为 $n$ 的二项堆最多只有 $\log{n} + 1$ 棵二项树。实际上，将包含 $n$ 个节点的二项堆，表示成若干个 $2$ 的指数和(或者转换成二进制)，则每一个 $2$ 个指数都对应一棵二项树。例如，$13$ (二进制是`1101`)的 $2$ 个指数和为 $13 = 2^3 + 2^2 + 2^0$, 因此具有 $13$ 个节点的二项堆由度数为 $3$, $2$, $0$ 的三棵二项树组成。 #### 基本操作 ##### 插入一般而言，可并堆的插入就一句话：将新结点视为一个只有一个结点的堆，执行堆的合并。 ##### 合并两个二项堆直接合并的话几乎肯定会破坏性质2，所以我们需要从下往上扫一遍，遇见有相同大小的就合掉。你想到了什么？二进制加法？对，就是这个。容易发现复杂度是 $O(\log n)$ 的。 ##### 查找最小数维护一个指针就好啦，时间复杂度 $O(1)$。 ##### 删除一个最小数 1. 找到那个最小数（肯定是某个二项堆的根节点）。 2. 暴力去掉，把子节点都拆出来倒一起。 3. 倒出来的子节点当做一个新堆与原堆合并。时间复杂度$O(1+1+\log n)$ = $O(\log n)

调整某个数的权值

这个在某一个二项堆里面进行内部消化就好啦。能上浮上浮，不能上浮就从大的孩子开始往小的找，这样每次比较都能够排除一半的待比较集合，时间复杂度 O(\log n)。

实现

下面给出由 DeepSeek 完成的包含以上操作的二项堆代码：here.

（五）斐波那契堆 (Fibonacci Heap)

Q : 不是哥们你学它干嘛

A : 炫技

这是个象征着自由的数据结构

定义与性质

斐波那契堆是一种可合并堆，可用于实现合并优先队列。它比二项堆具有更好的平摊分析性能，它的合并操作的时间复杂度是 O(1)。与二项堆一样，它也是由一组堆最小有序树组成，并且是一种可合并堆。与二项堆不同的是，斐波那契堆中的树不一定是二项树；而且二项堆中的树是有序排列的，但是斐波那契堆中的树都是有根而无序的。斐波那契堆舍弃了二项堆的二项树结构，每个节点的孩子个数没有任何限制，同时用一个大大的双向循环链表串起整个堆。

当然，斐波那契堆虽然理论时间复杂度得到了改善，但是它常数太大了，以至于能够用它的场合都能用二项堆来替代。所以，其在OI中几乎没有任何实际价值。

基本操作

插入

同样，斐波那契堆的插入操作就一句话：将新结点视为一个只有一个结点的堆，执行堆的合并。

合并两个斐波那契堆

既然我们用一个循环链表表示一个斐波那契堆，那么把两个堆串一起就好了。

查找最小数

维护一个指针就好啦，时间复杂度 O(1)。

删除最小数

首先，我们删除那个最小数，然后将它的孩子们全部倒一起堆到根表（就是最大的那个双向链表）里面。

但是，我们不可能就这么拍拍屁股走人，我们需要更新那个最小数指针。

然后你会发现，如果按照上述狂野奔放的操作的话，我们的斐波那契堆会退化成斐波那契双向链表，根表里面节点的数量最多可能达到 O(n)。所以，为了防止 O(n^2) 惨剧出现，我们需要对一些散散的根节点进行一些合并。

参照二项堆的思路，合并的时候，只需要让每种堆只有一个就好了。二项堆里面是每种大小的堆只有一个，而我们这里让每种根节点的度数只有一个。为什么？因为我们太自由了，不想维护太多信息。维护堆的大小就太严格了，所以就干脆直接维护度这种随手 O(1) 维护的信息好了。所以，我们直接扫一遍，发现有度相同的直接合并。合并方式特别随意，根节点比一下，输了的丢赢家的孩子表里面去。

调整某个节点的权值

如果没有破坏堆的性质，那就可以直接continue了。但是，在树里面跳的话，会涉及到遍历孩子等一系列麻烦操作，很难保证 O(\log n) 的时间复杂度。所以，必须要找一个不同的方式来调整节点的权值。

这里只讲向根调节，即，如果是大根堆的话，只支持向上调节，小根堆的话只支持向下调节。但是，斐波那契堆是象征着自由的数据结构，即使是最复杂的操作也十分简单暴力。我们找到那个节点，把它拧下来，丢到根表里面去。轻松做到 O(1)。但是你会发现，这样乱搞是要付出代价的，因为这个算法明显十分可卡。也就是说，如果用心卡一下，你的根表里面会充斥着 O(n) 个根节点，占着各种度数。干的漂亮！我们成功地把一个堆变成了分块级的时间复杂度！

所以，我们不能这么乱搞。如果无限制地拧下一个根节点里面的孩子，会让这个根节点的大小与度数严重失衡。解决方案也很简单粗暴，我们让一个节点不能失去太多的孩子，如果它失去的孩子多于一个，我们把它也给拧下来。

实现

下面给出由 DeepSeek 完成的包含以上操作的斐波那契堆代码：here.

复杂度分析

定义一个势能函数 Φ(t)=t 的根表的大小。

势能函数，是均摊时间复杂度证明的一种方式。如果一个操作会引起势能减少，我们就认为这个操作不占用时间。当然，势能函数不能定义成 Φ(t)=∞−操作数，所以，势能在一开始必须为一个有限常数，并且，引起势能增加的操作都必须为势能的增加付出代价。

插入/合并

插入和合并操作会使两个斐波那契堆的势能函数相加，因此不引起势能上升（我们不生产势能，我们只是势能的搬运工），所以仅消耗本身的常数时间。时间复杂度为 O(1)。

查找最小数

容易发现时间复杂度是 O(1)。

删除最小数

随手分析就可以发现，合并操作的开销=开数组登记根节点的开销+合并的开销。其中，登记根节点的开销是由最多的度数不同的根节点个数决定的。

假设度为k的节点最少有 F_k 个子节点。度为 k+1 的节点可以被拆分成两个部分：一个度为 k 的节点和其最大的一个子树。由于子树最多损失一个节点，所以子树的度最少为 k-1，即 F_{k+1} = F_k + F_{k-1}。于是我们就成功证明了 f(i) \ge Fib(i)。其中 Fib(i) 表示斐波那契数列的第i项。然后我们回顾一下斐波那契数列的通项公式：

f(i) \ge Fib(i) = \frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}

所以说，O(f(i))≈O(1.618 i)，斐波那契数列的增长速度是 O(\log n)的。由此，需要登记的根节点最大只有 O(\log n) 种。再考虑合并的开销。合并的时候，我们可能会有 O(n) 个根结点，但是每次合并仅花费常数时间，还都会使势能函数减少 1。则，合并所用时间可以视为由势能支付，可以看做不消耗时间。因此，我们的时间是 O(\log n)。

调整堆的权值

很显然，我们要做的仅仅是拧下来-检查父节点，时间复杂度是 O(1) 的。

（六）布罗达尔队列（Brodal Queue）

Q : 不是哥们你学它干嘛

A : 炫技

尽管他复杂度低，但是工业中运用比较少，因为其实现复杂，而且存在大量的双链表操作，导致其复杂度对应的常数相当高。这里介绍的是用来快速寻找最小值的 Brodal Queue，需要寻找最大值反过来即可。

定义与性质

首先需要知道几点：

一些基本概念。
每个队列包含两个树，T_1 和 T_2。
节点的子节点按从右到左递增的顺序存储在双链表中，同时还有指向最左边子节点和父节点的指针（也就是 4 个指针）。
Violating nodes：指那些不符合父节点小于子节点这一标准的节点，下文称坏点。
每个节点如果有孩子是 rank = j 的（秩为 j），那么节点 rank 为 j 的孩子有 2-7 个（最小为 2，最大为 7）。
Violation list。其存储了所有的坏点，下文称坏点列表。

guides

和斐波那契堆类似，Brodal也是采用类似二进制计算的形式。Brodal采用的是一种叫 Guides的数据结构，其目标具体来说是为了保证：根至少有每种rank子节点两个；w 数组中子节点每种的rank的数量不超过 6。

其使用情景如下：需要维护一个 x_{16} 到 x_1 的队列，条件是 x_i \le T ( T 是一个阈值，threshold，不是前面说的树)。这里我们假设 T=2,假如我们需要做一个加很多 2 的操作，但是我们只允许对结果操作 O(1)次。Guide 就是来找到需要做什么操作的。

在前面提到过，guide 的作用有两种，这里假设其已经发挥了作用，使得根节点有着各种 rank 的子节点 2-7 个，为了让 guide 更好的计算出我们需要进行的操作（这里 T=2，意味着我们进行两种操作，加和减），我们新开一个 x_i' 并对其做如下操作：

对于进行加操作的 guide，把数量为 2-5 的都设置为 0，6 设置为 1，7 设置为 2。
对于进行减操作的 guide，把数量为 7-4 的都设置为 0，3 设置为 1，2 设置为 2。
对于加操作来说，是减 2 和加 1，对于减操作来说，是加 2 和减 1。

但是 guide 还需要对应回节点，这里还需要另外开一个数组，用来指向对应的内存单元。内存单元指向的是最左边的元素的索引或者值（这意味着同一个块的元素指向相同的内存单元）。这里这个块我还没完全理解，但是参考论文中提到的连续的块，似乎是内存分配单位？这样做有两个好处：给一个元素我们可以快速找到其在内存块中最左边的元素 O(1)；在 O(1) 时间内删除块。如图是一个例子，下划线表示相同的块。

下图是一个作为例子的 Guide 的数据结构(出自论文)

准则

#### 基本操作 ##### 链接和断开当我们需要把具有相同 `rank` 的 $x_1$，$x_2$，$x_3$ 合并，并且这三者没有根节点，那么找到最小的然后把其他两个作为其最左边节点即可，不会出现坏点。并且仍然满足准则 $S$ 和 $O$ 这十条。

当我们需要把根节点x的儿子移走时，当其具有 2-3 个 rank 为 rank(x)-1 孩子时，如果把这 2-3 个孩子都移走，这时候 x 的 rank 是其孩子最大 rank +1，如果当其具有 4 个及以上 rank 为 rank(x)-1 的孩子时，可以轻松的移除两个。

总体来说，移除一棵 rank k 的子树，总是会导致 2-3 个 k-1 的树和一个额外的 rank 最大为 k 的树。如图所示：

维护根节点的孩子

对于根节点，添加或者删除子节点需要维护准则 R_1，这时候需要使用 4 个 guide，T_1 和 T_2 各两个，这里仅以 T_1 为例，T_2 类似。

为了保证对于 t_1 的孩子节点的访问时间能控制在常数时间内，这里我们需要维护一个变长数组来指向 t_1 的 rank为 0 到 r(t_1)-1 的孩子节点。R_1 准则规定了其必须存在。Guide 主要针对 rank 小于等于 r(t_1) - 3 的孩子节点，对于其他两种rank独立处理（直接处理保证其在 2-7 范围内），这样做是为了避免由于两个 guide 之间相对独立（一个 guide 负责上边界，一个 guide 负责下边界）导致的问题。

当我们向 t_1 中添加 rank 为 i 节点的时候(i < r(t_1) - 2)，guide 会告诉我们在哪里操作。当这个操作导致树高度增长时，我们也要扩充相应的 guide 域。

对于 t_1，由于其根节点是最小值，因此我们的操作不会引起坏点，但是对于 t_2，删除操作会引起三次损坏。因此我们仅删除 t_2 中 rank 大于 r(t_1) 的节点。当删除后剩余的树的 rank 小于 r(t_1) 时，将其作为 t_1 的孩子，否则作为 t_2 的，产生的坏点根据其rank放置在 V 中。

冲突减少转换(Violation reducing transformations)

这里的冲突减少针对 y，y 属于 T_1 和 T_2 交集，有 V(y) 和 W(y)。

假设我们现在有两个冲突节点，x_1 和 x_2，并且 x_1 和 x_2 具有相同的 rank（这里已经确保这两个节点都是坏点）。假如 x_1 和 x_2 不是兄弟（这里我们假设 x_1 的父节点更小），那样我们把 x_2 换过来做 x_1 的兄弟。如果 x_1 有不少于一个兄弟，那么把 x_1 切下来作为 t_1 的子节点。假如 x_1 和 x_2 已经是兄弟了，并且是仅有的两个孩子节点，这时候如果 r(y)>r(x_1)+1,直接将 x_1 和 x_2 切下来作为 t_1 的子节点。但是如果r(y)=r(x_1)+1,这个时候我们将 x_1,x_2,y 全部切下来，y 的 rank 将由他新的最左边的儿子决定(+1)，然后用t_1 的同 rank 的子节点替换 y。这时，如果 y 是 t_1 的子节点，那么我们只切下 y。如果替换 y 的节点是坏点，那么我们把这个节点加入到 W(t_1)。

避免过多坏点

这里主要介绍下减少坏点的方法。

首先，我们只往 V(t_1) 和 W(t_1) 添加坏点。然后 W(t_1) 的内容被 guide监视，guide保证 W(t_1) 的节点数少于 6（规则 O_4）。当加入节点后 W(t_1) 的节点数超过 6 个时，会进行冲突减少转换操作（在guide指导下）。

当我们对queue执行操作的时候，通过将 T_2 的子树移到 T_1 来将 t_1 的 rank 提高至少 1，可以减少 \alpha 个坏点(rank 大于 r(t_1)) (规则 O_5)，

常用的操作

Insert 插入

作为meld的一种特例。将新结点视为一个只有一个结点的堆，执行堆的合并。

Meld 合并( Q_1 和 Q_2 )

合并涉及四棵树（每个队列两棵），拥有最小的根节点的树是新的 T_1（由于 O_1 准则，这棵树应该是 Q_1 或者 Q_2 的 T_1 树），如果这棵树拥有最大的 rank，我们仅需把其他几棵树加进去。这是最简单的情况。

否则拥有最大rank的这棵树成为新的 T_2 树，这时候把剩下的树加进去，如果某一棵树的 rank和新 T_2 树相等，还需要进行拆分。

Decrease Key

用新的值代替旧的。如果新的值小于 t_1，我们把 t_1 和新的值做一个交换。如果新的值是好节点我们停止（即满足父节点小于任意子节点），否则做减少坏点处理。

Delete MIN 删除最小值节点

这个是操作中最复杂的，复杂度达到了O(\log n)。首先通过把 T_2 的孩子移到 T_1 树来把 T_2 树清空，这时候 T_2 树的根节点作为 T_1 树的根节点的一个rank 0 的子节点。然后删除 t_1 。这时候有 O(\log n) 棵非独立子树。然后在 V 和 W 集中以及子树的根节点中寻找最小值。如果这个最小值不是根，那么我们把他和一个rank相同的非独立子树的根交换，然后将新的节点最为最小值节点，将非独立子树们作为新的节点的孩子，然后进行 O(\log n)次链接和断开操作，就可以让新的树遵守准则 S_1-S_5，R_1和R_3。然后将现在根节点的 V 和 W 集合并，然后将旧的 V 和 W 集并入，这一步的开销也是 O(\log n)，然后做冲突减少转换（最多 O(\log n) 次)来使得每个rank 最多有一个坏点，然后将现在的作为新的 W 集，把 V 集置空，使得满足 O_1-O_5 以及 R_2 准则。

删除某一节点

先将待删除节点使用Decrease Key，并将新的 key 设置为负无穷，然后使用删除最小值节点方法。

其他的优先队列操作

实现

这里给出 DeepSeek 的实现，笔者也可以自行尝试实现，显然可以极好的提升代码能力。

例题

P3378 【模板】堆

P3377 【模板】左偏树/可并堆

P1456 Monkey King

P2713 罗马游戏

0x23 线段树 I：基本操作，扫描线与合并分裂

~~可可爱爱的线段树姐姐~~

（一）线段树入门

引入

1000ms 时限下，考虑一个问题，我们有一个 n 个数的数列，有 m 个操作：

把 a_l \sim a_r 加上 k
求 a_{l} \sim a_r 的和。

先不考虑修改，对于查询，我们可以使用前缀和来维护。但是当我们引入修改操作后，事情变得难以解决起来。

当 n \le 5000 的时候，我们考虑暴力维护每次询问，硬更新硬求和即可，复杂度 O(n^2)。

当 n \le 50000 的时候，我们考虑分块，于是复杂度被优化到了近似 O(n \sqrt{n})。

当 n \le 300000 的时候，我们观察到 O(n \sqrt n) 也不足够优秀，这个时候，使用一款对数级别的算法解决这个问题变得十分必要。于是，我们发明了线段树。

线段树的基本结构

大部分人学习数据结构的时候都是先学习的树状数组再学习的线段树。笔者认为虽然树状数组比起线段树代码难度较小，细节也较少，但思维难度却是较高的。（可能是笔者太菜了，当时理解lowbit都理解半天）所以本篇文章会优先介绍线段树再介绍树状数组。

首先，我们有一个序列。这个序列包含有 6 个元素： \{1,1,4,5,1,4\}。对于分块，我们是把这个数列划分为一些块来分别维护，但这样终究也只能是在数列上动些手脚。因此，我们考虑更“二维”的去组织数据。

考虑把数列从中间劈开，分为 [1,3] 和 [4,6] 两段。每一段上维护该段的信息，譬如该段数据之和。这样，我们就可以在 O(1) 的时间内知道这一段的和。但是，如果询问时我们问到了这一段内部分数据的和（如 [4,5]）或者跨段的和（如 [2,6]），那我们就束手无策了。为了避免这种情况，我们把每一段再分为两段，也就是把 [1,3] 分解成 [1,2] 和 [3,3]（[4,6] 自行类比）。这样，当面临上面两种情况的时候，就可以解决了。

同理，我们不断对每一段拆分，直到拆分完每一段的长度都为 1。这个时候我们就可以把数据组织起来，建立一棵从上到下区间长度逐步缩短的树，完成线段树的建立。然后我们就可以在每个节点处维护一些信息。值得注意的是，只有最下面一层的叶子节点才保存了实际的数字，其它的每个节点只保存着这个区间的信息（如区间和，区间最值等）。所以对于上面那个数列，它建出的线段树中每个节点存的值长这样：

学完了线段树的结构，我们可以给线段树下定义了。

定义

线段树第一定义

我们说：线段树是一种二叉搜索树,它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

线段树第二定义

我们说：线段树数据结构皇冠上的明珠。

线段树第三定义

我们说：线段树是十分可爱且十分可爱的。

线段树第四定义

我们说：线段树前三种定义中只有第一种定义是完全正确的，其他定义应用在竞赛中除了一分不得以外没有任何坏处。

基本操作

建立线段树数组

int n,m,a[N];
int t[4 * N];

我们需要一个数组来存储线段树。该数组的含义是：

对于每一个线段树结点，我们维护它的所属区间的值。

一般来讲，对于朴素的线段树，我们对于一个编号为 p 的结点，我们使用 2p 作为它的左儿子，使用 2p+1作为它的右儿子。此时，容易证明数组中每个位置的利用是不重不漏的，该结论留给读者自行证明。至于为什么要开 4 倍 N 的空间，请耐心往下看，你会得到答案。

上传信息

既然我们在每个节点维护该点所属区间的信息，那么如果我们想求出它上面那一层区间的值，那我们如何处理呢？

容易发现，每个节点所维护的区间信息等于它左儿子维护信息与右儿子维护区间信息的结合。这又引出了线段树的一个使用条件：它所维护的操作是需要满足结合律的。因此，对于上文给出例子，我们给出示例代码：

void pushup(int p)
{
  tree[p].val = tree[ls].val + tree[rs].val;
}
//这里ls=p*2,rs=p*2+1

建树

有了上传信息的操作，我们就可以写出建树代码，从最大的区间向小区间二分递归，如果递归到 l = r 的叶子结点就把当前结点位置的数列的值填进树里，最后一层一层利用递归传回去就可以了，复杂度是 O(n) 的。

void build(int p,int l,int r)
{
    if(l == r)
    {
        t[p] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(p);
}

查询

查询好办，从最大的区间开始二分往下扫，可以分为三种情况：

如果查询区间被该区间完全包含，那么直接返回该区间的值，无需继续递归。
如果查询区间被该区间部分包含，那么继续递归。
如果查询区间和该区间没有任何交集，那么直接返回 0，表示你在递归空气。

然后就可以很简单的写出代码了。

int qry(int ql,int qr,int l,int r,int p)
{
    int ans = 0;
    if(ql <= l && r <= qr) return t[p];
    int mid = (l+r) >> 1;
    if(ql <= mid) ans += qry(ql,qr,l,mid,ls);
    if(qr > mid) ans += qry(ql,qr,mid+1,r,rs);
    return ans;
}

单点修改

单点修改比较简单，不断递归，定位到要找的节点，修改即可。笔者可以自行完成这部分代码。时间复杂度为从顶部遍历到叶子的 O(\log n)。

区间修改

考虑如何进行区间修改。如果直接把区间遍历一遍，依次修改，复杂度会达到无法接受的 O(n\log n)。那么怎么能让区间修改的复杂度变小呢？我们可以考虑整段整段的像查询一样维护，但是，如果查询还用不到这一段，我们没必要去浪费额外的时间进行修改，因此我们可以建立一个容器，把要修改但还没修改的东西都扔到里面，等到需要修改的时候再进行修改，这样不仅有效减少了复杂度，还可以让多次修改操作一并修改，这样大大节约了时间。我们称这个扔修改的容器为“懒标记”。也就是线段树的关键：Lazy-Tag.

pushdown操作

再想一个问题，在给某个区间打上懒标记后，我们如何查询其他区间的值？

如果我们直接查询到那些区间上，会发现根本就没有被加上过2。为什么呢? 因为现在懒标记打在了区间上。而他的子节点压根没被修改过。所以我们需要把懒标记向下传递。这就有了一个操作，叫做pushdown，它可以把懒标记下传。设想一下，如果我们要把懒标记下传，应该注意什么呢？

首先，要给子节点打上懒标记。
然后，我们要修改子节点上的值。
最后，不要忘记把这个节点的懒标记清空。

这边直接给出区间加区间和的pushdown。

void add(int p,int l,int r,int k)//add函数也可以直接写在里面
{
    tag[p] = tag[p] + k;
    t[p] = t[p] + k * (r-l+1);
}
void pushdown(int p,int l,int r)
{
    int mid = (l + r) >> 1;
    add(ls,l,mid,tag[p]);
    add(rs,mid+1,r,tag[p]);
    tag[p] = 0;
}

同时，在前面我们定义一个 tag 数组，表示该节点的懒标记的值。

学会了懒标记，应该可以很轻松地写出区间修改的代码了。

区间修改的操作很像区间查询，也是查找能够覆盖住的子区间，然后给它打上懒标记。

void udt(int nl,int nr,int l,int r,int p,int k)
{
    if(nl <= l && r <= nr)
    {
        t[p] += k*(r-l+1);
        tag[p] += k;
        return;
    }
    pushdown(p,l,r);
    int mid = (l+r) >> 1;
    if(nl <= mid) udt(nl,nr,l,mid,ls,k);
    if(nr > mid) udt(nl,nr,mid+1,r,rs,k);
    pushup(p);
}

复杂度分析

为什么需要开 4 倍空间

注：这是来自 OI-Wiki 的证明。

关于线段树的空间：如果采用堆式存储（2p 是 p 的左儿子，2p+1 是 p 的右儿子），若有 n 个叶子结点，则 d 数组的范围最大为 2^{\left\lceil\log{n}\right\rceil+1}。

分析：容易知道线段树的深度是 \left\lceil\log{n}\right\rceil 的，则在堆式储存情况下叶子节点（包括无用的叶子节点）数量为 2^{\left\lceil\log{n}\right\rceil} 个，又由于其为一棵完全二叉树，则其总节点个数 2^{\left\lceil\log{n}\right\rceil+1}-1。

当然如果你懒得计算的话可以直接把数组长度设为 4n，因为 \frac{2^{\left\lceil\log{n}\right\rceil+1}-1}{n} 的最大值在 n=2^{x}+1(x\in N_{+}) 时取到，此时节点数为 2^{\left\lceil\log{n}\right\rceil+1}-1=2^{x+2}-1=4n-5。所以开 4n 是绝对安全的。

（二）权值线段树

定义与性质

我们说：普通的线段树维护区间信息，权值线段树维护值域信息。

权值线段树就是对权值作为维护对像而开的线段树，即每个点上存的是区间内的对应数字的某种值（最常见的是出现次数）。权值线段树可以干很多事情，比如查询第 k 小，查找前驱后继等。当插入一个 6 时，我们考虑在区间 [1,8]，[5,8]，[5,6]，[6,6] 上 +1。那么每个区间维护的信息就是这个区间内的数的数量。这就是权值线段树的原理。

我们知道，对于一棵线段树而言，如果它的总长度不变，那么它的形态是不会改变的。也就是说，在 len 不变的情况下，权值树的形态是不会改变的。这样一来，我们就可以对权值树进行加减法操作。对于权值树 A,B，若 A,B 形态相同，则我们可以直接合并这两棵权值树，合并的方式就是对应节点相加。显然，加出来的树依然是一棵权值线段树。这个性质也非常好，可以解决一些普通线段树无法解决的问题。

操作

插入就是把从这个数的节点到根节点的路径上每一个节点都加上 1 即可。删除同理，减去 1 就行了。

很多平衡树能做的操作权值线段树都能做，并且权值线段树比平衡树们码量小很多，非常优秀。

查询第k大数

请注意，这个查询第k大是针对整个权值线段树的，要查区间第k大请去学主席树或树套树。

权值线段树是维护值域的，一个节点的左右端点都应该是一个具体的数字，而且值域肯定是递增的，所以我们可以二分。

如果 k 小于区间中点，那么也就说明结果为左区间第 k 大数。否则，也就说明结果为右区间第 k-l_{size} 大数。

int kth(int x,int l,int r,int k){
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(k<=t[ls]) return kth(ls,l,mid,k); 
    return kth(rs,mid+1,r,k-tr[ls]);
}

查询一个数的排名

和查询第k大差不多。

每次把 x 与当前区间中点 mid 比较，如果小于等于 mid ，说明在左区间，向左儿子寻找。如果大于 mid ，说明在右区间，这时，它的排名要加上左子树的大小（它比整个左子树的数都大）

如果找到叶子节点了，那么返回 1 (在 [l,r] 的区间只有自己，排名第一)

int rnk(int x,int l,int r,int k){
    if(l==r) return 1;
    int mid=(l+r)>>1;
    if(k<=mid) return rnk(ls,l,mid,k);
    return rnk(rs,mid+1,r,k)+tr[ls];
}

空间优化技巧

这里介绍两种优化方式：离散化和动态开点。

两种方法其实各有优劣，如果只是为了缩小值域，离散化似乎更好写一点，但是动态开点还可以被应用到可持久化、线段树合并和分裂上，所以都学一学吧。

离散化

数据范围太大了，需要缩小数据范围，这句话让你想到了什么？

当然是离散化了！

所以我们可以把所有操作都存起来，排序然后离散化，离线进行操作。离散化是一种数据处理的技巧，本质上可以看成是一种哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。方法如下：

创建原数组的副本。
将副本中的值从小到大排序。
将排序好的副本去重。
查找原数组的每一个元素在副本中的位置，位置即为排名，将其作为离散化后的值。

动态开点

动态开点，顾名思义，就是使用的时候再开点。

如果数据范围是 [-10^7,10^7]，在权值线段树的使用过程中，很大一部分的节点会使用不到，这会造成一种浪费。

动态开点的意思就是：不一上来就把所有的节点全部建立起来，只在需要用到一个节点的时候再建立一个节点。

注意：使用动态开点线段树的话，节点的下标将是无序的，因此必须建立结构体或用两个数组来分别保存一个节点的左右子节点。

（三）扫描线

我们有一个问题：求 n 个四边平行于坐标轴的矩形的面积并。暴力求解显然对于较大的 n 不可行，所以我们考虑使用数据结构进行对问题的优化。

所谓扫描线，其实就是利用线段树维护线段，从下往上扫，每遇到一条线段就计算矩形长度以及更行当前行的线段长度，维护就行了，注意需要离散化。

做法上，给每一个矩形的上下边进行标记，下面的边标记为 1，上面的边标记为 -1。每遇到一个水平边时，让这条边（在横轴投影区间）的权值加上这条边的标记。小矩形（不一定只有一个）的宽度就是整个数轴上权值大于 0 的区间总长度。

用线段树维护矩形的长，也就是整个数轴上覆盖次数大于 0 的点。需求列举如下：

一段区间权值加 1、减 1。
统计整个数轴上，区间权值大于 0 的「区间长度和」。

如果你尝试直接用普通线段树模板来实现的话，也许会遇到些挫折。具体地，由于在区间加时，即使修改区间和节点管理区间重合，我们还是不能常数时间知道覆盖次数如何变化。这是因为我们不能直接知道：管理范围里有多长的区间会从 1 变成 0（从 0 变成 1）。

这道题只需要朴素的分治就能实现：维护每个节点管理区间中「完全覆盖区间的次数 v[]」（类似不用下放的懒惰标记）和「已覆盖的长度 w[]」两个信息。这里给出一份示例代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
constexpr const int N=1e5,V=1e5;
struct line{
    int l,r,w;
};
vector<line>q[N<<1|1];
int hashX[N<<1|1],hashY[N<<1|1];
struct segTree{
    struct node{
        int l,r;
        int len,cover;
    }t[N<<3|1];

    int size(int p){
        return t[p].r-t[p].l+1;
    }
    void up(int p){
        if(t[p].cover){
            t[p].len=size(p);
        }else{
            if(t[p].l==t[p].r){
                t[p].len=0;
            }else{
                t[p].len=t[p<<1].len+t[p<<1|1].len;
            }
        }
    }
    void build(int p,int l,int r){
        t[p]={l,r};
        if(l==r){
            t[p].cover=0;
            t[p].len=0;
            return;
        }
        int mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        up(p);
    }
    void add(int p,int l,int r,int k){
        if(l<=t[p].l&&t[p].r<=r){
            t[p].cover+=k;
            up(p);
            return;
        }
        if(l<=t[p<<1].r){
            add(p<<1,l,r,k);
        }
        if(t[p<<1|1].l<=r){
            add(p<<1|1,l,r,k);
        }
        up(p);
    }
    int query(){
        return t[1].len;
    }
}t;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;
    static int x1[N+1],y1[N+1],x2[N+1],y2[N+1];
    for(int i=1;i<=n;i++){
        cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
    }
    for(int i=1;i<=n;i++){
        q[x1[i]].push_back({y1[i],y2[i],1});
        q[x2[i]].push_back({y1[i],y2[i],-1});
    }
    t.build(1,0,V);
    ll ans=0;
    for(int i=0;i<V;i++){
        for(auto x:q[i]){
            t.add(1,x.l,x.r-1,x.w);
        }

        ans+=1ll*t.query();
    }
    cout<<ans<<'\n';
    cout.flush();
    return 0;
}

与其说扫描线是一个算法，不如说是利用线段树去维护一些特殊的东西，从而实现某种特殊的功能。

（四）线段树的更多特殊操作

合并

顾名思义，线段树合并是指建立一棵新的线段树，这棵线段树的每个节点都是两棵原线段树对应节点合并后的结果。它常常被用于维护树上或是图上的信息。

首先，对于两个普通的线段树（也就是那种左儿子是 p<<1 右儿子是 p<<1|1 的线段树），没有必要专门设计一个算法合并它们，因为他们已经满了，也就是说我们直接把两个数组按位相加然后重新建一遍线段树肯定是正确且最有效率的。所以我们考虑如何对于两棵动态开点线段树进行合并。观察到并没有什么特别有效的措施，所以直接考虑暴力合并。

假设两颗线段树为 A 和 B，我们从 1 号节点开始递归合并。递归到某个节点时，如果 A 树或者 B 树上的对应节点为空，直接返回另一个树上对应节点，这里运用了动态开点线段树的特性。如果递归到叶子节点，我们合并两棵树上的对应节点。最后，根据子节点更新当前节点并且返回。

0x24 线段树 II：更多的线段树

（一）zkw线段树

（二）李超线段树

（三）猫树

（四）吉司机线段树

0x25 线段树 III：树链剖分及其他

线段树部分的推荐阅读 & 引用

线段树从入门到进阶（超清晰，简单易懂）

线段树，从入门到入坑

浅谈权值线段树

ls学习笔记note37:扫描线(Line Sweep Algorithm)

题解：P5490 【模板】扫描线 & 矩形面积并

0x26 树状数组

0x27 平衡树 I：替罪羊与FHQ

0x28 平衡树 II：Splay与有旋Treap

0x29 平衡树 III：更多的平衡树

0x2A 笛卡尔树

定义与性质

基本操作

实现

复杂度分析

例题

0x2B 可持久化数据结构

Part 4 树状数据结构（二）

0x31 划分树

定义与性质

基本操作

实现

复杂度分析

例题

0x32 Kruskal 重构树

定义与性质

基本操作

实现

复杂度分析

例题

0x33 树套树

0x34 K-D Tree 及空间数据结构

0x35 Link-Cut-Tree

0x36 析合树

0x37 PQ 树

0x38 vEB树

Part 5 其他数据结构和技巧

要写的东西：莫队（带修莫队，树上莫队，回滚莫队，二离莫队，二维莫队），ODT

0x41 莫队

0x42 珂朵莉树（ODT）

空间数据结构：https://www.cnblogs.com/KillerAery/p/10878367.html

罕见：软堆 (Soft Heap)，布隆过滤器，Judy数组 (Judy Array),哈希树 (Merkle Tree),空间填充曲线 (Space-Filling Curves),计数最小略图 (Count-Min Sketch)

鸣谢名单

首先非常感谢所有在OI-Wiki和百度百科做出贡献的创作者，本文的几乎每一个章节都引用了它们的部分介绍，没有你们，我根本无法完成这篇文章。

按名字首字母排序。

一站式搞定数据结构

写在前面

前言

Part 1 线性数据结构

0x01 数组

定义与性质

复杂度分析

优势与劣势

推荐阅读 & 引用

0x02 栈

定义与性质

操作

实现

数组模拟栈

链表模拟栈

STL中栈的操作

变种：单调栈

定义

具体操作

复杂度分析

例题

推荐阅读 & 引用

0x03 队列

（一）普通队列

定义与性质

操作

实现

数组模拟队列

双栈模拟队列

STL队列

例题

（二）双端队列

定义与性质

操作

实现

STL 双端队列

例题

（三）优先队列

例题

（四）单调队列

引入

定义与原理

操作

实现

例题

引用 & 推荐阅读

（五）STL中 stack,queue 和 deque 的常数讨论

1. 双端队列 - deque

实现原理

常数分析（时间复杂度）

2.栈和队列 - stack & queue

0x04 哈希表

（一）朴素哈希

定义与性质

哈希函数

字符串哈希

冲突

（二）一些有趣的哈希

加密哈希

概述

实现原理

第1步：填充补位 (Padding)

第2步：附加长度信息 (Appending Length)

第3步：初始化缓冲区 (Initialize Buffers)

第4步：处理 512 位消息块 (Process Blocks)

破解与安全性

布谷鸟哈希（Cuckoo hash）

算法原理

0x05 链表

定义与性质

基本操作

建立链表

向链表中插入数值

从链表中删除数据

实现

指针实现

STL实现

例题

推荐阅读 & 引用

0x06 ST表