倍增 LCA

1、LCA：输入树的节点个数 $n$，这棵树以节点 $1$ 为根，接下来 $n-1$ 行，分别输入节点 $2 \to n$ 的父节点，再输入询问次数 $q$，每个询问给出两个整数 $u, v$，输出 $u, v$ 的最近公共祖先 $lca(u,v)$
2、最近公共祖先 LCA：深度最大的公共祖先，即几个节点的父节点链从下向上最早相交的点 (可以是这两个点中的一个)。性质：$u \to v$ 的简单路径可以分为两条链，即 $u \to lca(u,v)$ 和 $lca(u,v) \to v$；类似于 $max, min, gcd$ 等运算，其满足 $lca(x,y,z) = lca(x,lca(y,z))$；多个点的 $lca(x_1,x_2,…,x_k)$ 等价于 DFS 序最小点 和 DFS 序最大点的 $lca$
3、倍增 LCA：类似于ST 表，我们令 $fa[x][j]$ 表示节点 $x$ 向上走 $2^j$ 所到达的点，例如对于节点 $x$，其向上第一个父节点为 $fa[x][0]$，第二个为 $fa[x][1]$，第四个为 $fa[x][2]$，第八个为 $fa[x][3]$；此外，从根开始以节点深度从上到下标记层次，用 $dep[x]$ 记录 $x$ 的深度。这样的结构可以实现快速跳跃，要从 $x$ 向上跳跃到目标层次，可以贪心地先迈大步再迈小步：从大到小枚举 $j$，再检查 $fa[x][j]$ 是否超过目标层次，超过则不操作，不超过则 $x$ 跳跃到当前 $fa[x][j]$，继续向下枚举。例如，如果要从第 $8$ 层跳跃到第 $2$ 层，二者相隔 $6$ 个节点：为方便，从 $j = 3$ 开始枚举，此时 $fa[x][j]$ 是向上 $8$ 个节点的位置，超出目标范围不操作；继续枚举 $j = 2$，此时 $fa[x][j]$ 为向上 $4$ 个节点的位置，令 $x$ 跳到该位置，此时还差 $2$ 个节点到目标；继续枚举 $j = 1$，$x$ 跳到当前 $fa[x][j]$ 到达目标节点。可以发现，起始相隔的 $6$ 个节点二进制为 $110_2$，$1$ 的位置恰好指示了对应位置 $j$ 需要跳跃
4、实现上，初始化最上面虚拟的点 $fa[1][0] = 0$ (无意义)，操作上需要求 $fa[][]$ 数组，再求 $lca$。对于求数组，可以通过 DFS 得到，转移方程为 $fa[x][j] = fa[fa[x][j-1]][j-1]$，例如求 $fa[x][2] = fa[fa[x][1]][1]$ (求 $x$ 向上走 $2^2$ 步，等同于从 $x$ 向上走 $2^1$ 步再走 $2^1$ 步)，在 DFS 过程中，上面的点的 $fa[][]$ (即转移方程右侧)是已知的；此外，对于 $dep[]$ 有 $dep[x] = dep[fa[x][0]] + 1$ (深度为父节点 $+1$)。对于求 $lca$，给定两点 $x, y$，首先将深度大的(假设是 $x$)向上跳至二者在同一深度(用上面的方法跳跃)，判断 $x, y$ 是否相等(因为可能 $y$ 就是 $x$ 的祖先)，相等就输出 $y$；如果不相等，那么二者一起向上跳，依然从大到小枚举 $j$，但条件为若 $fa[x][j] = fa[y][j]$ 则不跳 (始终保持两个点不相等)，这样操作后，最终两个点会留在 $lca$ 的子节点，所以返回父节点 $fa[x][0]$ 即为 $lca$

01Trie

1、Trie 指字典树：简单地说，对于 $abcd, abcc, abca, acca$ 这四个字符串，互相之间有相同前缀，将它拆分成字符，建成边权为字符、点权为到该点为止相同前缀的字符串个数的树，称为 Trie 树，树的高度为字符串长度，如下图(蓝色为边权，红色为点权)。其通常处理前缀问题(如判断某个字符串作为前缀出现多少次)，但实际很少用到 Trie 树，常用的是 01Trie 树
2、01Trie 存储的不是字符，而是二进制的 $0, 1$，用于表示数字，基于二叉树：例如数组内有数字 $5 = 0101_2, 7 = 0111_2, 2 = 0010_2, 10 = 1010_2$，便可以用01Trie 树来存储表示这个数组，树的高度为最长二进制位数，如下图所示
3、01Trie初始只有一个空节点(初始节点 $0$)，采用动态开点的方式，其每个节点存储点权 $val$ 和两条边 $0, 1$ 分别指向的子节点 $son[0], son[1]$。更新时，没有的节点就动态开点，经过的节点点权 $+1$，对应二进制位为 $0$ 就左走，为 $1$ 就右走。对于数值范围在 $10^9$ 内的(约 $30$ 位二进制)，01Trie 通常需要 $32n = N \lt\lt 5$ 的空间

