清北普转提五一集训

###### 以下内容为豆包+课件内容，所以有些比较先进的东西，尽情谅解
# 上午课程：数据结构核心知识精要与拓展
## 一、栈（Stack）：后进先出的线性数据结构典范
### 1.1 栈的理论基石与抽象模型
栈作为线性数据结构家族的重要成员，严格遵循**后进先出（Last In First Out，LIFO）**原则，这一特性使其在众多计算机科学领域中发挥着不可替代的作用。从抽象层面看，栈可被视为一种受限的线性表，其数据操作被限定在表的一端进行，这一端被称为栈顶。在计算机系统运行过程中，函数调用时栈帧的创建与销毁、表达式求值时操作数与运算符的处理等，都依赖于栈结构的LIFO特性。例如，当主程序调用函数A时，函数A的局部变量、参数以及返回地址等信息会依次压入栈中；函数A执行完毕后，这些信息按照入栈的相反顺序依次出栈，从而确保程序能够正确恢复到调用前的状态。

在C++标准库中，`stack`容器适配器为开发者提供了便捷的栈操作接口。使用时，需引入`<stack>`头文件，若涉及输入输出操作，还需引入`<iostream>`头文件，代码示例如下：
```cpp
#include <iostream>
#include <stack>
using namespace std;
```

### 1.2 栈的核心操作详解与复杂度剖析
#### 1.2.1 操作示例代码
```cpp
int main() {
    // 创建一个整型栈，此时栈为空，时间复杂度为O(1)
    stack<int> s;

// 压栈操作，将元素依次压入栈顶，每次操作时间复杂度为O(1)
    s.push(10);
    s.push(20);
    s.push(30);

// 访问栈顶元素，获取栈顶数据但不改变栈结构，时间复杂度为O(1)
    cout << "Top element: " << s.top() << endl;  // 输出30

// 出栈操作，移除栈顶元素，时间复杂度为O(1)
    s.pop();
    cout << "After pop, top element: " << s.top() << endl;  // 此时栈顶变为20

// 获取栈的大小，返回栈中元素数量，时间复杂度为O(1)
    cout << "Stack size: " << s.size() << endl;  // 输出2

// 检查栈是否为空，判断栈中是否存在元素，时间复杂度为O(1)
    if (!s.empty()) {
        cout << "Stack is not empty" << endl;
    }

return 0;
}
```

#### 1.2.2 操作说明与复杂度表
|操作名称|方法定义|代码示例|时间复杂度|空间复杂度|操作特性说明|
|----|----|----|----|----|----|
|入栈|`push()`|`s.push(10)`|O(1)|O(1)|在栈顶添加元素，数据存储于栈顶位置，操作时间固定|
|出栈|`pop()`|`s.pop()`|O(1)|O(1)|移除栈顶元素，释放栈顶空间，操作时间固定|
|访问栈顶|`top()`|`int x = s.top()`|O(1)|O(1)|获取栈顶元素值，不改变栈结构，操作时间固定|
|检查空|`empty()`|`if(s.empty())`|O(1)|O(1)|判断栈内元素数量是否为0，操作时间固定|
|获取大小|`size()`|`int sz = s.size()`|O(1)|O(1)|返回栈中元素个数，依赖底层容器实现方式，时间固定|

### 1.3 教师示例代码深度解读与优化建议
```cpp
#include<bits/stdc++.h>
#include<stack>

using namespace std;

// 快读函数，利用getchar提高输入效率，降低I/O时间复杂度
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

stack<int> q;

int main(){
    q.push(1);
    q.push(2);// 向栈中加入元素，遵循LIFO原则
    int z=q.top();// 访问栈顶元素，获取当前栈顶数据
    if (q.empty()) { // 判断栈是否为空，检查栈内元素状态
        cout << "Stack is empty";
    }
    cout<<q.size()<<"\n"; // 输出当前栈中元素个数
    q.pop(); // 删除栈顶元素，改变栈结构
    
    return 0;
}
```
此代码中的`read`函数通过直接操作字符输入流，避免了`cin`的复杂流处理机制，在处理大规模数据输入时，能大幅提升程序的运行效率。不过，`#include<bits/stdc++.h>`这种头文件包含方式虽然方便，但会引入整个标准库的命名空间，可能导致命名冲突，在大型项目或多人协作开发中，建议明确引入所需头文件，以增强代码的可读性和可维护性。

