Template of data structure and algorithm
数据结构和算法模板

Data Structure 数据结构

Trie 字典树

Binary Indexed Tree 树状数组

Sparse Table 稀疏表

Segment Tree 线段树

• 主席树

• Li-Chao Segment Tree 李超线段树

Aho-Corasick automaton AC自动机

Balance Tree 平衡树

• Splay Tree 伸展树

• Treap 树堆

• FHQ-Treap 范浩强Treap

Link/cut tree

块状链表

Dancing Link 舞蹈链

Suffix array 后缀数组

Suffix automaton 后缀自动机

...

---

Algorithm 算法

Graph theory 图论

Graph 图

• Dijkstra algorithm

• Bellman-Ford algorithm

• SPFA

• Floyd-Warshall algorithm

• Kruskal algorithm

• Prim algorithm

• Hungarian algorithm 匈牙利算法

• Topological sorting 拓扑排序

• Tarjan algorithm

• Chu-Liu algorithm 朱刘算法

Network Flow 网络流

• Edmonds-Karp algorithm EK算法

• Dinic algorithm

Number theory 数论

• Linear sieve 线性筛

• Fast exponentiation 快速幂

• Euclidean algorithm 欧几里得算法

• Extended Euclidean algorithm 扩展欧几里得算法

• Chinese remainder theorem 中国剩余定理

• Extended chinese remainder theorem 扩展中国剩余定理

• BSGS

• Extended BSGS 扩展BSGS

• Du algorithm 杜教筛

Dynamic programming 动态规划

• Knapsack problem 背包问题

• 01 knapsack 01背包

• Unbounded knapsack 完全背包

• Bounded knapsack 多重背包

• 混合背包

• 分组背包

• 有依赖背包

• 区间DP

• 状态压缩DP

• 数位DP

• 树形DP

• 单调队列优化DP

• 斜率优化DP

• 插头DP

Geometry 计算几何

• Andrew algorithm

• Sort-and-incremental algorithm

• Welzl algorithm

• Shamo algorithm

• Bowyer-Watson algorithm

Mathematic 数学

• Fast Fourier transform 快速傅里叶变换

• 二项式反演

• Number-theoretic transform 数论变换

Other 其他

• Mo algorithm 莫队算法

• 带修改莫队

• 回滚莫队

• 树上莫队

• 二次离线莫队

• CDQ divide and conquer 陈丹琦分治

• Simulated annealing 模拟退火

• to be continued...