链表：
链表和数组都可用于存储数据。与链表不同，数组将所有元素按次序依次存储。不同的存储结构令它们有了不同的优势：
不管用数组建立什么链表(只要不是循环链表)：
建议用两个变量存储链表头和链表尾。
可以判断插入的节点的下一项是否是现在的链表头，如果是，就更新链表头
同理，可以判断插入的节点的上一项是否是现在的链表尾，如果是，就更新链表尾
链表因其链状的结构，能方便地删除、插入数据，操作次数是 O(1)。但也因为这样，寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是 O(n)。
数组可以方便地寻找并读取数据，在随机访问中操作次数是 O(1)。但删除、插入的操作次数是 O(n) 次。
单向链表：
单向链表中包含数据域和指针域，其中数据域用于存放数据，指针域用来连接当前结点和下一节点。
代码实现：
单链表需要两个数组 vector也可以
一个是存储数据的数组
比如：
int data[10086];
long long data[10086];
也可以用结构体来存储数据：
struct node {
int a, b, c;
long long x, y, z;
}data[10086];
然后就是存储地址的数组了， 作者认为数组中直接存储下标很简单
int add[10086];
链表也可以直接用结构体：
struct Node {
int value;
Node *next;
};
向单向链表中插入（写入）数据
用标准的方法：
流程大致如下：
初始化待插入的数据 node；
将 node 的 next 指针指向 p 的下一个结点；
将 p 的 next 指针指向 node。
具体过程可参考下图：
代码：
void insertNode(int i, Node *p) {
Node *node = new Node;
node->value = i;
node->next = p->next;
p->next = 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 名存实亡。
代码：
void deleteNode(Node *p) {
p->value = p->next->value;
Node *t = p->next;
p->next = p->next->next;
delete t;
}
数组法：
找到删除的上一个，连向删除的下一项（指向是指修改下标值）
双向链表：
双向链表中同样有数据域和指针域。不同之处在于，指针域有左右（或上一个、下一个）之分，用来连接上一个结点、当前结点、下一个结点。
代码实现：
可以用数组模拟：
创建存储数据的数组：
int data[10086];
long long data[10086];
struct node{
int a, b, c;
long long x, y, z;
};
接着就是存储地址的数组了，根据双向链表的定义和性质，需要建立两个存储地址的链表， 仍然是存储下标值：
int addressl[10086];
int addressr[10086];
也可以用一个结构体直接模拟双向链表：
struct Node {
int value;
Node *left;
Node *right;
};
双向链表插入和删除：
删除：
一般方法：
流程大致如下：
将 p 左结点的右指针指向 p 的右节点；
将 p 右结点的左指针指向 p 的左节点；
新建一个临时结点 t 存放 p 的地址；
将 p 的右节点地址赋给 p，以避免 p 变成悬垂指针；
删除 t。
代码如下：
void deleteNode(Node *&p) {
p->left->right = p->right;
p->right->left = p->left;
Node *t = p;
p = p->right;
delete t;
}
数组法：
已知三个节点组成双向链表，要删除最中间的k节点：
代码：
r[l[k]] = r[k];
l[r[k]] = l[k];
插入：
一般方法：
作者不会，会的留个评论
数组法：
顺序很重要
插入节点idx
代码：
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
循环链表：
循环链表又分 单向循环链表和双向循环链表
单向循环链表：
将链表的头尾连接起来，链表就变成了循环链表。由于链表首尾相连，在插入数据时需要判断原链表是否为空：为空则自身循环，不为空则正常插入数据。简单来说就是首尾相连的单向链表。
建立过程如下图：
大致流程如下：
初始化待插入的数据 node；
判断给定链表 p 是否为空；
若为空，则将 node 的 next 指针和 p 都指向自己；
否则，将 node 的 next 指针指向 p 的下一个结点；
将 p 的 next 指针指向 node。
代码（同时也是插入代码）：
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;
}
}
使用数组怎么搞一个单向循环链表：
其实只用链表尾连向头就可以了。
插入和修改同单向链表
双向循环链表：
在向双向循环链表插入数据时，除了要判断给定链表是否为空外，还要同时修改左、右两个指针。
大致流程如下：
初始化待插入的数据 node；
判断给定链表 p 是否为空；
若为空，则将 node 的 left 和 right 指针，以及 p 都指向自己；
否则，将 node 的 left 指针指向 p;
将 node 的 right 指针指向 p 的右结点；
将 p 右结点的 left 指针指向 node；
将 p 的 right 指针指向 node。
代码：
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;
}
}
用数组做一个双向循环链表：
只需要把双向链表的头连向尾，尾连向头即可
删除同双向链表删除
数据结构和stl
数据结构是在计算机中存储、组织数据的方式。小到变量、数组，大到线段树、平衡树，都是数据结构。
栈 stack：
栈是 OI 中常用的一种线性数据结构，请注意，本文主要讲的是栈这种数据结构，而非程序运行时的系统栈/栈空间。
栈的修改是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。
用数组模拟栈
int st[N];
// 这里使用 st[0] (即 *st) 代表栈中元素数量，同时也是栈顶下标
// 压栈 ：
st[++*st] = var1;
// 取栈顶 ：
int u = st[*st];
// 弹栈 ：注意越界问题, *st == 0 时不能继续弹出
if (*st) --*st;
// 清空栈
*st = 0;
stl库中的栈：
常用成员函数：
元素访问
st.top() 返回栈顶
修改
st.push() 插入传入的参数到栈顶
st.pop() 弹出栈顶
容量
st.empty() 返回是否为空
st.size() 返回元素数量
同时也支持运算符：
较为常用的是使用赋值运算符 = 为 stack 赋值
定义：
stack <数据类型> 变量名;
队列 queue：
队列（queue）是一种具有「先进入队列的元素一定先出队列」性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。
数组模拟队列
通常用一个数组模拟一个队列，用两个变量标记队列的首尾。
代码：
int q[SIZE], ql = 1, qr;
队列操作对应的代码如下：
插入元素：q[++qr] = x;
删除元素：ql++;
访问队首：q[ql]
访问队尾：q[qr]
清空队列：ql = 1; qr = 0;
双栈模拟队列
还有一种冷门的方法是使用两个 栈 来模拟一个队列。
这种方法使用两个栈 F, S 模拟一个队列，其中 F 是队尾的栈，S 代表队首的栈，支持 push（在队尾插入），pop（在队首弹出）操作：
push：插入到栈 F 中。
pop：如果 S 非空，让 S 弹栈；否则把 F 的元素倒过来压到 S 中（其实就是一个一个弹出插入，做完后是首尾颠倒的），然后再让 S 弹栈。
容易证明，每个元素只会进入/转移/弹出一次，均摊复杂度 O(1)。
C++ STL 中的队列
STL 中的 queue 容器提供了一众成员函数以供调用。其中较为常用的有：
元素访问
q.front() 返回队首元素
q.back() 返回队尾元素
修改
q.push() 在队尾插入元素
q.pop() 弹出队首元素
容量
q.empty() 队列是否为空
q.size() 返回队列中元素的数量
queue 还提供了一些运算符。较为常用的是使用赋值运算符 = 为 queue 赋值
定义：
queue <数据类型> 变量名;
特殊队列
双端队列
双端队列是指一个可以在队首/队尾插入或删除元素的队列。相当于是栈与队列功能的结合。具体地，双端队列支持的操作有 4 个：
在队首插入一个元素
在队尾插入一个元素
在队首删除一个元素
在队尾删除一个元素
数组模拟双端队列的方式与普通队列相同。
C++ STL 中的双端队列
STL 中的 deque 容器提供了一众成员函数以供调用。其中较为常用的有：
元素访问
q.front() 返回队首元素
q.back() 返回队尾元素
修改
q.push_back() 在队尾插入元素
q.pop_back() 弹出队尾元素
q.push_front() 在队首插入元素
q.pop_front() 弹出队首元素
q.insert() 在指定位置前插入元素（传入迭代器和元素）
q.erase() 删除指定位置的元素（传入迭代器）
容量
q.empty() 队列是否为空
q.size() 返回队列中元素的数量
此外，deque 还提供了一些运算符。其中较为常用的有：
使用赋值运算符 = 为 deque 赋值，类似 queue。
使用 访问元素，类似 vector。
循环队列
使用数组模拟队列会导致一个问题：随着时间的推移，整个队列会向数组的尾部移动，一旦到达数组的最末端，即使数组的前端还有空闲位置，再进行入队操作也会导致溢出（这种数组里实际有空闲位置而发生了上溢的现象被称为「假溢出」）。
解决假溢出的办法是采用循环的方式来组织存放队列元素的数组，即将数组下标为 0 的位置看做是最后一个位置的后继。（数组下标为 x 的元素，它的后继为 (x + 1) % SIZE）。这样就形成了循环队列。
优先队列 vector：
vector 是 STL 提供的 内存连续的、可变长度 的数组（亦称列表）数据结构。能够提供线性复杂度的插入和删除，以及常数复杂度的随机访问。
作为 OIer，对程序效率的追求远比对工程级别的稳定性要高得多，而 vector 由于其对内存的动态处理，时间效率在部分情况下低于静态数组，并且在 OJ 服务器不一定开全优化的情况下更加糟糕。所以在正常存储数据的时候，通常不选择 vector。下面给出几个 vector 优秀的特性，在需要用到这些特性的情况下，vector 能给我们带来很大的帮助。
vector 可以动态分配内存
很多时候我们不能提前开好那么大的空间（eg：预处理 1~n 中所有数的约数）。尽管我们能知道数据总量在空间允许的级别，但是单份数据还可能非常大，这种时候我们就需要 vector 来把内存占用量控制在合适的范围内。vector 还支持动态扩容，在内存非常紧张的时候这个特性就能派上用场了。
vector 重写了比较运算符及赋值运算符
vector 重载了六个比较运算符，以字典序实现，这使得我们可以方便的判断两个容器是否相等（复杂度与容器大小成线性关系）。例如可以利用 vector 实现字符串比较（当然，还是用 std::string 会更快更方便）。另外 vector 也重载了赋值运算符，使得数组拷贝更加方便。
vector 便利的初始化
由于 vector 重载了 = 运算符，所以我们可以方便的初始化。此外从 C++11 起 vector 还支持 列表初始化，例如 vector data {1, 2, 3};。
// 1. 创建空vector; 常数复杂度
vector v0;
// 1+. 这句代码可以使得向vector中插入前3个元素时，保证常数时间复杂度
v0.reserve(3);
// 2. 创建一个初始空间为3的vector，其元素的默认值是0; 线性复杂度
vector v1(3);
// 3. 创建一个初始空间为3的vector，其元素的默认值是2; 线性复杂度
vector v2(3, 2);
// 4. 创建一个初始空间为3的vector，其元素的默认值是1，
// 并且使用v2的空间配置器; 线性复杂度
vector v3(3, 1, v2.get_allocator());
// 5. 创建一个v2的拷贝vector v4， 其内容元素和v2一样; 线性复杂度
vector v4(v2);
// 6. 创建一个v4的拷贝vector v5，其内容是{v4[1], v4[2]}; 线性复杂度
vector v5(v4.begin() + 1, v4.begin() + 3);
// 7. 移动v2到新创建的vector v6，不发生拷贝; 常数复杂度; 需要 C++11
vector v6(std::move(v2)); // 或者 v6 = std::move(v2);
元素访问
vector 提供了如下几种方法进行元素访问
at()
v.at(pos) 返回容器中下标为 pos 的引用。如果数组越界抛出 std::out_of_range 类型的异常。
operator
v[pos] 返回容器中下标为 pos 的引用。不执行越界检查。
front()
v.front() 返回首元素的引用。
back()
v.back() 返回末尾元素的引用。
data()
v.data() 返回指向数组第一个元素的指针。
迭代器
vector 提供了如下几种 迭代器
begin()/cbegin()
返回指向首元素的迭代器，其中 *begin = front。
end()/cend()
返回指向数组尾端占位符的迭代器，注意是没有元素的。
rbegin()/crbegin()
返回指向逆向数组的首元素的逆向迭代器，可以理解为正向容器的末元素。
rend()/crend()
返回指向逆向数组末元素后一位置的迭代器，对应容器首的前一个位置，没有元素。
以上列出的迭代器中，含有字符 c 的为只读迭代器，你不能通过只读迭代器去修改 vector 中的元素的值。如果一个 vector 本身就是只读的，那么它的一般迭代器和只读迭代器完全等价。只读迭代器自 C++11 开始支持。
长度和容量
vector 有以下几个与容器长度和容量相关的函数。注意，vector 的长度（size）指有效元素数量，而容量（capacity）指其实际分配的内存长度，
与长度相关：
empty() 返回一个 bool 值，即 v.begin() == v.end()，true 为空，false 为非空。
size() 返回容器长度（元素数量），即 std::distance(v.begin(), v.end())。
resize() 改变 vector 的长度，多退少补。补充元素可以由参数指定。
max_size() 返回容器的最大可能长度。
与容量相关：
reserve() 使得 vector 预留一定的内存空间，避免不必要的内存拷贝。
capacity() 返回容器的容量，即不发生拷贝的情况下容器的长度上限。
shrink_to_fit() 使得 vector 的容量与长度一致，多退但不会少。
元素增删及修改
clear() 清除所有元素
insert() 支持在某个迭代器位置插入元素、可以插入多个。复杂度与 pos 距离末尾长度成线性而非常数的
erase() 删除某个迭代器或者区间的元素，返回最后被删除的迭代器。复杂度与 insert 一致。
push_back() 在末尾插入一个元素，均摊复杂度为 常数，最坏为线性复杂度。
pop_back() 删除末尾元素，常数复杂度。
swap() 与另一个容器进行交换，此操作是 常数复杂度 而非线性的。
vector 的实现细节
vector 的底层其实仍然是定长数组，它能够实现动态扩容的原因是增加了避免数量溢出的操作。首先需要指明的是 vector 中元素的数量（长度）n 与它已分配内存最多能包含元素的数量（容量）N 是不一致的，vector 会分开存储这两个量。当向 vector 中添加元素时，如发现 n>N，那么容器会分配一个尺寸为 2N 的数组，然后将旧数据从原本的位置拷贝到新的数组中，再将原来的内存释放。尽管这个操作的渐进复杂度是 O(n)，但是可以证明其均摊复杂度为 O(1)。而在末尾删除元素和访问元素则都仍然是 O(1) 的开销。 因此，只要对 vector 的尺寸估计得当并善用 resize() 和 reserve()，就能使得 vector 的效率与定长数组不会有太大差距。
vector
标准库特别提供了对 bool 的 vector 特化，每个「bool」只占 1 bit，且支持动态增长。但是其 operator 的返回值的类型不是 bool& 而是 vector::reference。因此，使用 vector 使需谨慎，可以考虑使用 deque 或 vector 替代。而如果你需要节省空间，请直接使用 bitset。
set
set 是关联容器，含有键值类型对象的已排序集，搜索、移除和插入拥有对数复杂度。set 内部通常采用红黑树实现。平衡二叉树的特性使得 set 非常适合处理需要同时兼顾查找、插入与删除的情况。
和数学中的集合相似，set 中不会出现值相同的元素。如果需要有相同元素的集合，需要使用 multiset。multiset 的使用方法与 set 的使用方法基本相同。
插入与删除操作
insert(x) 当容器中没有等价元素的时候，将元素 x 插入到 set 中。
erase(x) 删除值为 x 的 所有 元素，返回删除元素的个数。
erase(pos) 删除迭代器为 pos 的元素，要求迭代器必须合法。
erase(first,last) 删除迭代器在 [first,last) 范围内的所有元素。
clear() 清空 set
迭代器
set 提供了以下几种迭代器：
begin()/cbegin()
返回指向首元素的迭代器，其中 *begin = front。
end()/cend()
返回指向数组尾端占位符的迭代器，注意是没有元素的。
rbegin()/crbegin()
返回指向逆向数组的首元素的逆向迭代器，可以理解为正向容器的末元素。
rend()/crend()
返回指向逆向数组末元素后一位置的迭代器，对应容器首的前一个位置，没有元素。
以上列出的迭代器中，含有字符 c 的为只读迭代器，你不能通过只读迭代器去修改 set 中的元素的值。如果一个 set 本身就是只读的，那么它的一般迭代器和只读迭代器完全等价。只读迭代器自 C++11 开始支持。
查找操作
count(x) 返回 set 内键为 x 的元素数量。
find(x) 在 set 内存在键为 x 的元素时会返回该元素的迭代器，否则返回 end()。
lower_bound(x) 返回指向首个不小于给定键的元素的迭代器。如果不存在这样的元素，返回 end()。
upper_bound(x) 返回指向首个大于给定键的元素的迭代器。如果不存在这样的元素，返回 end()。
empty() 返回容器是否为空。
size() 返回容器内元素个数。
在贪心算法中经常会需要出现类似 找出并删除最小的大于等于某个值的元素。这种操作能轻松地通过 set 来完成。
// 现存可用的元素
set available；
// 需要大于等于的值
int x;
// 查找最小的大于等于x的元素
set::iterator it = available.lower_bound(x);
if (it == available.end()) {
// 不存在这样的元素，则进行相应操作……
} else {
// 找到了这样的元素，将其从现存可用元素中移除
available.erase(it);
// 进行相应操作……
}
map
map 是有序键值对容器，它的元素的键是唯一的。搜索、移除和插入操作拥有对数复杂度。map 通常实现为红黑树。
你可能需要存储一些键值对，例如存储学生姓名对应的分数：Tom 0，Bob 100，Alan 100。但是由于数组下标只能为非负整数，所以无法用姓名作为下标来存储，这个时候最简单的办法就是使用 STL 中的 map 了！
map 重载了 operator，可以用任意定义了 operator < 的类型作为下标（在 map 中叫做 key，也就是索引）：
map 中不会存在键相同的元素，multimap 中允许多个元素拥有同一键。multimap 的使用方法与 map 的使用方法基本相同。
插入与删除操作
可以直接通过下标访问来进行查询或插入操作。例如 mp[“Alan”]=100。
通过向 map 中插入一个类型为 pair<Key, T> 的值可以达到插入元素的目的，例如 mp.insert(pair<string,int>(“Alan”,100));；
erase(key) 函数会删除键为 key 的 所有 元素。返回值为删除元素的数量。
erase(pos): 删除迭代器为 pos 的元素，要求迭代器必须合法。
erase(first,last): 删除迭代器在 [first,last) 范围内的所有元素。
clear() 函数会清空整个容器。
查询操作
count(x): 返回容器内键为 x 的元素数量。复杂度为 O(\log(size)+ans)（关于容器大小对数复杂度，加上匹配个数）。
find(x): 若容器内存在键为 x 的元素，会返回该元素的迭代器；否则返回 end()。
lower_bound(x): 返回指向首个不小于给定键的元素的迭代器。
upper_bound(x): 返回指向首个大于给定键的元素的迭代器。若容器内所有元素均小于或等于给定键，返回 end()。
empty(): 返回容器是否为空。
size(): 返回容器内元素个数。
map 用于存储复杂状态
在搜索中，我们有时需要存储一些较为复杂的状态（如坐标，无法离散化的数值，字符串等）以及与之有关的答案（如到达此状态的最小步数）。map 可以用来实现此功能。其中的键是状态，而值是与之相关的答案。下面的示例展示了如何使用 map 存储以 string 表示的状态。
// 存储状态与对应的答案
map<string, int> record;
// 新搜索到的状态与对应答案
string status;
int ans；
// 查找对应的状态是否出现过
map<string, int>::iterator it = record.find(status);
if (it == record.end()) {
// 尚未搜索过该状态，将其加入状态记录中
record[status] = ans;
// 进行相应操作……
} else {
// 已经搜索过该状态，进行相应操作……
}
遍历容器
可以利用迭代器来遍历关联式容器的所有元素。
set s;
typedef set::iterator si;
for (si it = s.begin(); it != s.end(); it++) cout << *it << endl;
需要注意的是，对 map 的迭代器解引用后，得到的是类型为 pair<Key, T> 的键值对。
在 C++11 中，使用范围 for 循环会让代码简洁很多：
set s;
for (auto x : s) cout << x << endl;
对于任意关联式容器，使用迭代器遍历容器的时间复杂度均为 O(n)。
自定义比较方式
set 在默认情况下的比较函数为 <（如果是非内置类型需要 重载 < 运算符）。然而在某些特殊情况下，我们希望能自定义 set 内部的比较方式。
这时候可以通过传入自定义比较器来解决问题。
具体来说，我们需要定义一个类，并在这个类中 重载 () 运算符。
例如，我们想要维护一个存储整数，且较大值靠前的 set，可以这样实现：
struct cmp {
bool operator()(int a, int b) { return a > b; }
};
set<int, cmp> s;
尺取&差分&前缀和
前缀和
定义
前缀和可以简单理解为「数列的前 n 项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。
二维/多维前缀和
多维前缀和的普通求解方法几乎都是基于容斥原理。
差分
解释
差分是一种和前缀和相对的策略，可以当做是求和的逆运算。
它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。
双指针
引入
双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。
双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。
接下来我们来看双指针的几个具体使用方法。
维护区间信息
如果不和其他数据结构结合使用，双指针维护区间信息的最简单模式就是维护具有一定单调性，新增和删去一个元素都很方便处理的信息，就比如正数的和、正整数的积等等。
代码
int numSubarrayProductLessThanK(vector& nums, int k) {
long long ji = 1ll, ans = 0;
int l = 0;
for (int i = 0; i < nums.size(); ++i) {
ji *= nums[i];
while (l <= i && ji >= k) ji /= nums[l++];
ans += i - l + 1;
}
return ans;
}
使用双指针维护区间信息也可以与其他数据结构比如差分、单调队列、线段树、主席树等等结合使用。另外将双指针技巧融入算法的还有莫队，莫队中将询问离线排序后，一般也都是用两个指针记录当前要处理的区间，随着指针一步步移动逐渐更新区间信息。
利用序列有序性
很多时候在序列上使用双指针之所以能够正确地达到目的，是因为序列的某些性质，最常见的就是利用序列的有序性。
实现
vector twoSum(vector& numbers, int target) {
int r = numbers.size() - 1, l = 0;
vector ans;
ans.clear();
while (l < r) {
if (numbers[l] + numbers[r] > target)
r–;
else if (numbers[l] + numbers[r] == target) {
ans.push_back(l + 1), ans.push_back(r + 1);
return ans;
} else
l++;
}
return ans;
}
在归并排序中，在 O(n+m) 时间内合并两个有序数组，也是保证数组的有序性条件下使用的双指针法。
在单向链表中找环