## 二、队列（Queue）：先进先出的线性数据结构典范
### 2.1 队列的理论内涵与应用场景
队列是一种严格遵循**先进先出（First In First Out，FIFO）**原则的线性数据结构，其特点是数据的插入操作在队列尾部进行，而删除操作在队列头部进行。在实际应用中，队列的身影随处可见。例如，在操作系统的任务调度中，新产生的任务会按照到达顺序依次加入任务队列，系统按照任务入队的先后顺序进行处理，以此保证任务执行的公平性；在网络请求处理中，服务器会将客户端的请求放入请求队列，按照先进先出的原则依次处理，避免某些请求长时间得不到响应。

C++标准库提供了`queue`容器适配器，方便开发者实现队列功能。使用时，需引入`<queue>`头文件，若涉及输入输出操作，同样需要引入`<iostream>`头文件，示例代码如下：
```cpp
#include <iostream>
#include <queue>
using namespace std;
```

### 2.2 队列的核心操作详解与复杂度分析
#### 2.2.1 操作示例代码
```cpp
int main() {
    // 创建一个整型队列，初始状态为空，时间复杂度为O(1)
    queue<int> q;

// 入队操作，将元素加入队列尾部，每次操作时间复杂度为O(1)
    q.push(10);
    q.push(20);
    q.push(30);

// 访问队首元素，获取队列头部数据，不改变队列结构，时间复杂度为O(1)
    cout << "Front element: " << q.front() << endl;  // 输出10

// 访问队尾元素，获取队列尾部数据，不改变队列结构，时间复杂度为O(1)
    cout << "Back element: " << q.back() << endl;    // 输出30

// 出队操作，移除队首元素，时间复杂度为O(1)
    q.pop();
    cout << "After pop, front element: " << q.front() << endl;  // 此时队首变为20

// 获取队列大小，返回队列中元素数量，时间复杂度为O(1)
    cout << "Queue size: " << q.size() << endl;  // 输出2

// 检查队列是否为空，判断队列中是否存在元素，时间复杂度为O(1)
    if (!q.empty()) {
        cout << "Queue is not empty" << endl;
    }

return 0;
}
```

#### 2.2.2 操作说明与复杂度表
|操作名称|方法定义|代码示例|时间复杂度|空间复杂度|操作特性说明|
|----|----|----|----|----|----|
|入队|`push()`|`q.push(10)`|O(1)|O(1)|在队列尾部添加元素，数据存储于队尾位置，操作时间固定|
|出队|`pop()`|`q.pop()`|O(1)|O(1)|移除队首元素，释放队首空间，操作时间固定|
|访问队首|`front()`|`int x = q.front()`|O(1)|O(1)|获取队首元素值，不改变队列结构，操作时间固定|
|访问队尾|`back()`|`int x = q.back()`|O(1)|O(1)|获取队尾元素值，不改变队列结构，操作时间固定|
|检查空|`empty()`|`if(q.empty())`|O(1)|O(1)|判断队列内元素数量是否为0，操作时间固定|
|获取大小|`size()`|`int sz = q.size()`|O(1)|O(1)|返回队列中元素个数，依赖底层容器实现方式，时间固定|

### 2.3 STL自带队列与手写队列的对比分析
#### 2.3.1 STL自带队列示例
```cpp
#include<bits/stdc++.h>
#include<queue>
using namespace std;
queue<int> q;// 声明一个整型队列

int main() {
    q.push(1);// 向队列里加入元素，新元素进入队伍末尾
    q.push(2);

q.pop();// 删除队列头的元素，队伍最前面的人离开（该操作不返回元素值）

int x=q.front();// 获取队列头的元素，查看队伍最前面的人（不会删除该元素）

cout<<q.size()<<"\n"; // 输出当前队列剩余元素的数量，即队伍中剩余人数

return 0;
}
```
STL自带的`queue`容器适配器封装程度高，使用起来简洁方便，其底层默认基于`deque`容器实现，在性能和通用性方面表现出色，适用于大多数常见的队列应用场景。

