Alg-DS Idiom

alg_ds.mdown

Algorithm & Data Structures

[TOC]

#

• 2-SAT
• 2-3 Tree / 2-3-4 Tree
• 2-3 Heap
• <bits/stdc++.h>
• <ext/pb_ds/...>
• ([exp1] ? [exp2] : [exp3]) = [exp4] -> *((int *)([exp1] * long(&[exp2]) + ![exp1] * long(&[exp3]))) = [exp4]
• 位运算
• • x + y = x | y + x & y
• 杂题

A

• A*算法
• • IDA*
• • D*
• AC自动机 (ACAM)
• AC自动人偶 (Automation)
• AKS素性检测
• • https://en.wikipedia.org/wiki/AKS_primality_test
• • www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
• AGM方法(计算初等函数/pi)
• AOE网
• AOV网
• All-Pairs Similarity Search
• • https://www.zhihu.com/question/56380937
• 阿克曼函数 Ackermann
• adaptive algorithm
• • 适应性Huffman coding
• • • FGK
• • • Vitter
• AList
• And-or tree
• (a,b)-tree
• And-inverter graph
• AES-GCM-SIV
• AAA树
• Anluin's Learning Algorithm
• A power b mod m
• • ref
• 埃拉托色尼筛法
• • 求逆元

B

• Boyer-Moore 字符串匹配
• KMP 字符串匹配
• 倍增算法
• 并查集
• • 路径压缩
• • 按秩合并
• B树
• B+树
• B*树
• B-树
• Bx-树
• Bk-树
• • ref
• Border Tree
• B-trie
• 背包算法
• • 无界背包问题
• • 部分背包
• • 01背包
• • 完全背包
• • 多重背包
• • 分组背包
• • 带依赖背包
• • 泛化物品背包
• • 树形依赖背包
• BFS
• • BFS树
• Bellman-Ford
• • Yen-氏优化
• • 差分约束系统
• Burnside引理
• 博弈论
• BSGS （大小步）算法
• 半平面交
• 博弈树
• Bitset
• Bitmap
• • 求交集/并集/差集
• __builtin_xxx
• • popcount-parallel
• Binary Index Tree （树状数组）
• Black Box Linear Algebra
• Baillie–PSW
• Brodal queue
• Base64
• Buffer tree
• Bell(n) 贝尔数
• • n元集合划分方法数
• 伯努利数
• BSTW
• Beap
• Brodal queue
• BK-tree (模糊匹配)
• BSP tree
• Bin
• BWT
• 波兰表
• BBP （求pi）
• BFPRT
• Bush-Game
• brotlilz
• Boruvka

C

• CDQ分治
• 除法取模
• Cache优化
• Chen-Fox-Lyndon Theorem
• 差分约束
• CRT（中国剩余定理）
• 操作树
• Colussi（字符串匹配）
• Crochemore Perrin
• Compression
• • Run-length encoding
• • DFT
• • DCT （矩阵）
• • SVD
• 乘法
• • comba
• • karatsuba
• • toom cook
• • FFT
• • • 任意质数p模意义下FFT
• • FNT （快速数论变换） -> CRT优化
• • Schnhage–Strassen algorithm
• • Furer's algorithm
• 插值
• • 非负整系数:
• • • 输入1，输出S。
• • • 输入(S+1)，输出M。把M转化到(S+1)进制，每一个数位上的数就对应了原多项式的系数。
• • • 或者求f(x), f(f(x))转换到f(x)进制
• • 拉格朗日+分治/FFT
• • Neville/牛顿
• 长链剖分
• C-trie
• Cover tree
• 磁盘阵列负载均衡算法
• 次小生成树
• 次小最短路
• Cado-nfs
• cache blocking techniques
• compile-optimizations
• ref
• cipolla

D

• Dinic
• • 当前弧优化
• • 单路增广
• • 多路增广
• • 预流推进
• DFS
• • DFS序 DFS树
• 点分治
• 带花树 (Blossom Tree) （及加权版）
• 单纯形（线性规划）
• 杜教筛
• 点分治
• 多项式逆元
• 多项式拟合
• Duff's Device
• Dancing Links (DLX)
• • 精确覆盖
• Dynamic Graph
• 笛卡尔树
• Duval 算法
• 动态规划
• • 状态压缩
• • 线性/区间/坐标/背包/树型/概率/数位/插头动规/集合
• • 斜率优化
• • 决策单调性
• • 四边形不等式
• Dijkstra
• Dirichlet卷积
• 动态分治
• • 点/树
• 点在多边形内判定
• 点集直径
• • 旋转卡壳
• • 对踵点
• Delaunay三角剖分
• 对偶图
• 对顶堆
• 动态图
• 动态平面点定位
• D-ary heap
• 狄利克雷卷积 （积性函数）
• 等价流树
• • gusfiled
• • gomory hu tree
• De Brujin
• • ref
• Dinkelbach
• 多元函数gcd
• 地图生成
• • 柏林噪声
• • 随机游离(圆)

