写在开头
- 数据结构可有多种实现方式，如链表可以使用指针加结构体实现，栈与队列可以直接用STL中的容器，但本课程讲解的主要是如何使用数组模拟数据结构，原因如下：
- 效率高，比如指针和结构体模拟链表（动态列表）每次都要new一个新节点，但是new的速度非常慢
- 数据结构的用处：
- 在一群数字里查找最大（最小）值————堆
- 集合的合并————并查集
- 维护一个有序列表————平衡树（set）
- 维护区间最大值、区间和————树状数组、线段树
单链表（数组模拟（静态链表
适用问题：
- 用数组模拟的单链表写邻接表（链式前向星）：
- 邻接表是把每个点的邻边都存下来，它的形式就是n个单链表，每个单链表的头结点下标位置存储在head[]数组中，head[i]表示存储第i个点的邻边的链表的头结点下标
- 邻接表用途：存储图和树
组成元素：
- 开头是一个头结点（用head表示头结点下标（地址））
- 每个结点都包含一个value值（用e[]表示）和一个指向下一个节点的next指针（用ne[]表示，存储下一个节点的下标（地址））
- 最后一个节点指向空结点（用ne[i]=-1表示一个节点指向空结点）
- 括号内是用数组实现链表的习惯表示方法
特点：
- 可以在O(1)时间内找到下一个点，但是如果想找上一个点只能从头遍历
模板：
int e[N], ne[N]; // 链表元素及下个结点的下标（地址）
int head; // 头结点下标（地址）
int idx; // 当前哪个下标可用，每用一次都idx++
/** 创建不含头结点的单链表 */
void init() {
head = -1; //指向空结点
idx = 1; // 第1个结点的下标从1开始
}
/** 创建含下标为0的头结点的单链表 */
void init() {
head = 0;
// 头结点
e[0] = 0; // 可以使用头结点的值存储链表长度
ne[0] = -1;
idx = 1; // 第1个结点的下标从1开始
}
/** 向链表头部插入一个值为x数 */
void insert_head(int x) {
e[idx] = x;
ne[idx] = head;
head = idx++;
e[0]++; // 链表长度+1
}
/** 向链表头部（头结点后）插入一个值为x数 */
void insert_head(int x) {
e[idx] = x;
ne[idx] = ne[head];
ne[head] = idx++;
e[0]++; // 链表长度+1
}
/** 在下标为k的位置后插入一个值为x的数 */
void insert(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
e[0]++; // 链表长度+1
}
/** 删除下标为k的节点的后面的一个节点 */
void remove(int k) {
ne[k] = ne[ne[k]];
e[0]--; // 链表长度-1
}
/** 删除头节点 */
void remove_head() {
head = ne[head];
e[0]--; // 链表长度-1
}
/** 遍历链表 */
void print() {
for (int i = ne[head]; i != -1; i = ne[i]) cout << e[i] << " ";
}
说明：
- 采用含头结点的单链表，头结点存储链表长度
- 元素从下标
1开始存储
双链表（数组模拟
组成元素：
- 头结点（用下标是0的节点表示）和尾结点（用下标是1的节点表示）
- 每个结点都包含一个value值（用e[]表示）和两个指针（l[]指向左边的节点、r[]指向右边的节点）
- 括号内是用数组实现链表的习惯表示方法
模板：
const int N = 100010;
int e[N], l[N], r[N], idx;
/** 创建双链表（含头结点和尾结点） */
void init() {
//下标为0表示头结点，下标为1表示尾结点
r[0] = 1; // 头结点的右边是尾结点
l[1] = 0; // 尾结点的左边是头结点
idx = 2; //第一个可用的下标是2
}
/** 在下标为k的结点右侧插入一个结点 */
void insert(int k, int x) {
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx++;
}
//调用方法：
//在k的右边插入一个节点：insert(k,x);
//在k的左边插入一个节点：insert(l[k],x);
//在最左边插入一个节点：add(0, x);
//在最右边插入一个节点：add(l[1], x);
/** 删除下标为k的结点 */
void remove(int k) {
r[l[k]] = r[k];
l[r[k]] = l[k];
}
/** 输出 */
void print() {
for (int i = r[0]; i != 1; i = r[i]) printf("%d ", e[i]);
}
说明：
- 实现的双链表含头结点和尾结点，下标分别为
0和1 insert()函数可根据参数的选取实现在链表任意位置插入的功能（包括头插和尾插）- 遍历时从头结点的下一个位置开始（
r[0]），直到遍历到尾结点（下标为0）
模拟栈（数组模拟
组成元素：
- stk[]存储栈内元素
- tt存储栈顶下标，初始为0，第一个元素从1开始表示
模板：
int stk[N], tt = 0; // tt表示栈顶
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空
if (tt) not empty // tt>0则栈不为空
else empty
说明：
- 栈从下标
1开始存储元素 - 栈指针
tt的值可表示栈的实际长度
表达式求值（模拟栈计算中缀表达式
思路:
- 将中缀表达式看作一颗二叉树
- 计算时若一个运算符节点的子树全部遍历完毕，则可将其运算符对应的子表达式计算出结果，然后用这个结果代替这个运算符节点
- 先遍历左子树，然后遍历右子树，左右子树都遍历完之后就计算根节点的指，然后用结果代替节点值，继续向上遍历
- 可以树形结构做这个题，可以使用栈
- 但是使用栈的话，如何判断某棵子树已被遍历完？ 答：当前运算符优先级>=上一个运算符优先级，如果>=就把之前的式子计算一下结果，计算完的结果压入数字栈，将新运算符压入操作符栈，否则把运算符直接压入操作符栈（这样一来被压入栈的运算符的优先级从栈底到栈顶一定是严格单调递增的）
- 左括号直接入栈，遇到右括号时从栈顶开始执行计算过程并弹出栈顶操作符，直到遇到左括号，弹出左括号(左括号上面的操作符优先级从左括号开始往上到栈顶一定是严格单调递增的，所以从顶向下计算不会引起歧义)
模板：
#include<stack>
#include<unordered_map>
#include<cctype>
#include<string>
//适用于仅有双目运算符的中缀表达式
unordered_map<char, int>pr{{'+',1},{'-',1},{'*',2},{'/',2},{'^',3};//定义操作符优先级，主函数部分模板的代码逻辑与操作符具体是什么无关，因此此处定义只要与calc函数相匹配即可，无需考虑主函数部分会不会出错
stack<int> num;//操作数栈
stack<char> op;//操作符栈
void calc(){
int b=num.top();num.pop();
int a=num.top();num.pop();//操作数要反着读入
char c=op.top();op.pop();//读入操作数
int x;
// 依据操作符种类不同进行不同计算
if(c=='+')x=a+b;
else if(c=='-')x=a-b;
else if(c=='*')x=a*b;
else if(c=='/')x=a/b;
else if(c=='^')x=(int)pow(a,b);
//else {} //如果有其他种类操作符就继续定义num.push(x);//结果压入操作数栈
}
int main(){
string str;
cin>>str;//读入中缀表达式
for(int i=0;i<str.sisze();i++){//从头开始遍历中缀表达式
char c = str[i];
if(isdigit(c)){//如果是数字
int x=0,j=i;
while(j,str.size()&&isdigit(str[j]))x=x*10+str[j]-'0';//获取这个数
i=j-1;//双指针
num.push(x);//压入操作数栈
}
else if(c=='(')op.push(c);//左括号直接入栈
else if(c==')'){
while(op.top()!='(')calc();//执行计算直到遇到左括号
op.pop();//弹出左括号
}
else{
while(op.size()&&op.top!='('&&pr[op.top()]>=pr[c])calc();//当操作符栈不为空且栈顶操作符不是左括号且栈顶操作符优先级大于等于当前新操作符时循环执行计算操作
op.push(c);//将当前新操作符压入栈
}
}
while(op.size())calc();//当操作符栈还有操作符时，循环执行计算操作直至栈空
cout<<num.top();//此时操作数栈顶就是结果
return 0;
}
模拟队列
普通队列
组成元素：
- q[]存储栈内元素
- hh存储队头下标，初始为0
- tt存储队尾下标，初始为-1
模板：
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 取队头的值
q[hh];
// 取队尾的值
q[tt];
// 判断队列是否为空
if (hh > tt) empty //hh>tt则队列为空
else not empty
说明：
tt + 1 - hh可表示队列长度
循环队列
模板：
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh == tt){...}
说明：
- 这种实现方式与普通队列方式有点区别，在这里是先存入，后
++，故tt初值为0 - 可以把入队改成
q[tt] = x; tt = (tt + 1) % N;，出队改成hh = (hh + 1) % N; x = q[hh]; - 队满判断可用
(tt + 1) % N == hh - 队列长度可用
(tt - hh + N) % N求出
单调栈
用途：
常见题型：为每个数找出满足如下条件的数：
- 在它某一侧（左边或右边）
- 距离最近
- 比它小（大）
思路：
- 考虑方式与双指针类似，先想暴力怎么写，然后从中挖掘某个性质，使得可以将目光集中到某些状态里面，从而降低时间复杂度
- 当序列中出现逆序对时，对于已经扫描过的序列，逆序对中较大的那个数永远不会被用到，所以每当扫描到下一个数时，就将维护的栈从栈顶开始出栈直到将扫描到的新数加进栈顶时依旧能使维护的栈处于单调状态
- 单调栈优化之后看似是两重循环，其实每个数最多进栈一次最多出栈一次
模板：
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
int x;
cin>>x;
while (tt && check(stk[tt], x)) tt -- ;//check函数找到的是与x相比不满足单调性质的栈顶元素
//这里写题目操作
stk[ ++ tt] = x;
}
说明：
- 使用单调栈优化后每个元素最多进栈一次，每个元素最多出栈一次
- 时间复杂度由$O(n^2)$降为$O(n)$
单调队列
用途：
找出滑动窗口中的最大值（最小值），单调思想与单调栈相似，注意判断队头是否滑出窗口
模板：
int q[N];//队列元素是不是存下标比较好
int hh = 0, tt = -1;
//单调队列中的元素是目前窗口中的元素的子集
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;//弹出加入新元素后不满足单调性质的尾部元素直到加入新元素后队列仍然单调
q[ ++ tt] = i;//在队尾加入新元素
//单调增队列队头是窗口最大值
//单调减队列队头是窗口最小值
//这里写题目操作
}
说明：时间复杂度由$O(nk)$降为$O(n+k)$
KMP
思路：
- 依然是先思考暴力做法，然后优化
- 利用已经匹配过的部分的额外信息进行优化
- next[]数组含义：
- next[]数组维护的是以此下标为终点的前缀与后缀最长相等长度
- next[i]=j 等同于 p[1,j]=p[i-j+1,i]
- next标识符可能被某个头文件用过，保险起见使用ne[]
- 下标问题：
- 匹配过程中，i表示当前文本串s[]中正在匹配的位置，j表示模式串p[]中已经匹配成功的最后一个位置，也就是说，此时s[i]应该和p[j+1]尝试匹配，所以初始值i=1,j=0，s[]和p[]均从下标1开始存储
- 时间复杂度：O(n)
模板：
// s[]是文本串，p[]是模式串，n是s的长度，m是p的长度
int n,m;
char p[N],s[N];
// 求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;//在j!=0的前提下(？)这个j++始终与for循环中的i++同步，每次循环最多执行一次，即使下一个匹配成功后的if也不会对这个j++造成影响，因为下面的j=ne[j]虽然改变了下标，但其对应位置及其左邻域的字符模式没有因为这个操作而改变
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}
说明：
- 使用KMP算法时，起始下标为
1 - 字符串可用
char数组保存，读入时用cin >> p + 1读取，表示从下标1开始写入字符串 - 求
next数组时，由于ne[1]初始化已经为0，故从2开始计算 j == 0表示从头开始匹配模式串，匹配时用p[j + 1]比较
Trie树
用途：
- 高效快速存储和查找字符串集合，又称字典树
- 以字典的形式存在，实现方法是数组模拟指针
- 一般来说内部字符的种类不会很多，比如都是大写字母
- P.S.如果存储汉字之类的种类非常多的可以尝试使用二进制位存储（未理解 见算法基础课二（二）21:30左右，类似题目：143.最大异或对 trie树存储整数）
模板：
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
// idx存储当前用到哪个下标，和单链表的idx一样
// 插入一个全是小写字符的字符串
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx; // 不存在结点则创建结点
p = son[p][u]; // 指向新结点
}
cnt[p] ++ ;//这个字符串出现的次数
}
// 查询字符串出现的次数
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
说明：
- Trie树共享前缀，结点存在不代表根到该结点的字符串存在，需要看标记数组
cnt - Trie树是多重集合
son数组的第1维表示结点地址，要大于所有存储的字符串长度的和（不是字符串长度的最大值）；第2维表示每个结点的最大分支数，一般取字符种类数（如小写字母有26个）cnt[i]表示以son[i]结点为末尾的字符串的个数
并查集
特点：
- 代码短但思路精巧（面试喜欢出）
- 可以快速地支持下列操作：近乎O(1)
- 将两个集合合并
- 询问两个元素是否在一个集合当中
基本原理：
- 用树的形式维护所有的集合
- 每棵树的根节点的编号就是当前集合的编号
- 每个节点存储它的父节点，p[x]表示x的父节点，根节点的p[]等于它自己：p[root]=root
- 问题一：如何判断树根： if(p[x] == x)
- 问题二：如何求x的集合编号： while(p[x] != x)x = p[x];(复杂度依然较大，使用路径压缩可以将复杂度降至近乎o(1),另一种按秩合并优化方式不常用，有兴趣自己搜索，这里主要使用路径压缩方式)
- 问题三：如何合并两个集合： 如果px是x的集合编号，py是y的集合编号，那么合并操作：p[x]=y;
朴素并查集
模板：
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]); // 路径压缩优化
return p[x];
}//核心操作
// 初始化，假定节点编号是1~n，初始化时每个元素都单独是一个集合，它的父节点编号就是它自己
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
// 判断两个结点是否属于同一集合
if (find(a) == find(b)) {...}
说明：
- 查找函数中使用了路径压缩优化并查集结构，使得每个非根结点直接连到根节点上，每棵树的深度不超过
2 - 判断两个数是否属于同一个集合等价于判断两个数的祖宗结点是否相同，即
find(a) == find(b) - 合并操作本质是把其中一个祖宗结点连接到另一个祖宗结点上
维护size的并查集
模板：
int p[N], sz[N]; // 变动部分
//p[]存储每个点的祖宗节点, sz[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量，所以维护的时候只保证根节点的sz有意义即可
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
sz[i] = 1; //初始每个点所在的集合只有它自己一个节点// 变动部分
}
// 合并a和b所在的两个集合：
int x = find(a), y = find(b);
if (x != y) {//一定要有是否相等的判断，否则同一集合内的两个元素将引起集合元素数量的重复相加
p[x] = y;
sz[y] += sz[x];//sz更新
}
// 合并a和b所在的两个集合写法2：
if(find(a)!=find(b)){//一定要有是否相等的判断，否则同一集合内的两个元素将引起集合元素数量的重复相加
sz[find(a)]+=sz[find(b)];//这种写法必须先计算数量再合并集合
p[find(b)]=find(a);
}
// 判断两个结点是否属于同一集合
if (find(a) == find(b)) {...}
//查询a点所在集合的总节点数
sz[find(a)] //先找到它的根节点，然后返回根节点的sz
说明：
sz[x]存储的是以该结点为根的树的结点树- 在合并操作中，可以不必把
find(a)和find(b)存入两个变量。因为第一次调用find()时会进行路径压缩，下一次调用就是O(1)复杂度了。但要注意先修改sz再合并结点，二者顺序不可颠倒，因为结点含义会改变 - 改变
sz时，要先判断两个集合是否为同一个 - 在两个彼此不连通的连通图加上一条边连通二者，等价于把两个集合合并
- 为了避免合并步骤中出现顺序问题，可以用两个变量表示，同时也减少了代码量
维护到祖宗节点距离的并查集
模板：
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]); // 先更新d[p[x]]
d[x] += d[p[x]]; // 再更新d[x]
p[x] = u; // 最后更新p[x]
}
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0; // 自身到自身的距离是0
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
说明：
- 注意
find函数语句的先后次序，次序不对可能会导致含义错误
堆
用途：
- 手写堆支持修改和删除任意元素
- Dijkstra算法需要用堆优化
- 很多贪心、dp问题需要用堆优化
思路：
- 手写堆支持的操作：
- 插入一个数
- 求集合当中的最小值
- 删除最小值
- 删除任意一个元素（STL堆（优先队列）不支持）
- 修改任意一个元素（STL堆（优先队列）不支持）
- 堆的形式：一颗完全二叉树
- 堆的性质：（以小根堆为例）每个点都是小于等于左右儿子的（这是一个递归定义），因此根节点是堆的最小值
- 堆的存储：
- 用一维数组存（堆状数据结构（完全二叉树形）都这么存）
- 1号点是根节点（下标从1开始）
- x号点的左儿子：2x
- x号点的右儿子：2x+1
- 两个基本操作（以小根堆为例）：
- down 如果把一个节点的值变大了，就把这个节点往下移，将这个节点与它的左右儿子比较，如果它不是最小的，就和最小的儿子进行交换，重复这一操作直到不需要交换
- up 如果把一个节点的值变小了，就把这个节点往上移，将它与它的根节点比较，如果它比根节点小，就将它与根节点交换，重复这一操作直到不需要交换
- down和up操作的时间复杂度与树的高度成正比，也就是O(logn)
- 使用down、up实现五个操作：
- 插入一个数
heap[++sz] = x; up(sz); - 求集合当中的最小值
heap[1]; - 删除最小值
heap[1]=heap[sz];sz--;down(1); - 删除任意一个元素
heap[k]=heap[sz];sz--;down(k);up(k); - 修改任意一个元素
heap[k]=x;down(k);up(k); heap[1]代表根节点，也就是最小值heap[sz]代表最后一个节点，也就是数组最末尾，这个节点最容易删除（只需要sz--;）
- 插入一个数
普通模板：
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
int h[N], sz;}
void down(int u)
{
int t = u;
if (u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;//所求点与其左儿子之间的最小值
if (u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;//上一步两个点最小值与右儿子之间的最小值，也就是三个点之间的最小值
if (u != t)
{
swap(h[u], h[t]);
down(t);//递归
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
swap(h[u], h[u / 2]);
u >>= 1;//u/=2;
}
}
// --------------------------------基本操作--------------------------------
// 0. 建堆
void init() {
for (int i = n / 2; i; i -- ) down(i);
//将看似O(nlogn)的建堆过程简化为O(n)
//相当于从完全二叉树的倒数第二层开始down
//证明过程见算法基础课二（二）01:35:43 01:43:22
}
// 1. 插入一个数
void insert(int x) {
h[++sz] = x;
up[sz];
}
// 2. 求最小值
int top() {
return h[1];
}
// 3. 删除最小值
void remove() {
h[1] = h[sz];
sz--;
down(1);
}
// 4. 删除任意位置的元素（STL没有）
void remove(int k) {
h[k] = h[sz];
sz--;
down(k);
up(k);
}
// 5. 修改任意位置的元素（STL没有）
void update(int k, int x) {
h[k] = x;
down(k);
up(k);
}
说明：
- 所有基本操作都可由
up()和down()组合而成 - 建堆的时间可以看做是$O(n)$，因为只有$\frac{n}{2}$个结点参与建堆，这些结点向下调整的次数至多为$2^{h-1}\times 1+2^{h-2}\times 2+2^1\times \left( d-2 \right) +2^0\times \left( d-1 \right) $ ，由错位相减法可知结果$\lt n$
- 实现
down时，注意t的含义是当前最小结点的下标，是变化的，而u是不变的，不要与u的含义弄混 - STL没有基本操作4和基本操作5，尽管它们实现时同时调用了
down()和up()，但实际上只会执行其中一个 - 建堆是从
n/2逆着遍历到1
带映射的加强模板：
Djikstra算法用得到
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置 指针p->堆h
// hp[k]存储堆中下标是k的点是第几个插入的 堆h->指针p
int h[N], ph[N], hp[N], sz, m;
// 加强swap
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u)
{
int t = u;
if (u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t); // 加强swap
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2); // 加强swap
u >>= 1;
}
}
// --------------------------------基本操作--------------------------------
// 0. 建堆
void init() {
for (int i = n / 2; i; i -- ) down(i);
}
// 1. 插入一个数
void insert(int x) {
h[++sz] = x;
ph[++m] = sz; // m为当前插入的序号
hp[sz] = m;
up(sz);
}
// 2. 求最小值
int top() {
return h[1];
}
// 3. 删除最小值
void remove() {
heap_swap(1, sz); // 加强swap
sz--;
down(1);
}
// 4. 删除第k次插入的元素（STL没有）
void remove(int k) {
k = ph[k];
heap_swap(k, sz); // 加强swap
sz--;
down(k);
up(k);
}
// 5. 修改第k次插入的元素（STL没有）
void update(int k, int x) {
k = ph[k];
h[k] = x;
down(k);
up(k);
}
说明：
- 加强模板额外存储了插入记录
ph，映射插入序号和元素在堆中的位置，同时构建了ph的逆映射hp，可根据堆中的下标反推插入序号 - 所有
swap改成加强版的heap_swap，因为要维护ph和hp - 在
heap_swap中，由于参数是下标，但ph数组需要提供插入序号k，因此可用数组hp的值来作为ph的下标
哈希表(存储结构
用途：
- 将一个庞大的空间映射到一个相对较小的空间
- 经典问题：将10^9的数据范围映射到10^5的数据范围
- p.s.离散化相当于一种极其特殊的hash方式，离散化需要保序，hash函数是单调递增的
- 算法题中hash结构一般只实现添加和查找，很少实现删除（如果非要实现删除一般是开一个bool变量打一个标记之类的）
- hash函数取模的值一般是质数，而且这个质数要离2的整数次幂尽可能地远，这种情况下hash冲突的概率是最小的
- hash操作时间近似O(1)
模板：
//两种方法的区别在于处理hash冲突的方式不同
// (1) 拉链法（存储方式类似链式前向星
int h[N], e[N], ne[N], idx;
//取模的值N取大于要求的范围且是质数的值，如要求范围100000就取100003
// 向哈希表中插入一个数
void insert(int x)
{
int k = (x % N + N) % N;//保证取模后的结果是正数
//在h[k]所对应的这个链表中插入一个节点
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查询某个数是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
return false;
}
// (2) 开放寻址法（开一个映射后数据范围2~3倍大小的一维数组
const int null = 0x3f3f3f3f;//定义这个值，如果此处的值是null代表此处没有元素
int h[N];
//取模的值N取大于要求的范围且是质数的值，如要求范围100000就取100003，且经验上这个数一般是所需大小的2~3倍
memset(h, 0x3f, sizeof h); // 给h的每个字节初始化成0x3f，使得每个元素的值都是null
// 如果x在哈希表中，返回x的下标
// 如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)//循环直到找到一个空位置或者找到x的位置
{
t ++ ;
if (t == N) t = 0;//如果已经到了数组最后一个位置就循环到第一个位置
}
return t;
}
说明：
(x % N + N) % N首先把x缩放到满足abs(x) < N，由于第一次求余的结果可能是负数，因此还要再进行一次求余- 用单链表实现拉链法
- 用质数作为长度可以使得冲突最少（数学能证明）
- 可以事先实现一个求质数的函数，算出比
N大的最小质数，作为N的值 - 离散化是哈希的特例，因为离散化要求相对顺序不变，而哈希没有要求
- 哈希表的删除是通过标记实现的
- 开放寻址法手动设定
null的值，其值可根据题目给出的元素数值范围设计。例如元素值的绝对值$\leq 10^9$，又知0x3FFFFFFF$\gt 10^9$，但memset只能按字节赋值，故可考虑0x3F3F3F3F，经检验它$\gt 10^9$，故可使用memset(h, 0x3f, sizeof h);为数组元素“赋”初值null
字符串哈希（字符串前缀哈希法
用途：
O(1)代价计算子串的哈希值- 快速判断两个字符串是否相同
- 在许多字符串算法题中可以代替kmp，但有一些除外（如求一个字符串的循环节）
思路：
- 将一串字符看作p进制数字，将其转化为十进制之后再模上一个较小的数q，通过这种方式求一个复杂的字符串的hash值
- 一般不能将某字符映射为0
- 完全不考虑冲突，一般经验之谈取p=131或p=13331，q=2^64，这种情况下几乎不会出现冲突
- 可以通过类似“利用前缀和求区间和”的方式在O(1)时间内利用前缀串求出任意字串的hash值
模板：
typedef unsigned long long ULL;//取模数选用2^64，利用unsigned long long一旦溢出就等价于取模2^64的机制，自动对目标值取模
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
const int P = 131; // 或13331
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];//取模步骤已经隐含在ULL的机制里了
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
说明：
- 取模的数选用$2^{64}$，这样可用
unsigned long long类型自动进行求余运算，因为该类型溢出等价于mod$2^{64}$ - 质数
p可取经验值131或13331 - $s_i$取
s[i]的ASCII值 - 方法类似前缀和，只是这里还要额外乘上$p^{r-l+1}$，具体过程如下图所示
STL模板
// vector, 变长数组，倍增的思想
//系统为某一程序分配空间时，所需空间与空间大小无关，与申请次数有关，申请一次长度为1的空间与申请一次长度为1000的空间所需时间是一样的，所以vector优化目标是减少申请次数（减少时间），但可以浪费空间
//每次数组长度不够时，申请一个长度*2的新空间，把数组所有的数从原空间copy到新空间，如果数组长度是n，额外copy的总次数均摊到每个元素上的时间复杂度是O(1)，申请空间的总次数是o(logn)
#include<vector>
vector<int> a(10);//定义一个长度为10的vector
vector<int> a(10,3);//定义一个长度为10的且每个数都是3的vector
vector<int> a[10];//vector数组，定义了10个vecotr
a.size() // 返回元素个数
a.empty() // 返回是否为空, 空返回true，否则返回flase
a.clear() // 清空
a.front() / a.back() //返回最开头的元素 / 返回最后一个元素
a.push_back() / a.pop_back() // 在最后插入一个元素 / 删除最后一个元素
a.begin() / a.end() // 指向最开头元素的迭代器 / 指向最后一个元素后面的位置的迭代器
a[i] //和数组一样支持随机寻址
vector<int>::iterator it=a.begin(); // 定义一个指向a开头的迭代器变量
cout<< *it; // 通过对迭代器it解引用输出a的开头元素
it ++; // 迭代器自增
vector<int> b;
if(a < b){……}
// 支持比较运算，按字典序
// pair<int, int> 存储一个二元组 ，前后两个变量类型可以任意
// 可以看作有两个变量，而且已经实现了比较函数的结构体，稍微省一点代码
pair<int, string> p; // 定义
p.first 取第一个元素
p.second 取第二个元素
// 支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
p = make_pair(10, "xyz");//构造pair
p = {20, "abc"};//c++11支持
//pair常用来存储两种属性，可以把需要优先排序的属性放到first
pair<int, pair<int, int>>//pair可以嵌套存储三个及以上属性
// string，字符串
string s;
s[i]//和数组一样支持随即寻址
s.size() / length() // 返回字符串长度
s.empty()
s.clear()
s.substr(起始下标，(子串长度)) // 返回子串，（字串长度）为空或者超过字符串范围时时从起始下标开始输出到结尾
s.c_str() // 返回字符串所在字符数组的起始地址，printf输出用
getline(cin,s,delim); // s字符串 delim终止符号
// queue, 队列
queue<int> q;
q.size()
q.empty()
// 没有清空clear函数 只能通过重新构造实现清空
q = queue<int>();
q.push() // 向队尾插入一个元素
q.front() // 返回队头元素
q.back() // 返回队尾元素
q.pop() // 弹出队头元素
// priority_queue, 优先队列，默认是大根堆
#include<queue>
priority_queue<int> heap;
heap.size()
heap.empty()
// 没有清空clear函数
heap.push() // 插入一个元素
heap.top() // 返回堆顶元素
heap.pop() // 弹出堆顶元素
// 变成小根堆的方式：
// 第一种：定义成小根堆
priority_queue<int, vector<int>, greater<int>> q;
// 第二种：插入元素x的时候全部插入它的相反数-x
// stack, 栈
size()
empty()
// 没有清空clear函数
push() // 向栈顶插入一个元素
top() // 返回栈顶元素
pop() // 弹出栈顶元素
// deque, 双端队列，队头队尾都可以插入删除，而且可以随机访问，相当于加强版vector，速度比较慢
size()
empty()
clear()
front() / back()
push_back() / pop_back()
push_front() / pop_front()
begin() / end()
[]
// set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin() / end()
// ++, -- 返回前驱和后继，时间复杂度 O(logn)
// set/multiset set不允许重复元素，multiset允许重复元素
#include<set>
insert() // 插入一个数
find() // 查找一个数 时间复杂度O(logn) ，如果不存在返回end迭代器
count() // 返回某一个数的个数
erase()
// (1) 输入是一个数x，删除所有x O(k + logn)
// (2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) // 返回大于等于x的最小的数的迭代器
upper_bound(x) // 返回大于x的最小的数的迭代器
// map/multimap
insert() // 插入的数是一个pair
erase() // 输入的参数是pair或者迭代器
find()
[] // 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound() / upper_bound()
// unordered_set, unordered_map, unordered_multiset, unordered_multimap, 基于哈希表，内部无序
// 和上面类似，增删改查的时间复杂度是 O(1)
// 不支持 lower_bound()/upper_bound()， 迭代器的--
// 但可以遍历，但遍历出的序列是无序的
// bitset, 压位 状态压缩
//将bool所需空间压缩到1/8
bitset<10000> s; // 可以存储10000个“是/否”状态
//支持所有位运算操作
// ~, &, |, ^
// >>, <<
// ==, !=
// [] // 取出某一位是0还是1
count() // 返回有多少个1
any() // 判断是否至少有一个1
none() // 判断是否全为0
set() // 把所有位置成1
set(k, v) // 将第k位变成v
reset() // 把所有位变成0
flip() // 把所有位取反，等价于~
flip(k) // 把第k位取反
-
迭代器
迭代器类型 对应容器 操作 前向迭代器 forward_list / unordered_map / unordered_multimap / unordered_set / unordered_multiset p++,++p,*p,==,!=，赋值，复制双向迭代器 list / set / multiset / map / multimap p++,++p,p--,--p,*p,==,!=，赋值，复制随机访问迭代器 array / vector / deque p++,++p,p--,--p,*p,==,!=,赋值，复制,p+i,p-i,p+=i,p-=i,p[i],<,<=,>,>=,p1-p2
说明：
- 系统为某程序分配空间所需要的时间与空间大小无关，而与申请次数有关
priority-queue默认是大根堆，可通过插入-x变成小根堆
参考资料：y总直播，站内卢盼盼笔记