#### 2.3.2 手写队列示例
```cpp
#include<bits/stdc++.h>
using namespace std;
const int xx=1e5+5;
// 自定义队列结构体
struct queue{
    int a[xx];// 用数组记录队列元素
    int end;// 队列尾的位置
    int first;// 队列头的位置

// 入队操作，在队尾添加元素，时间复杂度O(1)
    void push(int x){
        end++;
        a[end]=x;
    }

// 出队操作，通过移动队首指针实现，避免整体元素前移的高复杂度，时间复杂度O(1)
    void pop(){
        first++;// 不需要所有的都往前移（时间复杂度太大），直接把队列头往后移即可
    }

// 获取队列大小，计算队列中元素个数，时间复杂度O(1)
    int size(){
        return end-first+1; 
    }

// 获取队首元素，返回队列头部数据，时间复杂度O(1)
    int front(){
        return a[first];
    }
}xjy;

int main(){
    return 0;
} 
```
手写队列通过数组模拟队列结构，能够清晰地展示队列的底层实现原理，有助于深入理解队列的工作机制。然而，这种实现方式存在一定的局限性，例如数组大小固定，可能会出现溢出的情况，并且缺乏动态扩容等功能，相比STL自带的队列，在灵活性和稳定性方面稍显不足。

### 2.4 单调队列：特殊队列的高级应用与优化
#### 2.4.1 单调队列的基本概念与数学定义
单调队列是一种特殊的队列数据结构，其内部元素始终保持单调递增或单调递减的顺序。在数学建模和算法设计中，单调队列常用于解决动态规划问题中的区间极值维护问题。例如，在滑动窗口模型中，需要快速求解窗口内的最大值或最小值，单调队列能够高效地满足这一需求。

#### 2.4.2 单调队列的核心特性与算法证明
1. **单调性保持**：队列内元素严格遵循单调规则，通过数学归纳法可以证明，在插入和删除操作后，队列的单调性依然能够得到保持。
2. **高效插入与删除**：插入元素时，通过比较新元素与队尾元素，移除不满足单调性的旧元素，确保队列始终保持单调，每次插入操作的时间复杂度为O(1)。
3. **快速获取极值**：由于队列的单调性，队首或队尾元素（根据单调方向）即为当前队列所维护的极值，获取极值操作的时间复杂度为O(1)。

#### 2.4.3 实现代码与性能分析
```cpp
#include<bits/stdc++.h>
using namespace std;
deque<int> q; // 使用双端队列实现单调队列，方便在两端进行插入和删除操作
const int xx=1e5+5;
int a[xx];

// 向单调队列插入元素，同时维护单调性，时间复杂度O(1)
void push(int i) {
    while(q.size()>0 && a[q.back()]>=a[i]){
        q.pop_back();
    }  
    q.push_back(i);
}

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]; 
    }
    int m;
    cin>>m;// 求所有长度为m的区间最小值

for(int i=1;i<=n;i++){
        push(i);// 向单调队列里加入a[i] 
        if(i-m==q.front()) q.pop_front();// 把a[i-m]这个数删掉，因为它超出窗口范围
        if(i>=m){// 若已经到达m的位置
            cout<<a[q.front()]<<"\n";// 直接输出队列头元素（此时队列是单调递增，队首为最小值） 
        }
    }
    return 0;
}
```
上述代码通过`deque`（双端队列）实现单调队列，在处理长度为`m`的滑动窗口最小值问题时，整体时间复杂度为O(n)，相较于暴力解法的O(n * m)，性能得到了显著提升，充分体现了单调队列在处理特定问题时的高效性。

## 三、并查集（Disjoint Set Union, DSU）：不相交集合处理的利器
### 3.1 并查集的理论基础与数学模型
并查集是一种树形数据结构，主要用于处理不相交集合的合并与查询问题。在图论领域，它可以用来判断无向图的连通性；在集合论中，用于维护集合的划分关系。并查集支持两个核心操作：**查找（Find）**和**合并（Union）**。通过路径压缩和按秩合并等优化手段，可将单次操作的均摊时间复杂度降低至近乎O(1)，使其在处理大规模集合动态维护问题时表现出色。

### 3.2 并查集核心操作的算法实现与复杂度分析
#### 3.2.1 实现代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
const int xx=1e5+5;
int to[xx];// to[i]代表i的箭头指向谁，即i的父节点

// 查找函数，从p出发，找到其所在集合的根节点，并进行路径压缩优化，时间复杂度近乎O(1)
int go(int p) {
    if(p==to[p]) return p;
    else {
        to[p]=go(to[p]);
        return to[p]; 
    }
}

// 合并函数，将p1和p2所在的集合进行合并（随机选择一个根节点作为新的根），时间复杂度近乎O(1)
void add(int p1,int p2){
    if(rand()%2){
        to[go(p1)]=go(p2);
    }else{
        to[go(p2)]=go(p1);
    }
}