E

• 二分图
• • 匹配
• • • 无权/带权无向图匹配 
• • 染色
• • 匈牙利算法
• • Dinic
• • Hopcroft-Karp
• 二进制分组
• 二叉搜索树
• 二项堆
• • 斐波那契堆
• • • AF heap
• 二叉堆
• • 双端堆
• • 最大-最小堆
• 二维数点
• Euler Tour Tree
• Exgcd
• 二进制法（博弈）
• Edmonds-Karp (BFS最大流)
• Exponential tree
• Enfilade
• EM
• ECC (椭圆曲线)
• Exponential by square
• • Montgomery's ladder technique (avoid side-channel attack)

F

• FFT （快速傅里叶变换） (radix-2)
• • 母函数
• • 2^k
• • 三进制
• • 原根/阶
• FWT (Fast Walsh-Hadamard Transform)
• 分块
• • 分块套分块
• Floyd（点对）
• Floyd判圈
• Finger tree (FGT)
• fhq Treap
• 斐波那契堆
• Fusion Tree
• 分数规划
• 分治
• • 二分
• • 三分
• Four Russians
• Ford-Fulkerson
• fread/fwrite
• Fisher-Yates
• Fenwick tree （范围树）
• Flood-Fill
• 反演
• • Mobius
• • 二项式 -> 容斥 -> 下三角矩阵/逆矩阵
• Fractional Cascading
• • http://blog.csdn.net/liuqiyao_01/article/details/8478719
• funnel sort
• frobenius自同态
• FGK
• Fermat 平方和定理
• fat node 持久化手段

G

• Goldreich-Levin算法
• 高斯消元
• 高维前缀和
• 归并树
• 高精度
• Graham扫描外接凸多边形
• • 水平序
• • 极角序
• Gift wrapping
• Golden-section Search
• Galil-Giancarlo
• GNFS
• • O(e^(((64/9)^(1/3)+o(1))*(ln(n))^(1/3)*(ln(ln(n)))^(2/3)))
• 格林公式
• Gray码
• 公平组合游戏
• Gap buffer
• GMM
• Grisu3 (float->string)
• 高斯整数
• 滚动数组

H

• 后缀自动机 (SAM)
• 后缀树
• • generalised suffix tree
• 后缀数组
• • 倍增 DA
• • DC3
• • SA-IS (Linear Suffix Array Construction by Almost Pure Induced-Sorting)
• • • ref
• • 最长公共前缀
• • 最长回文
• • compressed suffix array
• • FM-index
• 回文自动机 (PAM)
• 环套树
• 环加外向树
• 划分树
• 回文树
• 红黑树
• • 4阶B树
• • • 红节点和他的父节点当成一个节点看待。这样每个黑节点可以有0-4个子节点, 然后黑节点本身又是平衡的。
• • ref:《SGI STL》
• Hash
• • perfect hashing (dynamic perfect hash table)
• • virtual hashing
• • universal hashing
• • double hashing
• • Bloom filter
• • quotient filter
• • Count-Min sketch
• • Koorde
• • prefix hash tree
• • rolling hashing
• • minhash
• • https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/
• • ref:《SGI STL》
• • Rabin-Karp rolling hash
• • ref
• • Zobrist
• Hamilton-Cayley 定理
• 哈夫曼树
• 合并线性基
• 环形缓冲区
• 霍夫圆
• Hashed array tree
• Heavy-light/Heavy-path Decomposition (树链剖分/轻重链划分)
• Householder变换
• HAT-trie
• • implement

I

• IDA* （迭代加深搜索）
• ICP匹配
• Interval tree
• ISAP
• IDDFS

J

• 均摊分析
• 交互式证明
• 煎饼排序
• 静态树
• 矩阵分解
• • LU
• • QR
• • Schur
• • SVD
• • Jordan标准型
• 记忆化
• Johnson算法（图论）
• 矩阵幂
• • 模意义 https://www.zhihu.com/question/35758656/answer/76347094
• • 分治
• 矩阵乘法
• • K算法
• • Strassen
• 积性函数前缀和
• 卷包裹法
• 矩阵树定理
• JPS+
• • http://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than
• 竞赛图
• 竞争分析
• 菊花图
• Judy array
• 矩阵费马小定理
• 结式 (Resultant)

K

