算法竞赛
从复杂度与正确性出发，覆盖数据结构、搜索、动态规划、图论、字符串、竞赛数学与计算几何。每个知识点给出讲解、C++ 模板与模板题。
先学习复杂度、基础技巧与数据结构，再进入搜索、贪心和动态规划；图论、字符串与竞赛数学可以按题目需要交叉学习。每篇文章给出适用条件、复杂度、C++ 模板与模板题，模板题优先选用 Library Checker。
已完成 2 / 231 个知识点
基础与复杂度
复杂度分析、正确性论证与最常用的基础技巧。
- 时间与空间复杂度规划中
- 递归式与主定理规划中
- 摊还分析规划中
- 循环不变量与正确性证明规划中
- 枚举规划中
- 模拟规划中
- 前缀和与差分规划中static_range_sum
- 双指针与滑动窗口规划中
- 离散化规划中
- 位运算技巧规划中
- 排序：比较排序与线性排序规划中
- 二分查找与二分答案规划中
- 三分法规划中
- 分治规划中
- 随机化技巧规划中
- 高精度计算规划中addition_of_big_integersmultiplication_of_big_integersdivision_of_big_integers
- 快速读写与代码模板规划中
- 对拍与调试规划中
数据结构
按操作需求选择数据组织方式：静态查询、动态修改、可持久化与离线处理。
- 栈、队列与双端队列规划中deque
- 单调栈规划中
- 单调队列规划中
- 双栈模拟队列与可合并信息规划中queue_operate_all_compositedeque_operate_all_composite
- 哈希表规划中associative_array
- 二叉堆与优先队列规划中double_ended_priority_queue
- 可并堆：左偏树与配对堆规划中
- 并查集unionfind
- 带权并查集规划中unionfind_with_potentialunionfind_with_potential_non_commutative_group
- 可撤销并查集规划中
- ST 表规划中staticrmq
- 树状数组point_add_range_sum
- 线段树规划中point_set_range_compositepoint_add_range_sum
- 懒标记线段树规划中range_affine_range_sumrange_add_range_min
- 动态开点与线段树合并规划中point_set_range_composite_large_arrayrange_affine_range_sum_large_array
- 吉司机线段树规划中range_chmin_chmax_add_range_sum
- 李超线段树规划中line_add_get_minsegment_add_get_min
- 可持久化线段树规划中range_kth_smallestpersistent_range_affine_range_sum
- 可持久化数组、栈、队列与并查集规划中persistent_queuepersistent_unionfind
- Treap 与 FHQ Treap规划中ordered_setdynamic_sequence_range_affine_range_sum
- Splay 树规划中range_reverse_range_sum
- pb_ds 平衡树与 std::set 技巧规划中predecessor_problem
- 笛卡尔树规划中cartesian_tree
- Link-Cut Tree规划中dynamic_tree_vertex_add_path_sumdynamic_tree_vertex_set_path_composite
- Euler Tour Tree 与 Top Tree规划中dynamic_tree_vertex_add_subtree_sumdynamic_tree_subtree_add_subtree_sum
- 小波矩阵规划中range_kth_smalleststatic_range_frequency
- 01 Trie规划中set_xor_min
- 二维树状数组与二维数点规划中rectangle_sumpoint_add_rectangle_sumstatic_rectangle_add_rectangle_sum
- K-D Tree规划中
- 分块规划中static_range_mode_query
- 莫队算法规划中static_range_inversions_querystatic_range_count_distinct
- 带修莫队、回滚莫队与树上莫队规划中
- 珂朵莉树（ODT）规划中
- bitset 优化规划中
搜索
在状态空间中找解：遍历、剪枝、双向与启发式。
- 深度优先搜索规划中
- 广度优先搜索规划中
- 回溯与剪枝规划中
- 双向搜索规划中
- 折半搜索规划中
- 迭代加深与 IDA*规划中
- A* 搜索规划中
- Dancing Links规划中
- 模拟退火与爬山规划中
贪心与构造
证明局部选择可以推出全局最优，并学会构造答案。
- 贪心与交换论证规划中
- 区间调度与区间覆盖规划中
- 反悔贪心规划中
- Huffman 编码规划中
- 构造题思路规划中
- 交互题规划中
动态规划
定义状态、写出转移、选择计算顺序，并用数据结构或性质优化转移。
- 动态规划基础规划中
- 记忆化搜索规划中
- LIS 与 LCS规划中longest_increasing_subsequence
- 背包 DP规划中
- 区间 DP规划中
- DAG 上的 DP规划中
- 树形 DP规划中
- 换根 DP规划中tree_path_composite_sum
- 状压 DP规划中
- 插头 DP 与轮廓线 DP规划中
- 数位 DP规划中
- 概率与期望 DP规划中
- 计数 DP规划中number_of_subsequences
- 高维前缀和（SOS DP）规划中
- 单调队列优化 DP规划中
- 斜率优化规划中
- 决策单调性与分治优化规划中
- 四边形不等式与 Knuth 优化规划中
- WQS 二分（Aliens Trick）规划中
- Slope Trick规划中
- 矩阵快速幂优化 DP规划中
- 动态 DP规划中point_set_tree_path_composite_sum
- Min-Plus 卷积规划中min_plus_convolution_convex_convexmin_plus_convolution_convex_arbitrary
图论
把关系、依赖与路径抽象为图：连通性、最短路、生成树、匹配与网络流。
- 图的存储与遍历规划中
- 拓扑排序规划中
- Dijkstra规划中shortest_path
- Bellman-Ford 与 SPFA规划中
- Floyd 与传递闭包规划中
- Johnson 全源最短路规划中
- 0-1 BFS规划中
- 差分约束规划中
- K 短路规划中k_shortest_walk
- Kruskal 与 Kruskal 重构树规划中minimum_spanning_tree
- Prim 与 Borůvka规划中
- 最小树形图规划中directedmst
- 强连通分量规划中scc
- 2-SAT规划中two_sat
- 割点与桥规划中
- 双连通分量与圆方树规划中biconnected_componentstwo_edge_connected_components
- 欧拉路径规划中eulerian_trail_directedeulerian_trail_undirected
- 找环与最小环规划中cycle_detectioncycle_detection_undirected
- 二分图判定规划中
- 二分图最大匹配规划中bipartitematching
- 带权二分图匹配（KM）规划中assignment
- 一般图匹配规划中general_matchinggeneral_weighted_matching
- 最大流：Dinic 与 ISAP规划中
- 最小割及其应用规划中
- 费用流规划中min_cost_b_flow
- 上下界网络流规划中
- 全局最小割（Stoer-Wagner）规划中
- 支配树规划中dominatortree
- 色数与独立集规划中chromatic_numbermaximum_independent_set
- 三元环、四元环与团规划中enumerate_trianglescounting_c4enumerate_cliques
- 斯坦纳树规划中minimum_steiner_tree
树论
利用树的层次结构：直径、重心、祖先查询、路径与子树信息。
- 树的基础与 DFS 序规划中
- 树的直径规划中tree_diameter
- 树的重心规划中
- 最近公共祖先规划中lca
- 倍增与树上跳跃规划中jump_on_tree
- 树链剖分规划中vertex_add_path_sumvertex_set_path_compositevertex_add_subtree_sum
- 树上启发式合并规划中
- 点分治与点分树规划中frequency_table_of_tree_distancevertex_add_range_contour_sum_on_tree
- 虚树规划中
- 树哈希与树同构规划中rooted_tree_isomorphism_classification
- Prüfer 序列规划中
- 树上差分规划中
字符串
利用前缀、后缀、自动机和回文结构处理匹配与重复。
- 字符串哈希规划中
- KMP 与前缀函数规划中
- Z 函数规划中zalgorithm
- Trie规划中
- AC 自动机规划中aho_corasick
- Manacher规划中enumerate_palindromes
- 回文自动机规划中eertree
- 后缀数组与 LCP规划中suffixarraynumber_of_substrings
- 后缀自动机规划中number_of_substringslongest_common_substring
- 后缀树规划中
- Lyndon 分解与最小表示法规划中lyndon_factorization
- Runs 与周期规划中runenumerate
- 带通配符匹配规划中wildcard_pattern_matching
- 序列自动机规划中
数论
整除、同余、积性函数与素数相关的算法。
- 最大公约数与扩展欧几里得规划中
- 模运算与快速幂规划中
- 乘法逆元规划中
- 埃氏筛与线性筛规划中enumerate_primes
- 欧拉函数与欧拉定理规划中sum_of_totient_function
- 中国剩余定理与扩展 CRT规划中
- Lucas 与扩展 Lucas规划中binomial_coefficient
- Miller-Rabin 素性测试规划中primality_test
- Pollard-Rho 因数分解规划中factorize
- 整除分块规划中enumerate_quotients
- 莫比乌斯函数与反演规划中
- 狄利克雷卷积规划中dirichlet_convolution_and_prefix_sumsdirichlet_inverse_and_prefix_sums
- 杜教筛规划中
- Min_25 筛与积性函数求和规划中sum_of_multiplicative_functioncounting_primes
- BSGS 与离散对数规划中discrete_logarithm_mod
- 原根与阶规划中primitive_root
- 二次剩余规划中sqrt_mod
- N 次剩余与整数开方规划中kth_root_modkth_root_integer
- 类欧几里得算法规划中sum_of_floor_of_linearmin_of_mod_of_linear
- 连分数与 Stern-Brocot 树规划中stern_brocot_treerational_approximation
- 高斯整数与平方和规划中gcd_of_gaussian_integerstwo_square_sum
- 扩展欧拉定理与幂塔规划中tetration_mod
组合数学
计数原理、经典数列、容斥与群论计数。
- 加法、乘法原理与排列组合规划中
- 二项式系数与预处理阶乘规划中binomial_coefficient_prime_modfactorial
- 容斥原理规划中
- 抽屉原理规划中
- 卡特兰数规划中
- 斯特林数规划中stirling_number_of_the_first_kindstirling_number_of_the_second_kind
- 贝尔数与分拆数规划中bell_numberpartition_function
- 错排规划中montmort_number_mod
- Burnside 引理与 Pólya 定理规划中
- LGV 引理规划中
- 二项式反演与子集反演规划中
- 伯努利数与自然数幂和规划中bernoulli_number
多项式与卷积
把计数和序列问题转成卷积，用 FFT、NTT 与形式幂级数高效求解。
- 快速傅里叶变换规划中
- 快速数论变换规划中convolution_mod
- 任意模数卷积规划中convolution_mod_1000000007
- 生成函数规划中
- 多项式求逆规划中inv_of_formal_power_series
- 多项式除法与取模规划中division_of_polynomials
- 多项式 ln 与 exp规划中log_of_formal_power_seriesexp_of_formal_power_series
- 多项式幂与开方规划中pow_of_formal_power_seriessqrt_of_formal_power_series
- 多点求值与快速插值规划中multipoint_evaluationpolynomial_interpolation
- 拉格朗日插值规划中shift_of_sampling_points_of_polynomial
- 多项式平移规划中polynomial_taylor_shift
- 线性递推与 Bostan-Mori规划中kth_term_of_linearly_recurrent_sequence
- Berlekamp-Massey规划中find_linear_recurrence
- 快速沃尔什变换规划中bitwise_xor_convolutionbitwise_and_convolution
- 子集卷积与集合幂级数规划中subset_convolutionexp_of_set_power_series
- GCD 与 LCM 卷积规划中gcd_convolutionlcm_convolution
- 多项式复合与复合逆规划中composition_of_formal_power_seriescompositional_inverse_of_formal_power_series
线性代数
矩阵运算、消元、行列式与线性基。
- 矩阵乘法与快速幂规划中matrix_productpow_of_matrix
- 高斯消元规划中system_of_linear_equationsmatrix_rank
- 行列式规划中matrix_detmatrix_det_arbitrary_mod
- 矩阵求逆规划中inverse_matrix
- 线性基规划中intersection_of_f2_vector_spaces
- 异或方程组与 bitset 消元规划中system_of_linear_equations_mod_2matrix_rank_mod_2
- 矩阵树定理规划中counting_spanning_tree_undirectedcounting_spanning_tree_directed
- 特征多项式规划中characteristic_polynomial
- BEST 定理规划中counting_eulerian_circuits
概率与博弈
期望的线性性、随机过程与组合博弈。
- 概率与期望的线性性规划中
- 随机游走与马尔可夫链规划中
- Nim 游戏规划中nim_product_64
- SG 函数规划中
- 常见博弈模型规划中
计算几何
在精度和退化情况下可靠地实现几何谓词与经典算法。
- 向量、点积与叉积规划中
- 线段相交与点线关系规划中
- 多边形面积与点在多边形内规划中count_points_in_triangle
- 极角排序规划中sort_points_by_argument
- 凸包规划中static_convex_hullconvex_layers
- 旋转卡壳规划中furthest_pair
- 半平面交规划中
- 平面最近点对规划中closest_pair
- 圆与最小圆覆盖规划中minimum_enclosing_circle
- 扫描线规划中area_of_union_of_rectangles
- Pick 定理规划中
- 曼哈顿距离与切比雪夫距离规划中manhattanmst
- 三维计算几何基础规划中
离线与分治技巧
通过调整处理顺序或整体处理询问来降低复杂度。
- 离线询问与排序规划中
- CDQ 分治规划中
- 整体二分规划中
- 线段树分治规划中dynamic_graph_vertex_add_component_sum
- 根号分治规划中
- 启发式合并规划中