// 查询函数，判断p1和p2是否属于同一个集合，时间复杂度近乎O(1)
bool find(int p1,p2){
    if(go(p1)==go(p2)){
        return true;
    }else{
        return false;
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        to[i]=i; // 初始化，每个元素自己是一个集合，时间复杂度O(n)
    }
    int p1,p2;
    cin>>p1>>p2;
    add(p1,p2); // 合并p1和p2所在的集合
    cout << (find(p1,p2) ? "Same set" : "Different sets") << endl; // 查询并输出结果
    return 0;
}
```

#### 3.2.2 复杂度分析
经过路径压缩和按秩合并优化后，查找和合并操作的均摊时间复杂度近乎O(1)，初始化操作的时间复杂度为O(n)。这使得并查集在处理大量元素的集合合并与查询问题时，能够高效地完成任务，在诸如最小生成树算法（Kruskal算法）、社交网络中的朋友圈关系判断等场景中有着广泛的应用。
# 下午课程：算法思想与数据结构进阶知识精要
## 一、分块算法（Block Decomposition）：区间问题处理的高效策略
### 1.1 分块算法的理论基础与核心思想
分块算法是一种将数据分割成若干块进行处理的算法思想，它巧妙地融合了暴力枚举和高效算法的优势，在时间复杂度和实现复杂度之间找到了一个理想的平衡点。该算法的核心在于将长度为 \( n \) 的数据序列划分为大小近似相等的 \( \sqrt{n} \) 个块（特殊情况下也可根据需求调整块大小），通过对块内数据的预处理和灵活操作，实现对区间查询、修改等问题的高效解决。

以区间求和问题为例，若采用暴力枚举，每次查询区间 \([l, r]\) 的和都需要遍历该区间内的所有元素，时间复杂度为 \( O(n) \) ；而使用线段树等高级数据结构虽然能将查询复杂度降低到 \( O(\log n) \) ，但其实现过程复杂，代码调试难度大。分块算法则另辟蹊径，将数据分块后，对每个块内的数据进行预处理（如计算块内元素总和），在查询时，对于完全包含在块内的区间，可直接利用预处理结果快速得出答案；对于跨越多个块的区间，只需对部分边界元素进行枚举计算，从而将查询时间复杂度降低到 \( O(\sqrt{n}) \) ，同时代码实现难度显著低于线段树。

### 1.2 分块算法的代码实现与细节解析
```cpp
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn = 1000010;
int n, m, a[maxn];
int belong[maxn];//belong[i]代表i这个数是第几块 
int siz[maxn];//siz[i]代表第i块有几个数 
int mx[maxn];//mx[i]代表第i块所有数的最大值
int delta[maxn];//delta[i]代表第i块整体被加了多少

signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

// 计算块大小，通常取sqrt(n)，使块的数量和大小相对均衡
    int s = sqrt(n);
    for (int i = 1; i <= n; i++)
        belong[i] = (i - 1) / s + 1;

// 初始化块内元素个数和最大值
    for (int i = 1; i <= n; i++)
        mx[belong[i]] = max(mx[belong[i]], a[i]), siz[belong[i]]++;