• 可并堆
• KD Tree
• • implict k-d tree
• • min/max k-d tree
• • relaxed k-d tree
• • adaptive k-d tree
• 块状树
• 可持久化数据结构
• • zkw线段树
• • 主席树
• • fhq Treap
• • 可持久化线段树
• • 可持久化队列
• • 可持久化栈
• • 可持久化并查集
• • 可持久化堆
• • 可持久化线段树
• • 可持久化Treap
• Kirchoff定理（图论）
• Kirchoff矩阵
• k阶线性递推-特征多项式
• 快速幂 （矩阵/非矩阵）
• 卡特兰数
• 康托展开
• 快速数论变换
• KMP
• • 扩展KMP (exkmp)
• Karp-Rabin
• Karatsuba
• Kinetic data structure
• K-ary tree
• K-means
• KRT (网络流O(VE))
• Kadane’s algorithm (max subarray)
• Kosaraju
• Kahan sum (floating number)

L

• LCT (link-cut tree)
• 链剖
• 连通分量
• • 强连通分量
• • 双连通分量
• 离线算法
• LCA 最近公共祖先
• LCP 最长公共前缀
• LIS 最长上升子序列
• LCS 最长公共子序列
• LA (level ancestor) k-祖先
• • https://riteme.github.io/blog/2017-2-6/long-chain.html
• 连通性维护
• Lucas定理
• Lyndon word
• 拉格朗日插值
• 粒子群优化
• LZ77/LZW
• 离散化数组
• • 1~INT_MAX =>

struct element {
	int value, ord;
}

• LCT (linear recurrence random generator)
• lowbit
• 类欧几里得算法
• 李超线段树
• list labeling
• Leonardo heap
• Leftist heap
• Lightmap
• 轮廓线
• Lindström–Gessel–Viennot定理
• Left-child right-sibling binary tree
• 离散对数
• Log structured merge tree
• • ref

M

• Minimum Cut-Cut
• Matrix Tree
• 莫比乌斯反演
• 莫队算法
• Miller-Rabin素性检
• • 二次探测定理
• 模线性方程组
• Manacher（最长回文字串）
• 曼哈顿树
• 模拟退火
• Misere Play
• 灭绝树
• Montgomery
• Meet in the middle
• Merkle tree
• Metric tree
• M tree
• Multiplicative group of integers module n
• • ref
• micro-macro decomposition
• Mertens's function
• Myers Diff
• • ref

N

• 快速数论变换 (NTT) (radix-2)
• 牛顿迭代
• 拟阵
• Nim-Game
• Nagle算法
• NFA-DFA
• 逆元
• • ref

O

• 欧几里得算法
• • 最小生成树 (V图)
• 欧拉回路
• 欧拉序
• Octree
• • linear octree
• Order statistic tree

P

• 平衡树
• • AVL
• • RBT 红黑树
• • SBT
• • Treap 树堆
• • 替罪羊树
• • Splay
• 剖分
• • 梯子剖分
• • 长链剖分
• PQ Tree
• Polya计数定理
• Prufer编码
• 剖析树
• 配对堆 (Pairing)
• Pollard's rho
• • 期望O(v^0.5 lg(v))
• Pointer machine
• Pairing heap
• Patricia
• Pretty Diff
• • ref
• • ref
• Parent pointer tree (Spaghetti stack)
• • ref
• pdqsort pattern-defeating quick sort

Q

• 轻重链剖分
• 启发式算法
• • 启发式合并
• 前缀树
• Quine（输出自己的程序）
• 前向星/后向星
• 圈套圈算法
• QS-Sunday
• 强联通分量
• • Kosaraju
• • Tarjan
• • Gabow
• Quad tree
• Quick Hull
• （盲填）骑士跳

R

• 容斥定理
• R树
• Range tree
• RMQ 区间最值查询
• Relabel To Front
• • push-relabel
• Reservior sampling
• Ransac
• RSA
• • CCA
• • Wiener
• Rose tree
• R tree
• • Hilbert R tree
• R+ tree
• R* tree
• RB tree
• • ref:《SGI STL》
• RRT (Rapidly-exploring random tree)
• radix-2/4/...
• • FFT/NTT butterfly operator size=2
• std::rotate 队列rotate操作
• Rosser theorem (nthprime)
• • ref

S

