# **1 数据结构**
在计算机科学中，**数据结构**是计算机中存储、组织数据的方式。其实只要是用来存储数据的结构，都可以叫做数据结构，例如**数组**。数据结构与**算法**是紧密相关的，正确的数据结构选择可以提高算法的效率。在计算机程序设计的过程中，选择适当的数据结构是一项重要工作。许多大型系统的编写经验显示，程序设计的困难程度与最终成果的质量与表现，取决于是否选择了最适合的数据结构。
**抽象数据类型（ADT）**是计算机科学中具有类似行为的特定类别的数据结构的数学模型或者具有类似语义的一种或多种程序设计语言的数据类型。抽象数据类型是间接定义的，通过其上的可执行的操作以及这些操作的效果的数学约束（与可能的代价）。
在竞赛中，重要的不是数据结构本身，而是使用数据结构的**方法**。
# **2 常见数据结构**
## **2.1 堆栈(stack)**
**堆栈**又称为**栈**或**堆叠**，是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（top）进行加入数据（push）和移除数据（pop）的运算。这和自助餐馆中堆叠的盘子，箱子中的一堆书类似。
堆栈按照**后进先出**（Last In First Out）的原理运作。可对其进行如下的操作：
- **推入（push）**：将数据放入堆栈顶端，堆栈顶端移到新放入的数据。
- **弹出（pop）**：将堆栈顶端数据移除，堆栈顶端移到移除后的下一数据。
- **查询栈顶（top）**：返回堆栈顶端数据的信息。
- **判断栈是否为空（empty）**：判断堆栈是否为空并返回这个信息。
我们常用数组来实现一个堆栈。创建数组$stack$和变量$tot$，$stack$充当堆栈的容器，存放元素；$tot$初始化为$0$，用来表示堆栈的元素个数并充当栈顶指针。请看代码。
```cpp
int stack[SIZE],tot=0; //SIZE为预设堆栈大小
#define top (stack[tot])
#define pop (tot--)
#define push(x) (stack[++tot]=(x))
#define empty (!tot)
```
C++的`stack`库提供了`stack`类模板。它的空间占用是动态的，不需要预先设定，操作的常数比自己手写要大。下面列出它的使用方法，请看代码。
```cpp
// stack<type,container> identifier;
// 创建元素类型为type，底层容器为container的stack类变量identifier，建议container使用vector来获取最佳性能
// 创建一个元素类型为int的 stack
stack<int> s;
// 向 stack 顶部推入元素
s.push(25);
s.push(13);
// 查询 stack 顶部元素
cout<<s.top(); //13
// 弹出 stack 顶部元素
s.pop();
// 判断 stack 是否为空
cout<<s.empty(); //0
// 输出 stack 的元素个数
cout<<s.size(); //1
```
关于更多使用方法以及操作的时间复杂度，请自行查阅`cppreference`。
## 2.2 队列(queue)
**队列**，又称为**伫列**，是计算机科学中的一种抽象数据类型，只允许在后端（rear）进行插入操作，在前端（front）进行删除操作。这和超市收银台前的队列，食堂打饭的队列类似。
队列按照**先进先出**（First In First Out）的原理运作。它有如下的操作：
- **推入（push）**：将数据插入队列后端，队尾指针移到新放入的数据。
- **弹出（pop）**：将队列前端数据移除，队首指针移到移除后的下一数据。
- **查询队首（front）**：返回队列前端数据的信息。
- **判断队列是否为空（empty）**：判断队列是否为空并返回这个信息。
我们同样用数组来实现一个队列。创建数组$queue$和变量$fnt$与$rer$，$queue$充当队列的容器；$fnt$初始化为$0$，用来表示队首指针；$rer$初始化为$-1$，用来表示队尾指针。请看代码。
```cpp
int queue[SIZE],fnt=0,rer=-1; //SIZE为预设队列大小
#define top (queue[fnt])
#define pop (fnt++)
#define push(x) (queue[++rer]=(x))
#define empty (fnt>rer)
```
这种写法存在着问题。可以发现随着队列的推入和弹出操作，$fnt$的位置在不断后移。$fnt$前的内存空间都是无法使用到的，被浪费的空间。如果推入操作次数过多，那么就会造成**伪溢出**，也就是数组明明还有空间，但却无法使用这些空间。为了解决这个问题，我们通过取模的方式来使得队列形成一个循环结构。这种队列叫做循环队列，它有效的解决了伪溢出的问题。但是在这种方法下队列大小依然是个固定值，存储的数据数不能超过队列大小。请看代码。
```cpp
int queue[SIZE],fnt=0,rer=-1; //SIZE为预设队列大小
#define front (queue[fnt%SIZE])
#define pop (fnt++)
#define push(x) (queue[(++rer)%SIZE]=(x))
#define empty (fnt>rer)
```
C++的`queue`库提供了`queue`类模板。它的空间占用是动态的，不需要预先设定，操作的常数比自己手写的要大。下面列出它的使用方法，请看代码。
```cpp
// queue<type,container> identifier;
// 创建元素类型为type，底层容器为container的queue类变量identifier，建议container使用deque来获取最佳性能
// 创建一个元素类型为int的 queue
queue<int> q;
// 向 queue 尾部推入元素
q.push(25);
q.push(13);
// 查询 queue 首部元素
cout<<q.front();
// 弹出 queue 首部元素
q.pop();
// 判断 queue 是否为空
cout<<q.empty(); //0
// 输出 queue 的元素个数
cout<<q.size(); //1
```
关于更多使用方法以及操作的时间复杂度，请自行查阅`cppreference`。
## **2.3 数组(array)**
在计算机科学中，**数组数据结构**，简称**数组**，是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。数组也是很多其他数据结构实现中所用到的数据结构。
数组大家都会用，不过多阐述。
## **2.4 链表(linked list)**
**链表**是一种常见的数据结构，它不像数组那样，按线性顺序存储数据，而是在每一个结点里存指向下一个结点的指针(pointer)。这种就类似于排队的时候找到自己位置的一个方法就是记住自己在谁旁边。由于不需要按线性顺序存储数据，链表在插入的时候可以达到$O(1)$的复杂度，但是查找一个结点或者访问特定编号的结点则需要$O(n)$的时间。
使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机查询的优点，同时由于链表增加了结点的指针域，空间开销比较大。
链表中最简单的一种是**单向链表**。单向链表的结构是在每个结点保存数据和到下一个结点的地址，在最后一个结点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个结点的指针，有的时候也会同时储存指向最后一个结点的指针。一般查找一个结点的时候需要从第一个结点开始每次访问下一个结点，一直访问到需要的位置。但是也可以提前把一个结点的位置另外保存起来，然后直接访问。单向链表只可向一个方向遍历。
<p><div align="center"><img src="https://www.waltz26.cn/upload/2021/02/408px-Singly-linked-list.svg-8972743e88784e4386f4d1fe30748275.png" /></div></p>
一种更复杂的链表是**双向链表**。每个结点有两个连接：一个指向前一个结点，当此“连接”为第一个“连接”时，指向空值；而另一个指向下一个结点，当此“连接”为最后一个“连接”时，指向空值。
<p><div align="center"><img src="https://www.waltz26.cn/upload/2021/02/610px-Doubly-linked-list.svg-259132b02e414582894bf466747d945a.png" /></div></p>
双向链表中不仅有指向后一个结点的指针，还有指向前一个结点的指针。这样可以从任何一个结点访问前一个结点，当然也可以访问后一个结点。
下面来实现单向链表。首先是写链表结点的结构体。结构体包含两类信息，一个是我们存储的数据信息$key$，另一个是指针信息$next$。我们可以另外给这个结构体写一个构造函数方便开辟新结点时的初始化。请看代码。
```cpp
struct node //链表结点
{
int key;
node* next;
node(int _key,node* _next) //构造函数
{
key=_key;
next=_next;
}
};
```
然后是建表。这里有一个需要考虑到的问题：当链表中插入第一个元素时建表真的方便吗？我认为那是不够方便的，因为你要加上一个特判，并且每次创建新头结点时所得到的地址都将会不一样。所以在这里用了一个叫虚拟结点的东东，它来充当我们的结节点，以上的问题就没有了。请看代码。
```cpp
node *head=new node(0,NULL); //用虚拟节点来充当头结点
```
接下来实现查询功能。从链表的头结点出发，遍历链表直到找到存有我们要查询的值的那个结点。请看代码。
```cpp
bool linkedlist_find(node *head,int key) //查询
{
for(node* p=head->next;p;p=p->next)
if(p->key==key) return 1;
return 0;
}
```
再接下来实现插入功能。从链表的头结点出发，遍历链表直到找到我们要插入的那个位置的前一个位置的结点，创建一个新结点，将新结点的指针值改为后一个位置的结点的地址，再将该结点的指针值改为新结点的地址。请看代码。
```cpp
void linkedlist_insert(node *head,int key,int pos) //插入,位置从1开始
{
int i=1;
for (node* p=head;p;p=p->next,i++)
{
if (i==pos)
{
node* target=new node(key,p->next);
p->next=target;
return;
}
else ;
}
cout<<"Error pos!\n";
}
```
最后实现删除功能。从链表的头结点出发，遍历链表直到找到我们要删除的那个位置的前一个位置的结点，然后修改该结点的指针值为下一个位置的结点的指针值，最后删除下一个位置的结点的内存空间。请看代码。
```cpp
void linkedlist_delete(node *head,int pos) //删除，位置从1开始
{
int i=1;
for (node* p=head;p->next;p=p->next,i++)
{
if (i==pos)
{
p->next=p->next->next;
delete(p->next);
return;
}
else ;
}
cout<<"Error pos!\n";
}
```
链表写起来比较复杂，容易出错，所以非常有必要写一个检查函数，请看代码。
```cpp
void linkedlist_debug(node *head) //检查
{
for(node* p=head->next;p;p=p->next)
printf("Node[%p] key=%d next=%p\n",p,p->key,p->next);
}
```
C++的`list`库提供了`list`类模板。它的空间占用是动态的，不需要预先设定，操作的常数比自己手写的要大。下面列出它的使用方法，请看代码。
```cpp
// list<type> identifier;
// 创建元素类型为type的list类变量identifier
// 创建一个元素类型为int的 list
list<int> l;
// 向 list 头部插入元素
l.push_front(25);
// 向 list 尾部插入元素
l.push_back(13);
// 删除 list 头部元素
l.pop_front();
// 删除 list 尾部元素
l.pop_back();
// 判断 list 是否为空
cout<<l.empty(); //1
// 输出 list 的元素个数
cout<<l.size(); //0
// 清空 list
l.clear();
```
关于更多使用方法以及操作的时间复杂度，请自行查阅`cppreference`。
| 操作 | 数组 | 链表 |
| :------: | :----: | :----: |
| 插入 | $O(n)$ | $O(1)$ |
| 随机存取 | $O(1)$ | $O(n)$ |
## **2.5 图和树(graph&tree)**
后续的文章将会单独拿出来讨论，这里不做介绍。
## **2.6 堆(heap)**
**堆**是计算机科学中的一种特别的**完全二叉树**。若是满足以下特性，即可称为堆。给定堆中任意结点$F$和$S$，若$P$是$S$的父结点，那么$F$的值会小于等于（或大于等于）$S$的值。若父结点的值恒小于等于子结点的值，此堆称为最小堆；反之，若父结点的值恒大于等于结点的值，此堆称为最大堆。在堆中最顶端的那一个结点，称作根结点，根结点没有父结点。
在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。C++的`queue`提供的`priority_queue`类模板一般就是由**二叉堆**实现的。下面介绍二叉堆的实现。
首先需要了解一下完全二叉树的性质：
1. 具有$n$个结点的完全二叉树的深度为$\lceil{log_2n+1}\rceil$。
2. 编号为$k$的结点的左右子结点（如果有）的编号为$2k$和$2k+1$。
3. 编号为k的结点的父节点（如果有）的编号为$\lfloor\frac{k}{2}\rfloor$。
堆支持的基本操作有：
1. **插入（insert）**：在堆尾（完全二叉树中最后一个编号的结点的下个编号结点位置）插入元素，并依据堆性质上滤（percolate up）。
2. **删除（delete）**：删除堆顶（完全二叉树中的根结点）元素，堆尾元素移到堆顶，并依据堆性质下滤（percolate down）。
3. **查询堆顶（top）**：返回堆顶数据的信息。
我们来写一个小根堆。完全二叉树可以用数组来存储，请看代码。
```cpp
int heap[SIZE]; //SIZE为堆的大小
int heap_size; //记录当前堆的大小，初始化为0
```
插入操作分为两个部分：插入元素和上滤。对于一个要插入的元素，我们在堆尾加入这个元素，把堆尾结点设置为当前遍历结点，比较当前结点和其父结点的大小，如果当前结点值比父结点小，那么交换两个结点的位置，并重复比较操作；如果当前结点值比父节点大或者等于，那么结束比较操作。请看代码。
```cpp
void heap_insert(int x)
{
int now,fa;
heap[now=++heap_size]=x;
while (now!=1)
{
fa=now/2;
if (heap[now]<heap[fa])
{
swap(heap[now],heap[fa]);
now=fa;
}
else break;
}
}
```
删除部分分为三个部分：删除堆顶元素，将堆尾元素移到堆尾和上滤。我们直接将堆尾元素代替堆顶元素，把堆顶结点设置为当前遍历结点，比较当前结点和其左右子结点的大小，如果当前结点值比左右子结点小，那么结束比较操作；如果当前结点值比左右子结点大或者等于，那么交换两个结点的位置，并重复比较操作。请看代码。
```cpp
void heap_delete(void)
{
int now=1,son;
heap[1]=heap[heap_size--];
while (now*2<=heap_size)
{
son=now*2;
if (son<heap_size&&heap[son+1]<heap[son]) son++;
if (heap[now]>heap[son])
{
swap(heap[now],heap[son]);
now=son;
}
else break;
}
}
```
查询堆顶即堆的首个元素。请看代码。
```cpp
#define top heap[1]
```
C++的`queue`库提供了`priority_queue`类模板。它的空间占用是动态的，不需要预先设定，操作的常数比自己手写的堆要大。下面列出它的使用方法，请看代码。
```cpp
// prirority_queue<type,container,compare> identifier;
// 创建元素类型为type，底层容器为container，比较器为compare的priority_queue类变量identifier，建议container使用vector来获取最佳性能
// 创建一个元素类型为int，大根堆的 priority_queue
priority_queue<int> q;
priority_queue<int,vector<int>,less<int>> q;
// 创建一个元素类型为int，小根堆的 priority_queue
priority_queue<int,vector<int>,greater<int>> q;
// 向 priority_queue 尾部推入元素
q.push(25);
q.push(13);
// 查询 priority_queue 首部元素
cout<<q.top();
// 弹出 priority_queue 首部元素
q.pop();
// 判断 priority_queue 是否为空
cout<<q.empty(); //0
// 输出 priority_queue 的元素个数
cout<<q.size(); //1
```
关于更多使用方法以及操作的时间复杂度，请自行查阅`cppreference`。
## **2.7 散列表(hash table)**
**散列表**，也叫**哈希表**，是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查询速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名$x$到首字母$F(x)$的一个函数关系），在首字母为$W$的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则$f:x\to F(x)$，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。
对不同的关键字可能得到同一散列地址，即$k_{1}\neq k_{2}$，而$f(k_1)=f(k_2)$，这种现象称为**冲突**（collision）。具有相同函数值的关键字对该散列函数来说称做**同义词**。
散列表的核心是散列函数的构造，散列函数有以下常见的构造：
1. **直接定址法**：取关键字或关键字的某个线性函数值为散列地址。即$F(x)=x$或$F(x)=k\cdot a+b$，其中$a,b$为常数。
2. **模数法**：取关键字被某个不大于散列表长度$size$的数$p$除后所得的余数为散列地址。即$F(x)=x\%p$，其中$p\leq size$。$p$一般取素数或$size$，若$p$选择不好，容易产生冲突。
3. **进制法**：假设关键字可按顺序分为$s$个部分单值，且每个单值都有相同的固定取值范围大小$r$，那么散列函数可以这样设定：$F(x)=x[s-1]\cdot r^{s-1}+...+x[0]*r^0$，其中$x[i]$表示对应位置的取值减去该位置的可取最小值。
**字符串哈希**便可用进制法+模数法来构造。请看代码。
```cpp
string s;
int key=0;
cin>>s;
for (auto i:s)
key=(key*256+i)%SIZE; //SIZE为散列表大小
```
冲突是影响散列表使用的最大因素。为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理。而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。常用方法有以下几种：
1. **开放定址法**：$hash[i]=F(x)+d[i](0<i<m)$，其中i为已发生冲突的次数，$hash[i]$为冲突i次下的散列地址，$F(x)$为散列函数，$d$为增量序列，$m$为散列表大小。根据增量序列的不同分为**线性**，**平方**和**伪随机**探测。这种解决方法是无错的，但会产生问题。**聚集**（cluster）是在函数地址的表中，散列函数的结果不均匀地占据表的单元，形成区块，造成线性探测产生一次聚集（primary clustering）和平方探测的二次聚集（secondary clustering），散列到区块中的任何关键字需要查找多次试选单元才能插入表中，解决冲突，造成时间浪费。对于开放定址法，聚集会造成性能的灾难性损失，是必须避免的。
2. **单独链表法**：将散列到同一个存储位置的所有元素保存在一个链表中。
3. **双散列**：加多一个另外的散列函数形成双约束。
4. **再散列**：$hash[i]=F(hash[i-1])$，其中$i$为已发生冲突的次数，$hash[i]$为冲突$i$次下的散列地址，$F(x)$为散列函数。这种方法不易产生聚集，但增加了计算时间并且很有可能造成死循环。
# 3 常见数据结构思想延申
## 3.1 前缀表达式与后缀表达式
**前缀表达式**和**后缀表达式**相当于是对**表达式树**进行递归遍历中的**先序遍历**和**后序遍历**得到的序列。
先序遍历是先遍历父节点再遍历左右子结点，所以可知在前缀表达式中运算符在运算对象的前面，并且运算顺序是从序列右端到左端。后序遍历正好反过来（但不是序列反过来）。
在前缀表达式中，最先出现的运算符优先级最低，其后的运算符优先级依次增高。运算符后紧跟的两个数据（可能是数字也可能是运算符，每个运算符可以把它当式子来看）是它的运算对象。我们在进行计算时，通常都是先计算优先高的式子，所以可以反过来从右到左对式子进行计算。根据前缀表达式的性质显然可以用堆栈来处理，从右到左对前缀表达式进行遍历，遇到数字就推入堆栈；遇到运算符就弹出两个数字进行计算并将结果推入堆栈（因为运算符本身也可以是运算对象，它所对应的式子计算的结果可以把它代替）。后缀表达式就是从左到右进行遍历。
下面是后缀表达式计算的一个实例，题目是[[洛谷]P1449 后缀表达式](https://www.luogu.com.cn/problem/P1449)。请看代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
stack<int> s;
int main()
{
char c;
while ((c=getchar())!='@')
{
if (c>='0'&&c<='9')
{
int ans=0;
do
ans=ans*10+c-'0';
while ((c=getchar())!='.');
s.push(ans);
}
else
{
int a,b;
a=s.top();
s.pop();
b=s.top();
s.pop();
if (c=='+') s.push(a+b);
else if (c=='-') s.push(b-a);
else if (c=='*') s.push(a*b);
else s.push(b/a);
}
}
cout<<s.top()<<'\n';
return 0;
}
```
## 3.2 出栈序列与卡特兰数
给出一个**入栈序列**和**出栈序列**，问这个出栈序列是否是入栈序列可能的一个出栈序列？
这种是典型的堆栈模拟，利用堆栈的性质来模拟判断。设置一个位置标记$pos$，初始化为出栈序列的第一个位置。从左到右遍历入栈序列，然后将入栈序列的元素不断推入堆栈，每次推入后判断栈顶元素是否与出栈系列$pos$位置元素相同，如果相同那就将栈顶元素弹出并且$pos$往后一个位置，并重复操作直到条件不再满足。遍历结束后如果堆栈中没有元素，那么这个出栈序列就是正确的；如果堆栈中有元素，那么这个出栈序列就是错误的。
下面是一个实例，题目是[[洛谷]P4387 验证栈序列](https://www.luogu.com.cn/problem/P4387)。请看代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
stack<int> s;
int a[1000005],b[1000005];
int main()
{
int q;
cin>>q;
while (q--)
{
int n;
cin>>n;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<=n;i++)
cin>>b[i];
int pos=1;
for (int i=1;i<=n;i++)
{
s.push(a[i]);
while (!s.empty()&&s.top()==b[pos])
{
pos++;
s.pop();
}
}
if (s.empty()) cout<<"Yes\n";
else cout<<"No\n";
while (!s.empty()) s.pop();
}
return 0;
}
```
给定一个出栈序列，可能的出栈序列有多少个呢？
假设正处于堆栈模拟的某个状态，此时已推入$i$个数据，弹出$j$个数据，记到此状态的可能情况总数为$status[i][j]$，那么有这个关系：
$$
status[i][j]=status[i-1][j](i=j) \\
status[i][j]=status[i-1][j]+status[i][j-1](i>j)
$$
求出栈序列的总数就是$status[n][n]$，$n$为序列长度。那么这个递推式就可以看作是求平面直角坐标系中点$(0,0)$到点$(n,n)$的总路径数，在只能走$y=x$这条直线以下区域的条件下。
计算得到的数字有一个名字：**卡特兰数**(catalan number)。它的通项公式是：
$$
C_n=\frac{\begin{pmatrix}
n\\
2n
\end{pmatrix}}{n+1}
$$
## 3.3 数组模拟链表
链表的结点也可以通过数组来进行特定方式存储。这是将非特定方式存储做法中的内存空间映射到数组空间中，这种做法优点是可以自动获得一个附加数据：索引，能够进行$O(1)$的随机查询；缺点是不能动态的分配内存。这种做法有时候被叫做**数组模拟链表**，但是事实上只是用表示在数组中的位置的下标索引代替了指向内存地址的指针，这种索引其实也是逻辑上的指针，整个结构还是链表，并不算是被模拟的（但是可以说成是**用数组实现的链表**）。
链表结点的结构体有一些不同，虚拟结点的设立也有些区别，请看代码。
```cpp
struct node //链表结点
{
int key,next;
}linkedlist[SIZE];
//索引0是NULL
linkedlist[1].key=0;
linkedlist[1].next=0;
```
对于链表的三个操作，由于数组模拟链表使用索引来充当地址，所以链表的三个操作不再需要遍历链表来找到操作位置，转而以索引作为参数。由于是索引作参数，三个操作的编写是指定索引的，故依题意特别的编写。
## 3.4 通过堆优化贪心算法
有些题目的贪心算法解法中会有每次从数据流中取最大或最小值的进行操作并将结果返回数据流的过程，如果使用排序去获得最大或最小值的话那么会非常耗费时间。这时运用堆去获得这个最大或最小值就是很好的一个方法。例如在单源最短路径的**Dijsktra算法**中就可以通过使用堆来优化其时间复杂度到$O(nlogn)$ 。
# 4 C++STL提供的其他数据结构容器
## **4.1 自动扩展容量数组(vector)**
C++的`vector`库提供了`vector`类模板。`vector`相当于一个可变长数组。它的空间占用是动态的，不需要预先设定。下面列出它的使用方法，请看代码。
```cpp
// vector<type> identifier;
// 创建元素类型为type的vector类变量identifier;
// 创建一个元素类型为int的 vector
vector<int> v;
// 向 vector 尾部推入元素
v.push_back(25);
v.push_back(13);
// 删除 vector 尾部元素
v.pop_back();
// 判断 vector 是否为空
cout<<v.empty(); //0
// 输出 vector 的元素个数
cout<<v.size(); //1
// 清空 vector
v.clear();
```
关于更多使用方法以及操作的时间复杂度，请自行查阅`cppreference`。
## **4.2 集合(set)**
C++的`set`库提供了`set`类模板。`set`的功能如其名。它的空间占用是动态的，不需要预先设定。下面列出它的使用方法，请看代码。
```cpp
// set<type> identifier;
// 创建元素类型为type的set类变量identifier
// 创建一个元素类型为int的 set
set<int> s;
// 向 set 中插入元素
s.insert(25);
s.insert(13);
// 判断 set 是否为空
cout<<s.empty(); //0
// 输出 set 的元素个数
cout<<s.size(); //2
// 清空 set
s.clear();
```
还有一些位于`alogrithm`库中的函数：
- `includes`：若一个集合是另一个的子集则返回$true$。
- `set_difference`：计算两个集合的差集。
- `set_intersection`：计算两个集合的交集。
- `set_union`：计算两个集合的并集。
关于更多使用方法以及操作的时间复杂度，请自行查阅`cppreference`。
## **4.3 双端队列(deque)**
C++的`deque`库提供了`deque`类模板。`deque`是一个可在首尾推入弹出的队列。它的空间占用是动态的，不需要预先设定。下面列出它的使用方法，请看代码。
```cpp
// deque<type> identifier
// 创建元素类型为type的deque类变量identifier
// 创建一个元素类型为int的 deque
deque<int> d;
// 向 deque 尾部推入元素
d.push_back(25);
d.push_back(13);
// 向 deque 首部推入元素
d.push_front(25);
d.push_front(13);
// 查询 deque 首部元素
cout<<d.front();
// 查询 deque 尾部元素
cout<<d.back();
// 弹出 deque 首部元素
d.pop_front();
// 弹出 deque 尾部元素
d.pop_back();
// 判断 deque 是否为空
cout<<d.empty(); //0
// 输出 deque 的元素个数
cout<<d.size(); //2
// 清空 deque
d.clear();
```
关于更多使用方法以及操作的时间复杂度，请自行查阅`cppreference`。
## **4.4 关联(map)**
C++的`map`库提供了`map`类模板。`map`相当于一个索引和元素可以是任何类型的数组，`map`重载了`[]`运算符。它的空间占用是动态的，不需要预先设定。下面列出它的使用方法，请看代码。
```cpp
// map<type1,type2> identifier
// 创建元素类型type1关联元素类型type2的map类变量identifier
// 创建一个元素类型为char关联元素类型int的 map
map<char,int> m;
// 在 map 中创建一个关联
// 中括号中的内容称为键
m['A']=25;
m['B']=13;
// 删除 map 中对应键元素
m.erase('A');
// 判断 map 是否有此键
cout<<m.count('A'); //0
// 判断 map 是否为空
cout<<m.empty(); //0
// 输出 map 的元素个数
cout<<m.size(); //1
// 清空 map
m.clear();
```
关于更多使用方法以及操作的时间复杂度，请自行查阅`cppreference`。
# 5 序列
**序列**是被排成一列的对象。序列里，每个元素不是在其他元素之前，就是在其他元素之后。这里，元素之间的顺序非常重要。一个给定序列的**子序列**是从给定序列中去除一些元素，而不改变其他元素之间相对位置而得到的。
**序列信息**就是与序列元素相关的信息，例如单个元素的值，一段元素的和。**区间**是指序列中连续的一段元素的集合，通常以$[l,r](l<=r)$来表示区间。序列信息满足结合律是可区间查询的**充要条件**。
- **（结合律）**序列信息对于运算符$\bigotimes$，满足$a \bigotimes b \bigotimes c=(a \bigotimes b) \bigotimes c=a \bigotimes (b \bigotimes c)$。
# **6 序列方法-预处理**
## 6.1 只有大小关系的序列信息
对于只有大小关系的序列信息，可以通过**离散化**处理来减小序列信息的值域。
## 6.2 离散化
离散化，就是把无限空间中有限的个体映射到有限的空间中去。通俗的说，离散化是在不改变数据**相对大小**的条件下，对数据范围即值域进行相应的缩小。例如：
- $1,999,100000,15\to1,3,4,2$。
- $\{100,200\},\{20,50000\},\{1,400\}\to\{3,4\},\{2,6\},\{1,5\}$。
实现离散化需要两个基本算法：**排序算法**和**二分查找算法**。首先对序列进行排序，然后去重，最后用二分查找将编号与序列信息链接。请看代码。
```cpp
for (int i=1;i<=n;i++)
b[i]=a[i];
sort(a+1,a+n+1);
int m=unique(a+1,a+n+1)-(a+1); //去重
for (int i=1;i<=n;i++)
b[i]=lower_bound(a+1,a+m+1,b[i])-a;
```
还有一种不去重离散化，只需要用到排序算法，请看代码。
```cpp
/*
bool cmp(const int &x,const int &y)
{
return a[x]<a[y];
}
*/
for (int i=1;i<=n;i++)
b[i]=i;
sort(b+1,b+n+1,cmp);
```
## **6.3 可减的序列信息**
对于满足**可减**的序列信息，一切区间查询都可以转化为**前缀和**来查询，一切区间修改都可以转化为**差分**来修改。
- **（可减）**：序列信息可以进行减法或除法运算。
## **6.4 前缀和**
如果一个序列$s$与$a$满足：
$$
s_0=0 \\
s_i=s_{i−1}+a_i (i>0)
$$
那么序列$s$称为序列$a$的前缀和。对于任意查询区间$[l,r]$元素和，可以$O(1)$时间得到：$sum=s_r-s_{l-1}$。前缀和常见问题有：
- 给定一个序列，$m$次询问，每次询问区间$[l,r]$的元素和。
- 给定一个序列，$m$次询问，每次询问$[l,r]$的模$P$下的元素积。
## 6.5 差分
如果一个序列$d$与$a$满足：
$$
d_0=0 \\
d_i=a_i-a_{i-1} (i>0)
$$
那么序列$d$称为序列$a$的差分，而序列$a$正好是序列$d$的前缀和。对于任意区间$[l,r]$元素加值$d$，可以$O(1)$时间进行：将$b_l$加上$d$，将$b_{r+1}$减去$d$。差分常见问题有：
- 给定一个序列，$m$次修改，每次对区间$[l,r]$执行区间加，最后询问所得序列。
- 给定一个序列，$m$次修改，每次对区间$[l,r]$执行模$P$区间乘，最后询问所得序列。
## **6.6 二阶差分与二阶前缀和**
对于下面这个问题：
- 给定一个序列，$m$次修改，每次对区间$[l,r]$执行区间加等差数列（首项为$a_1$，公差为$d$），最后询问所得序列。
容易想到的是进行多次差分修改，但如果修改区间长度很大且修改次数也很多这个修改时间就不是$O(1)$的了。正确的方法是使用**二阶差分**。
- 原序列：$[0,0,0,0,0,0,0]$。
- 序列区间加等差数列：$[0,1,3,5,7,9,0]$。
- 新序列一阶差分：$[0,1,2,2,2,2,-9]$。
- 新序列二阶差分：$[0,1,1,0,0,0,-11]$。
观察后发现，修改区间长度为$len$，二阶差分就是$[0,a_1,d-a_1,0,0,0,-(a_1+len*d)]$，得到这个结果之后只需要修改二阶差分数组，然后求**二阶前缀和**就可以了。请看代码。
```cpp
int a[100005],b[100005],c[100005]; //原序列，一阶差分数组，二阶差分数组
int main()
{
int n;
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i]-a[i-1];
c[i]=b[i]-b[i-1];
}
int l,r,a1,d;
cin>>l>>r>>a1>>d;
c[l]+=a1;
c[l+1]+=d-a1;
c[r+1]-=a1+(r-l)*d;
for (int i=1;i<=n;i++)
{
b[i]=b[i-1]+c[i];
a[i]=a[i-1]+b[i];
cout<<a[i]<<' ';
}
return 0;
}
```
## **6.7 可快速合并的序列信息**
考虑一个序列的**分治树**，对于每个节点，预处理出所有形如$[l,m]$或$[m+1,r]$的子区间的信息，其中$m$为节点对应的区间的中点。这个过程的复杂度为$O(nlogn)$。对于任何区间查询$[l,r]$，分治树上都存在一个对应区间包含$[l,r]$，且中点$m$在$[l,r]$内的节点。找到这个节点，将预处理的$[l,m]$和$[m+1,r]$的信息合并，即可得到询问的答案。直接查找这个节点的复杂度是$O(logn)$，可以将序列长度扩充至最近的$2$的幂，利用**倍增**思想将查找复杂度优化至$O(1)$。
对于**可重复贡献问题**,使用**ST表**更加简便和快速。
## **6.8 RMQ问题**
- 给定一个序列，$m$次询问，每次询问区间$[l,r]$的最小/最大值。
这是一个很典型的序列问题，称为**RMQ问题**。我们该如何去解决这个问题？
## **6.9 倍增**
倍增，通过字面意思来看就是翻倍。它能够使线性的处理转化为对数级的处理。来看一个启发题：
- 如何用尽可能少的砝码称量出$[1,32]$之间的所有重量？（只能在天平的一端放砝码）
答案是使用$[1,2,4,8,16]$这五个砝码，可以称量出$[1,31]$之间的所有重量。同样，如果要称量$[1,127]$之间的所有重量，可以使用$[1,2,4,8,16,32,64]$这七个砝码。每次我们都选择$2$的整次幂作砝码的重量，就可以使用极少的砝码个数量出任意我们所需要的重量。
为什么说是极少呢？因为如果我们要量出$[1,1023]$之间的所有重量，只需要$9$个砝码，需要量出$[1,1048575]$之间的所有重量，只需要$19$个。如果我们的目标重量翻倍，砝码个数只需要增加1。这叫“对数级”的增长速度，因为砝码的所需个数与目标重量的范围的对数成正比。（**用3为什么不行？**）
利用2的整次幂的**对数级**的增长速度，加上序列信息的可快速合并性，就可利用倍增来对序列进行预处理优化查询。RMQ问题就是倍增求解的一个典型例子。设序列$a$和数组$f$，满足以下条件：
$$
f_{i,j}=min_{k \in [j,j+2^i)} a_k
$$
$f_{i,j}$表示从下标$i$开始长度为$2^i$的一段区间的最小值，可以得出以下递推式：
$$
f_{i,j}=min(f_{i−1,j},f_{i−1,j+2^{i−1}})
$$
预处理数组$f$的时间复杂度为$O(nlogn)$。对于询问区间$[l,r]$，设$s=⌊log(r−l+1)⌋$，则答案为$f_{s,l}$和$[l+2^s,r]$的答案的最小值。请看代码。
```cpp
int f[20][100005];
int main()
{
int n;
cin>>n;
for (int i=1;i<=n;i++)
cin>>f[0][i];
for (int j=1;j<17;j++) //预处理
for (int i=1;i+(1<<(j-1))<=n;i++)
f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
int l,r;
cin>>l>>r;
int i=l;
int minn=INT_MAX;
for (int j=16;~j;j--)
if (r-l+1&1<<j)
{
minn=min(minn,f[j][i]);
i+=1<<j;
}
cout<<minn<<'\n';
}
```
## **6.10 ST表**
ST表是在倍增的基础上，解决可重复贡献问题的数据结构。
- **（可重复贡献问题）**：是指对于运算$\bigotimes$，满足$x \bigotimes x=x$，则对应的区间询问就是一个可重复贡献问题。例如，最大值有$max(x,x)=x$，最大公约数有$gcd(x,x)=x$，所以**RMQ**和**区间GCD**问题就是一个可重复贡献问题。区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。
继续来看上面的倍增，由于RMQ问题是一个可重复贡献问题，于是$min(f_{s,l},f_{s,r−2^ s+1})$就是答案。只要能$O(1)$算出$s$，就能$O(1)$处理询问。
```cpp
int f[20][100005];
int lg2[100005];
int main()
{
int n;
cin>>n;
int t=0;
for (int i=1;i<=n;i++) //初始化log2
{
if (i>=(1<<(t+1))) t++;
lg2[i]=t;
}
for (int i=1;i<=n;i++)
cin>>f[0][i];
for (int j=1;j<17;j++) //预处理
for (int i=1;i+(1<<(j-1))<=n;i++)
f[j][i]=max(f[j-1][i],f[j-1][i+(1<<(j-1))]);
int l,r;
cin>>l>>r;
int s=log2(r-l+1);
cout<<min(f[s][l],f[s][r-(1<<s)+1])<<'\n';
}
```
# 7 序列方法-线性结构
## 7.1 2-pointer
**2-pointer双指针**是一种对于一维问题的**枚举**，同时存在两个指针在一维序列上扫描而得名。2-pointer分为两种：
- **对撞指针**：基于数据有序的条件下使用，一般用来查找一定条件的两个数，指针朝相反方向移动。
- **快慢指针**：像一个滑动窗口，一般用来解决满足条件的最短区间或最长区间问题，指针朝一个方向移动。
一般来说，2-pointer的题目都非常容易识别出来。
## **7.2 单调栈**
如果一个堆栈满足栈内元素满足**单调递减**或**单调递增**，那么这个堆栈称为**单调栈**。如何构造一个单调栈呢，我们通过模拟一组数据来帮助我们：
- 序列：$[2,5,7,4,2]$。
- 目标：构造一个单调递增栈。
- 过程：
1. 栈空，将$2$推入堆栈。
2. $5$推入堆栈仍满足单调递增，将$5$推入堆栈。
3. $7$推入堆栈仍满足单调递增，将$7$推入堆栈。
4. $4$推入堆栈就不满足单调递增，弹出栈内元素直到$4$推入堆栈仍满足单调递增。
5. $2$推入堆栈就不满足单调递增，弹出栈内元素直到$2$推入堆栈仍满足单调递增。
模拟一遍之后单调栈就非常好写了。请看代码。
```cpp
//单调递增栈
stack<int> s;
int a[SIZE];
int main()
{
int n;
cin>>n;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<=n;i++)
{
while (!s.empty()&&s.top()>a[i]) s.pop();
s.push(a[i]);
}
return 0;
}
```
单调栈处理序列的时间复杂度为$O(n)$，因为序列元素最多入栈一次，出栈一次。单调栈可以用来维护序列范围最值。
## **7.3 单调队列**
如果一个队列满足队内元素满足**单调递减**或**单调递增**，那么这个队列称为**单调队列**。如何构造一个单调队列呢，我们通过模拟一组数据来帮助我们：
- 序列：$[2,5,7,4,2]$。
- 目标：构造一个长度为$2$的单调递增队列。
- 过程：
1. 队空，将$2$推入队列。
2. $5$推入队列仍满足单调递增，将$5$推入队列。
3. $7$推入队列仍满足单调递增，将$7$推入队列，此时队列长度超过$2$，弹出队首。
4. $4$推入队列就不满足单调递增，弹出队尾元素直到$4$推入队列仍满足单调递增。
5. $2$推入队列就不满足单调递增，弹出队尾元素直到$2$推入队列仍满足单调递增。
模拟一遍之后单调队列就非常好写了，不过由于要支持弹出队尾的操作，所以需要使用**双端队列**。请看代码。
```cpp
deque<int> q;
int a[SIZE];
int main()
{
int n,k; //k为单调队列长度
cin>>n>>k;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<=n;i++)
{
while (!q.empty()&&q.back()>a[i]) q.pop_back();
q.push_back(a[i]);
while (!q.empty()&&q.size()>k) q.pop_front();
}
return 0;
}
```
单调队列处理序列的时间复杂度为$O(n)$，因为序列元素最多入队一次，出队一次。单调队列可以用来维护序列范围最值。
# 8 序列方法-树形结构
## 8.1 线段树
**线段树**是一种树形数据结构，1977年由**Jon Louis Bentley**发明，用以实现高效区间修改和区间查询。使用线段树的一个前提是序列信息可快速合并。
线段树即是序列的一个分治树。在线段树中每个结点表示的区间由以下规则确定（序列长度为$n$）：
- 根结点表示区间$[1,n]$。
- 结点表示的区间为$[l,r]$ ，且$l\neq r$ ，则其有左右$2$个子结点，取$m=⌊\frac{l+r}{2}⌋$ ，左子结点表示 $[l, m]$ ，右子结点表示$[m + 1,r]$ 。
对于一个序列长度为$8$的序列，其构建的线段树如下：
<p><div algin="center"><img src="https://www.waltz26.cn/upload/2021/03/graph-7abf6f0b8d3c4d9e8f51e4d8846bdcc5.png" /></div></p>
观察可得以下结论：
- 每一层的结点所表示的区间长度是上一层的结点所表示的区间长度的一半。
- 树高为$\left \lceil logn \right \rceil+1$。
- 结点数为$2n-1$。
如何构建线段树呢？我们常使用的是堆式建树的方法，也就是将线段树补全为完全二叉树。补全为完全二叉树后，就可以通过完全二叉树的编号方式来快速访问左右子结点。将线段树补全为完全二叉树，结点数不会超过原来的$2$倍，所以数组一般开$4n$的长度。请看代码。
```cpp
//宏定义，减少代码量
#define L (k<<1)
#define R (L+1)
#define M (l+r>>1)
int a[SIZE],f[SIZE*4]; //数组a表示序列，数组f表示维护的序列信息
void update(int k) //更新
{
//更新要维护的序列信息
}
void build(int l,int r,int k) //建树
{
if (l==r) //当前结点是叶子结点
f[k]=a[l]=a[r];
else
{
build(l,M,L); //左子树
build(M+1,r,R); //右子树
update(k); //向上更新
}
}
```
建树的过程是先不断的递归左右子树直到当前结点为叶子结点，然后将叶子结点赋予序列的元素值，最后在返回的过程中通过左右子结点的序列信息不断更新当前结点的序列信息。代码涉及了两个函数，来介绍下其形参表示的意义：
- $l,r$表是当前遍历结点所表示的区间的左右边界。
- $k$表示当前遍历结点的编号。
线段树应当支持三种操作：单点修改，区间查询，区间修改。下面将逐一介绍。
对于单点修改，我们的方法是向下查找该结点，将该结点位置的值修改后，向上更新。请看代码。
```cpp
void change_point(int l,int r,int u,int k)
{
if (l==r)
{
//修改
return;
}
if (u<=M)
change_point(l,M,u,L);
if (u>M)
change_point(M+1,r,u,R);
update(k);
}
```
对于区间查询，我们的方法是寻找尽可能少的不相交区间使其并集为$[l,r]$ 。从上往下进行寻找。 涂有绿色的结点表示该结点所表示的区间包含$[l,r]$。可知这样的不相交区间最多有$树高-1$，那么区间查询的时间复杂度为$O(logn)$。每一层绿色的结点不超过两个。例如下图表示的是修改区间$[4,6]$。
<p><div algin="center"><img src="https://www.waltz26.cn/upload/2021/03/graph-2ed7e363f39b4e3db1e89e4c0ee5f3b4.png" /></div></p>
请看代码。
```cpp
void ask_interval(int l,int r,int u,int v,int k)
{
if (u<=l&&v>=r)
return f[k];
int res; //res用来合并答案
if (u<=M)
//合并ask_interval(l,M,u,v,L)的答案
if (v>M)
//合并ask_interval(M+1,r,u,v,R)的答案
return res;
}
```
对于区间修改，我们的方法也是寻找尽可能少的不相交区间使其并集为$[l,r]$。但在这里就有一个问题，当修改了一个结点所表示的区间的值时，其子树所包含的结点所表示的区间的值也要改变，如果把这些结点全都进行修改，那么时间花费会比较大。例如修改区间$[1,8]$，这时候要对所有结点遍历一遍。
为了解决这一问题，前人引出了懒惰标记。懒惰标记将子树结点修改的操作交给后面的遍历，也就是在下次遍历到这些要修改的结点的时候再对其进行修改，这个修改是一个滞后的修改。这样区间修改的时间复杂度就和区间查询的时间复杂度一样是$O(logn)$。
例如修改区间[4,6]（如下图所示，其中涂了橙色的结点表示结点所表示的区间被包含在修改区间，灰色表示经过修改之后值不正确的结点。），假设修改操作是将区间的所有元素都加上一值$d$（并且维护的序列信息是区间和），我们找到这些并集为$[l,r]$ 的不相交区间，将对应结点的值加上$区间长度\times d$，并且给其懒惰标记的值加上$d$。
<p><div algin="center"><img src="https://www.waltz26.cn/upload/2021/03/graph%20(1)-082f85e789ab4a9c8b14608c710ea285.png" /></div></p>
请看代码。
```cpp
int lazy[SIZE*4];
void update(int k)
{
f[k]=f[L]+f[R];
}
void change_interval(int l,int r,int u,int v,int d,int k)
{
if (u<=l&&v>=r)
{
f[k]+=(r-l+1)*d;
lazy[k]+=d; //上懒惰标记
return;
}
if (u<=M)
change_interval(l,M,u,v,d,L);
if (v>M)
change_interval(M+1,r,u,v,d,R);
update(k); //别忘了向上的时候要更新
}
```
接下来是实现在下次遍历到需要修改的结点的时候更新结点的值，这一部分称为懒惰标记的**下放**，我们将其封装为一个`push_down`函数，请看代码。
```cpp
void push_down(int l,int r,int k) //下放
{
//更新子结点的值
f[L]+=lazy[k]*(M-l+1);
f[R]+=lazy[k]*(r-M);
//给子结点加上懒惰标记
lazy[L]+=lazy[k];
lazy[R]+=lazy[k];
//将标记消除
lazy[k]=0;
}
```
哪些操作会有遍历呢？单点修改，区间查询和区间修改。那么就需要在这些操作中添加`push_down`函数。请看代码（注意是对于上面的问题编写的）。
```cpp
void change_point(int l,int r,int u,int d,int k)
{
if (l==r)
{
f[k]+=d;
return;
}
push_down(l,r,k);
if (u<=M)
change_point(l,M,u,d,L);
if (u>M)
change_point(M+1,r,u,d,R);
update(k);
}
int ask_interval(int l,int r,int u,int v,int k)
{
if (u<=l&&v>=r)
return f[k];
push_down(l,r,k);
int res=0; //res用来合并答案
if (u<=M)
res+=ask_interval(l,M,u,v,L);
if (v>M)
res+=ask_interval(M+1,r,u,v,R);
return res;
}
void change_interval(int l,int r,int u,int v,int d,int k)
{
if (u<=l&&v>=r)
{
f[k]+=(r-l+1)*d;
lazy[k]+=d; //上懒惰标记
return;
}
if (u<=M)
change_interval(l,M,u,v,d,L);
if (v>M)
change_interval(M+1,r,u,v,d,R);
update(k); //别忘了向上的时候要更新
}
//可以发现，我们在递归之前push_down，在递归之后update。
```
将所有代码片段合并起来。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define SIZE 100005
//宏定义，减少代码量
#define L (k<<1)
#define R (L+1)
#define M (l+r>>1)
int a[SIZE],f[SIZE*4]; //数组a表示序列，数组f表示维护的序列信息
int lazy[SIZE*4];
void update(int k)
{
f[k]=f[L]+f[R];
}
void build(int l,int r,int k) //建树
{
if (l==r) //当前结点是叶子结点
f[k]=a[l];
else
{
build(l,M,L); //左子树
build(M+1,r,R); //右子树
update(k); //向上更新
}
}
void push_down(int l,int r,int k) //下放
{
//更新子结点的值
f[L]+=lazy[k]*(M-l+1);
f[R]+=lazy[k]*(r-M);
//给子结点加上懒惰标记
lazy[L]+=lazy[k];
lazy[R]+=lazy[k];
//将标记消除
lazy[k]=0;
}
void change_point(int l,int r,int u,int d,int k)
{
if (l==r)
{
f[k]+=d;
return;
}
push_down(l,r,k);
if (u<=M)
change_point(l,M,u,d,L);
if (u>M)
change_point(M+1,r,u,d,R);
update(k);
}
int ask_interval(int l,int r,int u,int v,int k)
{
if (u<=l&&v>=r)
return f[k];
push_down(l,r,k);
int res=0; //res用来合并答案
if (u<=M)
res+=ask_interval(l,M,u,v,L);
if (v>M)
res+=ask_interval(M+1,r,u,v,R);
return res;
}
void change_interval(int l,int r,int u,int v,int d,int k)
{
if (u<=l&&v>=r)
{
f[k]+=(r-l+1)*d;
lazy[k]+=d; //上懒惰标记
return;
}
if (u<=M)
change_interval(l,M,u,v,d,L);
if (v>M)
change_interval(M+1,r,u,v,d,R);
update(k); //别忘了向上的时候要更新
}
//可以发现，我们在递归之前push_down，在递归之后update。
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,q;
cin>>n>>q;
for (int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
while (q--)
{
int cmd,x,y,d;
cin>>cmd;
switch (cmd)
{
case 1: //区间修改
cin>>x>>y>>d;
change_interval(1,n,x,y,d,1);
break;
case 2: //区间查询
cin>>x>>y;
cout<<ask_interval(1,n,x,y,1)<<'\n';
break;
}
}
return 0;
}
```
这段代码对应的就是下面这个问题:
- 给定一个序列。
- $m$次询问，每次询问区间$[l,r]$的元素和。
- $m$次修改，每次对区间$[l,r]$执行区间加。
- 询问和修改可以在任意阶段。
线段树的代码虽然很长，但是通过对其进行分部分的设计，还是能很轻松的写好的。下面总结了设计的基本思路：
- 要维护的序列信息。
- 懒惰标记的设计。
- 序列信息的合并方法。
## 8.2 懒惰标记的可合并性
懒惰标记是有先后顺序的。线段树要求懒惰标记可合并，也就是两次修改可以化为一次修改（一个例子就是取模，对$3$取模然后对$4$取模，这两次取模就不可以化为一次取模）。懒惰标记的**可合并性**中常见的是**可加性**与**覆盖性**。
- **（可加性）**新的标记可以加到原来的标记上。
- **（覆盖性）**新的标记可以覆盖原来的标记。
## 8.3 懒惰标记组
有些题目不止有一种区间修改操作，这时候如果只用一个懒惰标记往往是无法描述这些区间修改操作的。可以使用**懒惰标记组**来表示这些区间修改。来看一个问题：
- 给定一个序列。
- $m$次询问，每次询问区间$[l,r]$的元素和。
- $m$次修改，每次对区间$[l,r]$执行区间加。
- $m$次修改，每次对区间$[l,r]$执行区间乘。
- 询问和修改可以在任意阶段。
怎么用线段树去解决这一问题？按照我们的设计思路，首先明确要维护的序列信息，易知是区间元素和。接下来进行懒惰标记的设计。问题同时要求了加和乘的区间修改，这是两种不同的区间修改，不能通过一个懒惰标记来描述。使用懒惰标记组来表示这两种修改：创建一个懒惰标记组，记为$(add,mul)$，其中$add$表示加的标记，$mul$表示乘的标记。
下放的三个部分是：子结点的值的更新，懒惰标记的合并，懒惰标记的消除。
设子结点的值为$son$，子结点表示的区间的长度为$len$，子结点的值的更新有两种方式：
- $son*mul+add*len$，先乘后加。
- $(son+add*len)*mul$，先加后乘。
讨论第一种影响。懒惰标记组的合并就类似于懒惰标记的合并，这里是满足可加性的，设要合并的两个懒惰标记组为$(add_1,mul_1)$和$(add_2,mul_2)$，合并后的懒惰标记组为$(add,mul)$，那么得到懒惰标记组的合并关系：
- $(\times mul_1+add_1)\times mul_2+add_2=\times mul+add$，
- $mul=mul_1\times mul_2$，
- $add=add_1\times mul_2+add_2$。
现在可以写出我们的`push_down`函数了。
```cpp
#define L (k<<1)
#define R (L+1)
#define M (l+r>>1)
int lazy_add[SIZE*4],lazy_mul[SIZE*4];
void push_down(int l,int r,int k) //下放
{
//更新子结点的值
f[L]=f[L]*lazy_mul[k]+lazy_add[k]*(M-l+1);
f[R]=f[R]*lazy_mul[k]+lazy_add[k]*(r-M);
//给子结点加上懒惰标记
lazy_mul[L]*=lazy_mul[k];
lazy_mul[R]*=lazy_mul[k];
lazy_add[L]=lazy_add[L]*lazy_mul[k]+lazy_add[k];
lazy_add[R]=lazy_add[R]*lazy_mul[k]+lazy_add[k];
//将标记消除
lazy_add[k]=0;
lazy_mul[k]=1;
}
```
来正式的描述这个过程。设懒惰标记组$(a,b)$：
1. 规定懒惰标记组对区间$[l,r]$的更新为$AFF\{[l,r],(a,b)\}$（上例中是$AFF\{[l,r],(a,b)\}=\times a+b\times (r-l+1)$）；
2. 将$AFF\{[l,r],(a,b)\}$式子中的$l,r$去掉，即为懒惰标记组对单点的更新，也是懒惰标记组的合并单元（类比于懒惰标记）。
3. 确定合并后懒惰标记组的元与合并前的懒惰标记组的元的关系，要满足一定关系才可以。
4. 最后确定懒惰标记组的元的初始值。
对于此更新：
- $(son+add*len)*mul$，先加后乘。
是不可行的，步骤$3$可得：
- $[(+add_1\times mul_1)+add_2]\times mul_2=+add\times mul$，
- $mul=mul_1\times mul_2$，
- $add=add_1+add_2/mul_1$。
$add$的式子中使用了合并前的$mul_1$，因为区间修改并不是由懒惰标记组描述的那样进行的，所以是不可行的。
B3A1-数据结构