for (int i = 1; i <= m; i++)
    {
        int opt;
        cin >> opt;
        if (opt == 1)
        {
            // 操作1：将区间[l, r]内的元素全部修改为v
            int l, r, v;
            cin >> l >> r >> v;
            if (belong[l] == belong[r])
            {
                // 若l和r在同一块内，直接暴力修改并更新块内最大值
                for (int j = l; j <= r; j++)
                {
                    a[j] = v;
                    mx[belong[j]] = max(mx[belong[j]], v);
                }
            }
            else
            {
                // 若l和r跨越多个块，分别处理边界块和中间完整块
                for (int j = l; belong[j] == belong[l]; j++)
                {
                    a[j] = v;
                    mx[belong[j]] = max(mx[belong[j]], v);
                }
                for (int j = belong[l] + 1; j < belong[r]; j++)
                {
                    for (int k = (j - 1) * s + 1; k <= min(j * s, n); k++)
                        a[k] = v;
                    mx[j] = v;
                }
                for (int j = r; belong[j] == belong[r]; j--)
                {
                    a[j] = v;
                    mx[belong[j]] = max(mx[belong[j]], v);
                }
            }
        }
        else if (opt == 2)
        {
            // 操作2：将区间[l, r]内的元素全部加上v
            int l, r, v;
            cin >> l >> r >> v;
            if (belong[l] == belong[r])
            {
                // 同块内直接暴力修改并更新块内最大值
                for (int j = l; j <= r; j++)
                {
                    a[j] += v;
                    mx[belong[j]] = max(mx[belong[j]], a[j]);
                }
            }
            else
            {
                // 跨块时，边界块暴力修改，中间块通过delta数组记录整体增量
                for (int j = l; belong[j] == belong[l]; j++)
                {
                    a[j] += v;
                    mx[belong[j]] = max(mx[belong[j]], a[j]);
                }
                for (int j = belong[l] + 1; j < belong[r]; j++)
                {
                    delta[j] += v;
                    mx[j] += v;
                }
                for (int j = r; belong[j] == belong[r]; j--)
                {
                    a[j] += v;
                    mx[belong[j]] = max(mx[belong[j]], a[j]);
                }
            }
        }
        else if (opt == 3)
        {
            // 操作3：查询区间[l, r]内的最大值
            int l, r, ans = -1e18;
            cin >> l >> r;
            if (belong[l] == belong[r])
            {
                // 同块内暴力枚举并考虑块内增量
                for (int j = l; j <= r; j++)
                    ans = max(ans, a[j] + delta[belong[j]]);
            }
            else
            {
                // 跨块时，分别处理边界块和中间块
                for (int j = l; belong[j] == belong[l]; j++)
                    ans = max(ans, a[j] + delta[belong[j]]);
                for (int j = belong[l] + 1; j < belong[r]; j++)
                    ans = max(ans, mx[j]);
                for (int j = r; belong[j] == belong[r]; j--)
                    ans = max(ans, a[j] + delta[belong[j]]);
            }
            cout << ans << endl;
        }
    }
    return 0;
}
```
在上述代码中，`belong`数组用于记录每个元素所属的块编号，`siz`数组存储每个块的元素个数，`mx`数组维护块内的最大值，`delta`数组记录块的整体增量。通过这些辅助数组，在进行区间操作时，能够快速定位和处理块内数据，实现高效的查询和修改功能 。

## 二、分治算法（Divide and Conquer）：问题分解与求解的经典范式
### 2.1 分治算法的基本概念与理论体系
分治算法是一种基于递归的算法设计范式，其核心思想是将一个规模较大、难以直接解决的复杂问题，分解为若干个规模较小、相互独立且与原问题类型相同或相似的子问题；然后递归地求解这些子问题；最后将子问题的解合并起来，得到原问题的解。该算法的执行过程可概括为三个关键步骤：
1. **分解（Divide）**：把原问题划分为若干个规模更小的子问题，确保子问题之间相互独立，且子问题的解法与原问题类似。
2. **解决（Conquer）**：通过递归调用自身，分别求解各个子问题。当子问题规模足够小时，直接得出其解。
3. **合并（Combine）**：将各个子问题的解按照一定的规则进行整合，从而得到原问题的最终解。

分治算法的有效性依赖于问题本身所具备的特性，包括：问题能够分解为相同类型的子问题；子问题之间相互独立，不存在重叠部分；存在明确的递归终止条件，避免无限递归；子问题的解可以通过合理的方式合并为原问题的解。

### 2.2 经典分治算法示例与性能分析
#### 2.2.1 归并排序（Merge Sort）
```cpp
#include <vector>
using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    // 合并两个有序子数组
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    // 复制剩余元素
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    // 回写到原数组
    for (int p = 0; p < k; p++) {
        arr[left + p] = temp[p];
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);      // 分解：排序左半部分
    mergeSort(arr, mid + 1, right); // 分解：排序右半部分
    merge(arr, left, mid, right);   // 合并：合并两个有序部分
}
```
归并排序的时间复杂度为 \( O(n \log n) \) ，其中 \( n \) 为待排序数组的长度。无论数组初始状态如何（有序、逆序或随机），其时间复杂度都保持稳定，这使得它在对时间复杂度有严格要求且数据规模较大的场景中表现出色。其空间复杂度为 \( O(n) \) ，主要用于临时存储合并过程中的数据。

#### 2.2.2 快速排序（Quick Sort）
```cpp
int partition(vector<int>& arr, int left, int right) {
    int pivot = arr[right]; // 选择最右元素作为基准
    int i = left - 1;
    
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[right]);
    return i + 1;
}

void quickSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int pi = partition(arr, left, right); // 分解：分区操作
        quickSort(arr, left, pi - 1);         // 解决：排序左子数组
        quickSort(arr, pi + 1, right);        // 解决：排序右子数组
    }
}
```
快速排序的平均时间复杂度为 \( O(n \log n) \) ，但在最坏情况下（如数组已经有序且每次选择的基准都是最值），时间复杂度会退化为 \( O(n^2) \) 。其空间复杂度在平均情况下为 \( O(\log n) \) ，依赖于递归调用栈的深度；在最坏情况下为 \( O(n) \) 。尽管快速排序存在最坏情况，但由于其平均性能优秀，并且在实际应用中可以通过随机选择基准等方式减少最坏情况的发生，因此在排序算法中被广泛使用。

## 三、字典树（Trie）：字符串处理的高效数据结构
### 3.1 字典树的基本概念与特性分析
字典树，又称前缀树或单词查找树，是一种树形数据结构，专门用于高效存储和检索字符串集合。它的设计理念基于字符串的公共前缀特性，通过将具有相同前缀的字符串共享树中的相同路径，极大地减少了存储空间和查询时间。

从结构上看，字典树是一棵多叉树，每个节点代表一个字符，从根节点到叶节点的一条路径对应一个字符串。例如，存储字符串集合{"apple", "app", "apply", "banana"}，在字典树中，"apple"、"app"和"apply"会共享前三个字符"app"对应的路径，只有在后续字符不同时才产生分支。这种结构使得字典树在字符串检索、拼写检查、自动补全、IP路由（最长前缀匹配）等场景中具有显著的优势。

### 3.2 字典树的实现代码与操作解析
```cpp
#include <bits/stdc++.h>
using namespace std;

// 定义数组最大长度
const int MAXN = 1e5 + 5;
// 定义每个数的二进制位数
const int MAX_BIT = 30;

// 存储输入的数字
int nums[MAXN];
// 字典树节点总数
int cnt = 0;
// 字典树，每个节点有两个子节点（0 和 1）
int trie[MAXN * 31][2];

// 插入一个数到字典树中
void insert(int x) {
    int p = 0;
    // 从最高位到最低位遍历 x 的二进制表示
    for (int i = MAX_BIT; i >= 0; i--) {
        int bit = (x >> i) & 1;
        // 如果该位对应的子节点不存在，则创建一个新节点
        if (!trie[p][bit]) {
            trie[p][bit] = ++cnt;
        }
        // 移动到下一个节点
        p = trie[p][bit];
    }
}