• 三叉链表
• 树链剖分
• • 轻重边
• • 重边先行
• Schreier–Sims algorithm
• SPFA
• • SLF：Small Label First
• • LLL：Large Label Last
• • Shuffle边表
• 随机化
• 扫描线算法
• 树套树
• 势能分析
• ST表 (Sparse Table)
• Skip List （跳表）
• Splay
• • 单旋
• • 双旋
• • top-down
• SBTree
• 四分树
• 八叉树
• 斯坦纳树
• • rectilinear
• 缩环树
• Schur定理
• 素数筛 (O(N))
• 生成函数
• 生成树
• • 最小mst
• • 第k小
• • 最优比率
• • • 分数规划
• • 0/1分数规划
• • 度限制
• 树分治
• 随机增量算法
• • 最小圆覆盖
• • 半平面交
• • Delaunay
• • 梯形图点定位
• SG函数
• 十字链表
• 双向广度搜索
• SAP (shortest augmenting path)（增广路最大流）
• Shift Or匹配
• 时间轮算法
• Shor
• string matching
• • Brute-Force
• • KMP/扩展KMP
• • Boyer-Moore
• • • Boyer-Moore-Horspool
• • • • ref
• • Galil-Giancarlo
• • Colussi
• • Horspool
• • Sunday
• • Manacher (回文)
• 树状数组
• • 求逆序对 (=> 归并排序交换数)
• • • 01逆序对O(n)
• • lowbit
• • 二维
• Simpson积分
• Surreal number
• Shunting-yard algorithm
• SSA (Schönhage–Strassen algorithm)
• Square on Tree
• 素数生成
• • 线性同余
• • Mersenne Twister
• • Lagged Fibonacci
• • WELL512
• 深度和
• suffix-tray
• suffix-trist
• 四边形不等式
• Succinct data structure
• SHA
• Sprague-Grundy定理
• 树形图
• Soft heap
• Skew heap
• SPQR tree
• Spaghetti stack
• Scene graph
• SIFT
• 四元数，欧拉角
• 水波模拟算法
• 树上操作
• • 树上SA/波兰表
• 四平方和构造算法
• simplex (三维线性规划)
• stein gcd

T

• 拓扑排序
• Top Tree (self-adjusting)
• Tango tree
• 图的树分解
• 凸包
• Tarjan (2-sat)
• 梯度下降
• two-pointer
• T tree
• Thread binary tree
• Ternary heap
• 图片主题色提取
• • https://xcoder.in/2014/09/17/theme-color-extract/
• Top K
• • quickselect/divideselect
• • radix
• • minheap
• topological algorithm
• tonelli-shanks

U

• UB tree

V

• veb树
• Voronoi图
• V算法
• Viterbi算法
• VP tree
• Vlist

W

• 网络流
• • 最大流
• • 最小割
• • 费用流
• • 设施选址
• WELL512
• WAM
• • unification
• WAVL tree
• Weight-balanced tree
• • CLJ 重量平衡树
• Weak heap
• WBLT
• wu manber
• wheel sieve
• Wythoff Game

X

• 斜率优化
• 线段树（染色）
• • 实时开节点的线段树
• • 可持久化线段树
• • 时间线段树
• • 李超线段树
• 循环卷积（倍长，求幂）
• 虚树
• 旋转卡壳
• 仙人掌
• 异或算法
• 线性规划
• 斜堆
• 辛普森积分
• 序列自动机
• 线性基
• • 合并线性基
• 小波树
• xy-fast tree
• 匈牙利树
• 线索二叉树
• X tree
• 线索树

Y

• 预流推进
• • HLPP
• • 最大标号
• 圆方树
• 原始－对偶算法
• 约当消元
• 蚁群优化
• 遗传算法
• （椭）圆上整点
• Young tableau
• • hook length formula
• 压缩算法
• • lzma
• • blosclz
• • zstd
• • snappy
• Y-fast

Z

• 字符串压位 (shift-and)
• 整体二分
• 主席树
• • 函数式
• • 区间k大
• 字典树 (Trie Tree)
• 在线算法
• zkw线段树
• 状态机
• • DFA
• • NFA
• 最小表示(字符串)
• 支配树
• 左偏树
• 最小生成树
• • 曼哈顿/欧几里得距离
• • prim
• • kruskal
• • 矩阵树
• 最小树形图 （有向MST）
• 最小覆盖
• • 最小覆盖圆
• • 最小外接圆
• • 最小链覆盖
• • 最小点覆盖
• 最小二乘法
• 最小点基
• 最小瓶颈生成树 (瓶颈路/BEQ)
• • 树上路径最值 (O(n alpha n)-O(1))
• 最近点对
• 最长公共前缀
• 最大权闭合图
• 字典树
• 左偏树
• 最小耗散优先
• 最短路径
• • 01
• • 非负边权
• • 负边权
• 最大匹配
• • 有向图 最小路径覆盖
• • 0/1矩阵 最小覆盖
• • 最大子矩阵
• 正交区间查询
• Zhu-Takaoka 字符串匹配
• Z-order
• Zero-suppressed decision diagram
• 重量/权值左偏树
• 洲阁筛
• Zeckendorf定理
• 朱刘算法及其优化
• Z3 prover