欢迎来到 Milk_Dragon 的算法笔记

一篇文章

ST表&RMQ ST表常用来快速求区间最值，即RMQ问题。 设 $ f_{i,j} $ 表示区间 $ [i,i+2^j-1] $ 中的最大值，显然 $ f_{i,j}=max(f_{i,j-1},f_{i+2^{j-1},j-1}) $。 查询时，我们设 $ k=log_{2}(r-l+1) $，所以答案为 $ max(f_{l,k},f_{r-2^k+1,k}) $。 ...

前缀和&二维前缀和 一维前缀和：没什么好讲的。 二维前缀和： 设 $f_{i,j}$ 表示左上角为 $(0,0)$，右下角为 $(i,j)$ 的矩阵中所有数的和，则根据容斥原理，$f_{i,j}=a_{i,j}+f_{i-1,j}+f_{i,j-1}-f_{i-1,j-1}$。如图所示： ...

树上LCA 倍增法 设 $f_{i,j}$ 为第 $i$ 个点往上跳 $2^j$ 个点所到的点，显然 $f_{i,0}$ 为第 $i$ 个点的父亲。 对于点 $u,v$，我们只需要将它们调整至同一深度，然后一起往上跳（不能重合）直到不能再跳，则最后它们的父亲就是 $lca(u,v)$。 ...

线段树 线段树常用来高效进行区间修改和区间查询，其实际上为一个二叉树，每一个节点都存储着一段区间的信息。假设 $i$ 号点维护的区间是 $[l,r]$，则其左儿子 $2i$ 维护的区间为 $[l,\left \lfloor \frac{l+r}{2} \right \rfloor ]$，其右儿子 $2i+1$ 维护的区间为 $(\left \lfloor \frac{l+r}{2} \right \rfloor,r]$。如图所示。 ...