// 查询与 x 异或结果最大的数
int query(int x) {
    int p = 0;
    int res = 0;
    // 从最高位到最低位遍历 x 的二进制表示
    for (int i = MAX_BIT; i >= 0; i--) {
        int bit = (x >> i) & 1;
        // 尝试走与当前位相反的路径
        if (trie[p][bit ^ 1]) {
            res |= (1 << i);
            p = trie[p][bit ^ 1];
        } else {
            // 若相反路径不存在，则走当前位路径
            p = trie[p][bit];
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        insert(nums[i]);
    }
    int ans = 0;
    // 遍历每个数，找出最大异或结果
    for (int i = 0; i < n; i++) {
        ans = max(ans, query(nums[i]));
    }
    cout << ans << endl;
    return 0;
}    
```
上述代码实现了基于字典树的最大异或查询功能。`insert`函数将数字的二进制表示插入字典树，通过逐层遍历二进制位，创建或沿着已有的路径前进；`query`函数则利用字典树的结构，尝试找到与给定数字异或结果最大的数，通过优先选择与当前位相反的路径，充分发挥了字典树在处理前缀相关问题上的优势。

### 3.3 字典树的操作复杂度分析
|操作类型|操作描述|时间复杂度|空间复杂度|说明|
|----|----|----|----|----|
|插入操作|将一个字符串插入字典树|O(L)|O(L)|L为字符串长度，需遍历字符串每个字符创建或查找节点|
|搜索操作|在字典树中查找特定字符串|O(L)|O(1)|只需沿着对应字符路径查找，不占用额外空间|
|前缀查询|查找所有以给定字符串为前缀的字符串|O(L + K)|O(1)|L为前缀长度，K为满足条件的字符串数量，遍历前缀后统计子树节点|

## 四、莫队算法（Mo's Algorithm）：离线区间查询的高效解决方案
### 4.1 莫队算法的基本概念与核心思想
莫队算法是由莫涛提出的一种用于高效处理离线区间查询问题的算法。所谓离线处理，是指在算法执行前，所有的查询操作都已知，算法可以根据这些查询的特点进行预处理和优化。该算法的核心思想融合了分块思想和滑动窗口技术：
1. **离线处理**：将所有查询预先存储，通过对查询进行特殊排序，为后续优化奠定基础。
2. **分块思想**：对查询的左端点进行分块排序，同一块内的查询再按右端点排序（奇偶块采用不同的排序方向），这种排序方式能够减少区间转移时的操作次数。
3. **滑动窗口**：通过维护一个当前区间，并根据查询需求调整区间的左右端点，利用前一个查询的结果来加速当前查询的计算，避免重复计算。

莫队算法适用于满足以下条件的问题：问题可以离线处理；查询区间 \([L, R]\) 的结果能够通过增减左端点 \( L \) 或右端点 \( R \) 来转移；转移操作的时间复杂度为 \( O(1) \) 或可接受的低复杂度，如在统计区间内不同元素个数等问题中，添加或删除一个元素对结果的影响可以快速计算。
### 4.2 莫队算法实现
#### 4.2.1 基本框架（C++实现）
```cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
// 分块大小设为数据规模的平方根，这是经过理论和实践验证的较优选择
const int BLOCK_SIZE = sqrt(MAXN);

struct Query {
    int l, r, id;
    // 重载小于号，定义查询排序规则
    bool operator<(const Query& other) const {
        // 先按左端点所属块号升序排序
        if (l / BLOCK_SIZE != other.l / BLOCK_SIZE)
            return l < other.l;
        // 同一块内，根据块号奇偶性决定右端点升序或降序排序
        return (l / BLOCK_SIZE & 1) ? (r < other.r) : (r > other.r);
    }
};

int a[MAXN];        // 原始数组，存储问题相关数据
int ans[MAXN];      // 存储每个查询的答案
Query queries[MAXN]; // 查询数组

// 向当前区间添加元素pos时的处理逻辑，需根据具体问题实现
void add(int pos) {
    // 添加a[pos]到当前区间
}

// 从当前区间移除元素pos时的处理逻辑，需根据具体问题实现
void remove(int pos) {
    // 从当前区间移除a[pos]
}

void mo_algorithm(int q) {
    // 对所有查询按照自定义规则排序
    sort(queries, queries + q);
    
    int curL = 1, curR = 0; // 当前区间初始为空
    for (int i = 0; i < q; i++) {
        int L = queries[i].l, R = queries[i].r;
        
        // 调整当前区间[curL, curR]到目标区间[L, R]
        while (curL > L) add(--curL);
        while (curR < R) add(++curR);
        while (curL < L) remove(curL++);
        while (curR > R) remove(curR--);
        
        // 计算并记录当前查询的答案
        ans[queries[i].id] = current_ans; 
    }
}
```
在上述代码中，`Query`结构体用于存储每个查询的左端点 `l`、右端点 `r` 以及查询的编号 `id`。`add` 和 `remove` 函数是莫队算法的核心自定义操作，需要根据具体问题进行实现，例如在统计区间内不同颜色的球的数量问题中，`add` 函数要处理新加入球对不同颜色数量统计的影响，`remove` 函数则要处理移除球后的影响 。`mo_algorithm` 函数先对查询进行排序，然后通过滑动窗口的方式依次处理每个查询，利用上一个查询的区间状态，通过调整左右端点，高效地计算出当前查询的结果。

#### 4.2.2 关键组件说明
1. **分块排序**：
    - 将查询左端点按块号排序，使得相邻的查询尽量在同一个块或者相邻的块中，减少区间跨越块的次数。
    - 同一块内按右端点排序（奇偶块不同方向），这样的排序策略能让区间的右端点在处理同一块内的查询时尽可能地单调移动，减少左右端点的来回跳跃，从而降低计算开销。以一个包含10个查询的序列为例，若不进行这样的排序，在处理查询时，区间端点可能会频繁地大幅度移动；而经过分块排序后，区间端点的移动会更加有序和高效 。
2. **转移函数**：
    - `add(pos)`：将位置`pos`的元素加入当前区间，在具体问题中，可能涉及到更新某些统计量。比如在统计区间内不同元素个数的问题中，若新加入的元素是区间内首次出现，需要将不同元素个数加1。
    - `remove(pos)`：将位置`pos`的元素移出当前区间，同样需要根据具体问题更新相关统计量。例如在上述问题中，若移除的元素是区间内唯一的该元素，那么不同元素个数需要减1。
3. **指针移动**：
    - 四个`while`循环调整当前区间`[curL, curR]`到目标区间`[L, R]`。通过逐步增加或减少左端点`curL`、右端点`curR`，利用已有的计算结果，避免对每个查询都重新计算整个区间，从而提高算法效率。

### 4.3 复杂度分析
1. **时间复杂度**：
    - 设`n`为元素数量，`q`为查询数量。
    - **排序**：使用标准库的排序函数，其时间复杂度为O(`q` log `q`)。
    - **左指针移动**：
        - 块内移动：每次查询最多O(`BLOCK_SIZE`)，因为同一块内左端点的移动范围不会超过块的大小。
        - 跨块移动：最多O(`n`)，整个过程中左端点跨越块的次数不会超过数据规模`n`。
        - 总计：O(`q` * `BLOCK_SIZE` + `n`)。
    - **右指针移动**：
        - 块内：由于分块排序的策略，右端点在块内是单调移动的，总计O(`n`)。
        - 跨块：最多O(`n` / `BLOCK_SIZE` * `n`)，当`BLOCK_SIZE = sqrt(n)`时，这部分复杂度为O(`n * sqrt(n)`)。
        - 当取`BLOCK_SIZE` = sqrt(`n`)时，总时间复杂度为O((`n` + `q`) * sqrt(`n`))，相比一些暴力解法，在处理大量区间查询时效率有显著提升。
2. **空间复杂度**：
    - O(`n`)用于存储原始数据，即数组`a[MAXN]`。
    - O(`q`)用于存储查询和答案，包括查询数组`queries[MAXN]`和答案数组`ans[MAXN]`，整体空间占用较为合理 。

### 4.4 完整实现示例
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n, m, a[maxn];
int belong[maxn];//belong[i]代表i这个数是第几块 
int siz[maxn];//siz[i]代表第i块有几个数 
int mx[maxn];//mx[i]代表第i块所有数的最大值
int delta[maxn];//delta[i]代表第i块整体被加了多少 
int cnt[maxn], ans = 0;
struct query{
    int l,r,id,ans;
};
query q[maxn];

// 定义查询排序规则，先按左端点所属块号排序，同块内按右端点升序排序
bool cmp1(const query &q1,const query &q2){
    if(belong[q1.l] != belong[q2.l]) return belong[q1.l]<belong[q2.l];
    else return q1.r<q2.r;
}

// 向当前区间插入元素x，更新相关统计量
void ins(int x){
    cnt[x]++;
    if(cnt[x] % 2 == 1){
        ans++;
    } else {
        ans--;
    }
}

// 按查询编号排序，方便输出结果
bool cmp2(const query &q1,const query &q2){
    return q1.id<q2.id;
}

// 从当前区间删除元素x，更新相关统计量
void del(int x){
    cnt[x]--;
    if(cnt[x]!=0){
        if(cnt[x]%2==0) ans++;
        else ans--;
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    } 
    int block_size = sqrt(n);
    for(int i = 1; i <= n; i++) {
        belong[i] = (i - 1) / block_size + 1;
    }
    for(int i = 1; i <= m; i++){
        cin>>q[i].l>>q[i].r;
        q[i].id = i;
    }
    // 对查询进行排序
    sort(q + 1, q + m + 1, cmp1);
    for(int i = q[1].l; i <= q[1].r; i++){
        ins(a[i]);
    }
    q[1].ans = ans;
    for(int i = 2; i <= m; i++){
        int l1 = q[i - 1].l, r1 = q[i - 1].r;
        int l2 = q[i].l, r2 = q[i].r;
        // 根据上一个查询和当前查询的区间，调整当前区间
        if(l1 < l2){
            for(int j = l1; j < l2; j++){
                del(a[j]);
            }
        } else {
            for(int j = l2; j < l1; j++){
                ins(a[j]);
            }
        }
        if(r1 < r2){
            for(int j = r1 + 1; j <= r2; j++){
                ins(a[j]);
            }
        } else {
            for(int j = r2 + 1; j <= r1; j++){
                del(a[j]);
            }
        }
        q[i].ans = ans;
    }
    // 按查询编号排序输出结果
    sort(q + 1, q + m + 1, cmp2);
    for(int i = 1; i <= m; i++) {
        cout << q[i].ans << endl;
    }
    return 0;
}
```
在这个完整示例中，问题设定为统计区间内出现奇数次的元素个数。`ins`函数实现了插入元素时对统计量`ans`的更新，`del`函数实现了删除元素时的更新。通过莫队算法的分块排序和滑动窗口操作，高效地处理了所有区间查询，最终按查询编号顺序输出结果 。