README

算法竞赛模板库 by 灵茶山艾府 💭💡🎈

 算法 Algorithm

由于算法知识点繁杂，将自己学习到的算法、做过的题目分类整理好是有必要的。

一个算法模板应当涵盖以下几点：
- 对该算法的基本介绍（核心思想、复杂度等）
- 参考链接或书籍章节（讲得比较好的资料）
- 模板代码（代码注释、使用说明）
- 模板补充（常见题型中的额外代码、建模技巧等）
- 相关题目（模板题、经典题、思维转换题等）

 算法目录

不了解 Go？快速入门教程

- 集合论与位运算
- 数据结构
  - 单调栈 monotone_stack.go
  - 单调队列 monotone_queue.go
    - 二维单调队列
  - 双端队列 deque.go
    - 最小双端队列 deque_min.go
  - 堆（优先队列）heap.go
    - 支持修改、删除指定元素的堆
    - 懒删除堆
    - 对顶维
    - 前缀中位数
    - 滑动窗口前 k 小元素和
  - 并查集 union_find.go
    - 点权并查集
    - 边权并查集（种类并查集）
    - 可持久化并查集
    - 回滚并查集 & 动态图连通性
  - ST 表 sparse_table.go
    - 不相交 ST 表（猫树）
    - 二维 ST 表
    - 线段树套 ST 表
  - 树状数组 fenwick_tree.go
    - 差分树状数组（支持区间加、区间求和）
    - 二维树状数组
    - 二维差分树状数组
    - 离线二维数点
  - 线段树 segment_tree.go
    - 线段树二分
    - 延迟标记（懒标记）
      - 矩形面积并（扫描线）segment_tree_rect.go
    - 动态开点
    - 线段树合并
    - 线段树分裂
    - 线段树分治 / 时间线段树
    - 可持久化线段树（主席树）
      - 在线二维数点
  - 树套树 seg_in_bit.go
  - CDQ 分治 cdq.go
    - 动态逆序对
  - 整体二分
    - 动态区间第 k 小
  - 0-1 线段树 segment_tree01.go
  - 左偏树（可并堆）leftist_tree.go
  - 笛卡尔树 cartesian_tree.go
  - 二叉搜索树公共方法 bst.go
  - Treap treap.go
    - 前 k 小元素和
  - 伸展树 splay.go
  - 动态树 LCT link_cut_tree.go
  - 红黑树 red_black_tree.go
  - 替罪羊树 scapegoat_tree.go
  - k-d 树 kd_tree.go
  - 珂朵莉树（ODT）
    - 数组版 odt.go
    - 平衡树版 odt_bst.go
  - 根号分治、分块 sqrt_decomposition.go
  - 莫队算法 mo.go
     - 普通莫队
     - 带修莫队
     - 回滚莫队
     - 树上莫队
- 字符串 strings.go
  - 字符串哈希
  - KMP
    - pi 函数
    - border
    - 最小循环节
    - fail 树（失配树 / border 树）
  - 扩展 KMP（Z algorithm）
  - 最小表示法
  - 最长回文子串 
    - Manacher 算法
  - 回文自动机（回文树，PAM）pam.go
  - 后缀数组（SA）
  - 后缀自动机（SAM）sam.go
  - 字典树 trie.go
    - 可持久化字典树
  - 0-1 字典树 trie01.go
    - 最大异或和
    - 第 k 大异或和
    - 删除元素
    - 可持久化 0-1 字典树
    - 【研究】0-1 字典树上最多有多少个节点
  - AC 自动机 acam.go
- 数学
  - 数论 math.go
    - 辗转相除法（最大公因数 GCD）
    - 类欧几里得算法 ∑⌊(ai+b)/m⌋
    - Pollard-Rho 质因数分解算法
    - 埃氏筛（埃拉托斯特尼筛法）
    - 欧拉筛（线性筛）
    - 欧拉函数
    - 原根
    - 扩展 GCD
      - 二元一次不定方程
    - 逆元
      - 线性求逆元
    - 中国剩余定理（CRT）
      - 扩展中国剩余定理
    - 离散对数
    - 大步小步算法（BSGS）
      - 扩展大步小步算法
    - 二次剩余
    - Jacobi 符号
    - N 次剩余
    - 卢卡斯定理
      - 扩展卢卡斯定理
    - 卡特兰数
    - 默慈金数
    - 那罗延数
    - 斯特林数
      - 第一类斯特林数（轮换）
      - 第二类斯特林数（子集）
    - 贝尔数
    - 欧拉数
    - 数论分块（整除分块）
    - 莫比乌斯函数
    - 莫比乌斯反演
      - 互质计数问题
      - GCD 求和问题
    - 杜教筛
  - 组合数学 math_comb.go
    - 常见模型
    - 常用恒等式
    - 容斥原理
  - 快速傅里叶变换 FFT math_fft.go
    - 分治 FFT
    - 二维 FFT
  - 快速数论变换 NTT math_ntt.go
    - 包含多项式全家桶（求逆、开方等等）
  - 快速沃尔什变换 FWT math_fwt.go
  - 连分数、佩尔方程 math_continued_fraction.go
  - 线性代数 math_matrix.go
    - 矩阵快速幂
    - Berlekamp-Massey 算法
    - Kitamasa 算法
    - 高斯消元
    - 行列式
    - 线性基
  - 数值分析 math_numerical_analysis.go
    - 自适应辛普森积分
    - 拉格朗日插值
  - 计算几何 geometry.go
    - 线与点
    - 线与线
    - 圆与点
      - 最小圆覆盖
        - Welzl 随机增量法
      - 固定半径覆盖最多点
    - 圆与线
    - 圆与圆
    - 圆与矩形
    - 最近点对
    - 多边形与点
      - 判断点在凸多边形内 $O(\log n)$
      - 判断点在任意多边形内
        - 转角法（统计绕数）
    - 凸包
      - 动态凸包
    - 最远点对
      - 旋转卡壳
    - 半平面交
  - 博弈论 games.go
    - SG 函数