ZROI学习笔记——Week 1

Michael Wong - 二两碘酊 / 2023-07-17 / 原文

7.17 Day 1 - 基础数据结构

按秩合并：将小子树作为大子树的儿子，维持深度在 \(O(\log n)\) 级别。

void merge(int x,int y) {
    if(size[x=get(x)]<size[y=get(y)]) std::swap(x,y);
    size[x]+=size[y],fa[y]=x;
}

后两者结合：时间复杂度为 \(O(n \alpha(n) + q)\)，其中 \(\alpha\) 为反阿克曼函数。

单变量反 Ackermann 函数（简称反 Ackermann 函数）\(\alpha(x)\) 定义为最大的整数 \(m\) 使得 \(Ackermann(m,m) \leq x\)。因为 Ackermann 函数的增长很快，所以其反函数 \(\alpha(x)\) 的增长是非常慢的，对所有在实际问题中有意义的 \(x\)，\(\alpha(x) \leq 4\)，所以在算法时间复杂度分析等问题中，可以把 \(\alpha(x)\) 看成常数。
撤销上一个合并操作：抛弃路径压缩，只使用按秩合并，撤销时删边重新计算子树大小即可。
Kruskal 重构树：合并根节点 \(u,v\) 时，新建节点 \(w\)，将 \(u,v\) 作为 \(w\) 的儿子，得到的树称为 Kruskal 重构树。可以处理与时间相关的查询问题，例题将在倍增后揭晓。

倍增求 LCA：\(f(u,i)\) 为节点 \(u\) 向上跳 \(2^i\) 步到达的节点，则有

\[f(u,i)=f(f(u,i-1),i-1), \]
预处理 \(f\) 即可 \(O((n+q) \log n)\) 求 LCA。
Kruskal 重构树：合并时新建的节点 \(w\) 带 时间属性，可以搭配倍增求 LCA 支持 可持久化并查集在线查询。

我必须说明 ST 是 Sparse Table（稀疏表）的缩写，我发现有好多人都不知道它名字的真正来源。

ST 用于解决 RMQ 问题（区间最值问题，Range Minimum/Maximum Query），或者其他 可重复贡献问题（即区间重合不影响运算结果的问题，比如取 \(\min\) ）。

比如取 \(\min\)，则有

\[mn(u,i)=\min (mn(u,i-1),mn(u+2^{i-1},i-1)), \]

\(\Theta(n \log n)\) 预处理 \(mn\) 即可 \(O(1)\) 解决 RMQ。

单点修改，维护前缀，区间查询。

基础做法：lowbit。
BIT 上二分：从高到低决定 \(x\) 的每一个二进制位是 \(0\) 还是 \(1\)，可以给二分降一个 \(\log\)，降成 \(O(\log n)\)。

实际上，BIT 就是省略了右儿子的线段树，因此线段树的功能完全包含 BIT，但为此付出的代价是 \(2 \sim 10\) 倍的常数。将 BIT 的树状结构牢记于心，可以更好理解 BIT 倍增. —— Alex Wei