数据结构 Part.1 zerol
树状数组
特性 定义 lowbit(x) 为 1<<(x 二进制表示末尾 0 的个数) 下标 x 表示 (x-lowbit(x),x] 的和 查询前缀和 单点修改
差分 修改差分 差分前缀和 差分前缀和的前缀和 二维 二维差分
稀疏表
特性 预处理 f[i][j] 表示从 i 开始长为 2^j 的区间的最值 预处理 查询
namespace rmq { int f[maxn][20]; inline int highbit(int x) { return 31 - __builtin_clz(x); } void init(int* v, int n) { FOR (i, 0, n) f[i][0] = v[i]; FOR (x, 1, highbit(n) + 1) FOR (i, 0, n - (1 << x) + 1) f[i][x] = min(f[i][x - 1], f[i + (1 << (x - 1))][x - 1]); } int get_min(int l, int r) { assert(l <= r); int t = highbit(r - l + 1); return min(f[l][t], f[r - (1 << t) + 1][t]); } };
并查集
按秩合并 路径压缩 信息维护
可回滚并查集 namespace uf { int fa[maxn], sz[maxn]; int undo[maxn], top; void init() { memset(fa, -1, sizeof fa); memset(sz, 0, sizeof sz); top = 0; } int findset(int x) { while (fa[x] != -1) x = fa[x]; return x; } bool join(int x, int y) { x = findset(x); y = findset(y); if (x == y) return false; if (sz[x] > sz[y]) swap(x, y); undo[top++] = x; fa[x] = y; sz[y] += sz[x] + 1; return true; } inline int checkpoint() { return top; } void rewind(int t) { while (top > t) { int x = undo[--top]; sz[fa[x]] -= sz[x] + 1; fa[x] = -1; } } }
持久化并查集 持久化数组 只能按秩合并