概述

给定一个文本 $A$ 和一个字符串 $B$ ，我们可以利用 KMP 算法尝试找到并展示 $B$ 在 $A$ 中的所有出现（occurrence）。

本文部分内容转载自 OI Wiki Splay

$\LaTeX$ 就先咕着吧……有时间慢慢搞

概述

Splay是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链，它由 Daniel Sleator 和 Robert Tarjan 发明。

本文部分内容转载自 OI Wiki 树状数组套主席树

概述

普通数据结构维护单一维度信息，树套树维护多维度信息。

咕咕咕~

概述

乘法逆元定义：如果一个线性同余方程$ax\equiv 1 \mod b$，则$x$成为$a \mod b$的逆元，记作$a^{-1}$。

乘法逆元一般用于求$a/b\mod p$的值（$p$通常为质数），是解决模意义下分数数值的必要手段。

对于$a/b\mod p$，我们可以求出$b$在$\mod p$下的逆元，然后乘上$a$再$\mod p$，就是这个分数的值了。

概述

树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。

具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。