Useless Algorithms

If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

—— $\textcolor{black}{\text{U}}\textcolor{red}{\text{m_nik}}$

本文来自 $\textcolor{black}{\text{U}}\textcolor{red}{\text{m_nik}}$ 的 CodeForces 博客，大多是一些强大复杂但是不一定有用的算法或数据结构。

• 李超线段树；
• 吉司机线段树；
• RMQ in $O(n)\sim O(1)$；
• Treap 以外的平衡二叉树；
• 动态树；
• 小波树（Wavelet tree）¹；
• 归并树²；
• 二项堆；
• 斐波那契堆；
• 左偏树；
• 支配树；
• 3-connected components in $O(n)$ ³；
• $k$ 短路⁴；
• 一般图最大匹配；
• 一般图最大权匹配；
• 网络流最大流-预流推进算法；
• 多项式内的最小费用最大流；
• $O(E\log V)$ 的最小树形图；
• 后缀树；
• 在线二维凸包；
• 三维凸包；
• 半平面交；
• Voronoi 图 / 三角剖分；
• 多项式常见操作 (exp, log, sqrt, …)；
• 生成函数；
• 拉格朗日反演；
• That derivative magic by $\textcolor{red}{\text{Elegia}}$³；
• That new subset convolution derivative magic by $\textcolor{red}{\text{Elegia}}$³；
• 扫描线莫队 / 莫队二次离线；
• Matroid intersection³。