简介 该数据结构的作用有如下两点： 合并两个集合。 查询两个元素是否在同一个集合中。 基本实现原理是把每个集合用一颗树表示，树根的编号是这个集合的编号，每个节点都存储它的父节点，p[x] 表示 x 的父节点，对于根节点，p[x] = x。 对于优化，可以在查找树根时将路径上的每一个节点的父节点都指向树根。 例题 一共有 nnn 个数，编号是 111 ~ nnn，最开始每个数各自在一个集合中。 ...

Trie 树是用来存储和查找字符串或数字等构成元素不多的数据结构，多用来匹配特定前缀。

KMP 算法通过将相同前缀后缀的长度储存到 next 数组中来避免匹配时重复操作，将平方复杂度的的暴力算法优化到了线性复杂度。

在 C++ 中用数组来模拟单双链表，这样的方式也被称为静态链表，下面以两例题记录 C++ 中的链表应该如何定义和使用。

简介 堆是一种完全二叉树（从上到下，从左到右排列）这意味着它可以被储存到一个数组中，并且对任意一个节点 iii 都有左子节点为 2i2i2i，右子节点为 2i+12i+12i+1，和线段树类似。 当插入元素时，我们需要下滤操作来维持堆的单调性，具体操作流程如下： 将当前节点和两个子节点作比较，如果满足单调性不做任何调整。 如果不满足将较小的子节点与父节点交换，使较小的子节点在上面。 递归执行将放 ...

离散化的目的是将数值大且数量少的一组数据映射为一组较小的数据，比如 [-10^9, 10^9] 范围的数据映射到 [0, 10^5]，从而更方便地用数组储存一些数据。在实战中，通常将这组数据存储到 vector 中之后排序并去重，然后用下标表示某个数字，即将数字映射为下标。

双指针 双指针是在暴力解法可行的情况下进行优化，达到降低时间复杂度的结果。通常来说，它能将一个嵌套循环（平方复杂度）优化为一层循环（线性复杂度）。 一般地，双指针算法的模板与下面给出代码类似： 1234for (int i = 0, j = 0; i < n; i++) { while (cond(i, j, m)) j++; foo();} 下文均为例题。 ...

前缀和用来求一个区间内的和，差分用来对一个区间加减常数的操作减少复杂度，利用了高中数学中学过的数列前N项和的性质。

高精度的实现模板，包括存储、运算、以及关于边界处理的分析。

二分模板 寻找左边界用第一个，寻找右边界用第二个。 1234567891011121314151617int binary1(int l, int r) { while (l < r) { int mid = l+r>>1; if (check(mid)) l = mid+1; else r = mid; ...