权值线段树

1、权值线段树：输入操作次数 $q$ ($q \leq 2 \times 10^5$)，起始你有一个空的多重集合(允许元素多次出现)，对于每次操作：输入 $1\ x$ 表示向集合添加元素 $x$，输入 $2\ l\ r$ 查询大小在 $[l, r]$ 之间的元素个数，输入 $3\ k$ 查询集合中第 $k$ 小的元素
2、先前介绍的线段树用于维护原数组的区间信息，而权值线段树用于维护数组元素的某种属性，例如元素出现次数或其他权值(但一般就是维护元素出现次数，即维护元素出现次数这个桶)，数据结构上与线段树类似
3、以维护元素出现次数为例，原数组若为 $\{1, 2, 1, 3, 5\}$ ，则元素出现次数的桶内为 $\{[1]:2,\ [2]:1,\ [3]:1,\ [4]:0,\ [5]:1\}$ 。给这个桶建立线段树即为权值线段树，每个节点的管辖区间表示管辖数字的范围，权值为管辖范围内这些数字的出现次数，如节点 $\{[1, 4] : 4\}$ 表示数字 $1 \to 4$ 共出现了 $4$ 次(下图为线段树结构，请按上述描述类比理解权值线段树的结构)，树的叶子结点从左至右对应这个桶本身且管辖区间(对应桶的下标，也即元素值)从左至右都是升序的
4、权值线段树可以进行的操作有单点更新(不依赖 $lazytag$，插入一个元素时更新线段树权值)、数量查询(查询整个数组中元素大小在 $[l, r]$ 之间的元素个数)、数值查询(查询整个数组中第 $k$ 大/小的元素值)，所有操作从根节点开始。单点更新，与线段树搜寻策略相同，但可以搜寻过程中直接更新权值(因为不需要维护 $lazytag$)，当然也可以找到叶子后递回时pushup。数量查询，即对桶求区间和，在权值线段树上的处理和加法线段树是相同的，凑出完整的询问区间求和即可
5、数值查询，查找第 $k$ 小的元素值，从根节点起，看左子节点权值 $t[l]$：由于管辖区间(对应桶的下标，也即元素值)从左至右都是升序的，权值 $t[l]$ 则表示前 $t[l]$ 小的元素都在左子节点区间。如果 $t[l] \geq k$，说明第 $k$ 小在左子节点区间，应向左继续查找第 $k$ 小；否则，则应向右查找第 $k - t[l]$ 小的元素(因为左区间有 $t[l]$ 个更小的元素，向右查询时应减去 $t[i]$ 排除掉这些元素)；最后，应查找到一个叶子结点，其管辖区间即为所求元素值。类似地，查找第 $k$ 大时应判断右子节点权值，如果 $t[r] \geq k$ 则向右查第 $k$ 大，否则向左查第 $k - t[r]$ 大

线段树

1、先前学习了运用树状数组维护区间和，而线段树是一种更高效更通用的方法，通过 $lazytag$ 优化后可以在 $O(\log n)$ 下完成区间修改和查询(朴素版只能单点修改和区间查询)，还可以维护更多的区间信息(区间和、区间积、异或和、最值等满足可加性或集合合并性质的信息)，运用了分治思想
2、线段树是一种基于二叉树的数据结构，朴素版的每个节点包含的信息有：编号 $o$、管辖区间 $[s, e]$、权值(即维护的区间信息)。为了实现区间修改，还会加入懒标记 $lazytag$

欧拉路

1、欧拉路径：从某一点出发经过一条不间断的路径，这条路径刚好访问整个图的所有边一次且仅一次(一笔画问题)。一个图可能有多条欧拉路径
2、欧拉回路：一条首尾相接的欧拉路径(首尾相接的一笔画问题)。一个图可能有多条欧拉回路
3、欧拉图：具有欧拉回路的图。特点为：无向图中所有顶点的度都是偶数；有向图中所有顶点的入度和出度都相等
4、半欧拉图：具有欧拉路径但不具有欧拉回路的图。特点为：无向图中有且仅有两个顶点的度为奇数，这两个顶点分别为起点和终点；有向图中有且仅有一个顶点的出度 - 入度 $= 1$，另有且仅有一个顶点的入度 - 出度 $= 1$，这两个顶点分别为起点和终点
5、推论：欧拉图的所有欧拉路径都是欧拉回路，所以计算欧拉回路与欧拉路径的算法完全一样
6、无向图中，在欧拉路的 2 个奇数度点之外，每多有 2 个奇数度点，画完所需要最少的笔数增加一笔