Templates

---

Advanced templates for solving algorithmic problems

慢慢填坑...

Contents

---

• Data Structure
  • Sparse Table 稀疏表
  • Segment Tree 线段树
  • Fenwick Tree 树状数组
  • 2-3-4 Tree 2-4树
  • Red-Black Tree 红黑树
  • Splay Tree 伸展树
  • K-D Tree K-D树
  • Old Driver Tree 珂朵莉树
  • Union Find Set 并查集
  • 莫队算法
• String
  • 字符串哈希
  • KMP
  • 扩展KMP (Z algorithm)
  • 最长回文子串
    • Manacher算法
  • Trie Tree 字典树
    • 持久化
    • AC自动机
  • 后缀数组
• Mathematics
  • Number Theory
    • GCD
    • 扩展GCD
    • 质因数分解
    • 埃氏素数
    • 欧拉函数
    • 中国剩余定理
    • 组合数学
      • 卡特兰数
      • 斯特林数
      • 容斥原理
  • FFT
  • Geometry
  • Games
• Dynamic Programming
  • Knapsack DP
    • 0-1 背包
    • 完全背包
    • 多重背包
    • 分组背包
    • 树上背包
    • 字典序最小方案
  • 线性 DP
    • 最大子段和
    • LCS
    • LPS
    • LIS
    • LCIS
  • 区间 DP
  • 状压 DP
  • 环形 DP
  • 数位 DP
  • 树形 DP
• Graph Theory
  • Shortest Path Algorithms
    • Dijkstra
    • SPFA (基于队列优化的bellman-ford算法)
    • Floyd
  • Minimum Spinning Tree
    • Kruskal
    • Prim
  • Matching
    • 匈牙利算法
    • Kuhn-Munkres算法 (带权二分图最大完美匹配)
  • Max Flow
    • Dinic
    • ISAP
    • HLPP
  • Topological Sorting
    • 判环问题
  • Euler Path or Euler Loop
• Others