数据结构 Part.1 zerol.

Presentation on theme: "数据结构 Part.1 zerol."— Presentation transcript:

1 数据结构 Part.1 zerol

2 树状数组

3 特性 定义 lowbit(x) 为 1<<(x 二进制表示末尾 0 的个数)
下标 x 表示 (x-lowbit(x),x] 的和 查询前缀和 单点修改

4 差分 修改差分 差分前缀和 差分前缀和的前缀和 二维 二维差分

5 稀疏表

6 特性 预处理 f[i][j] 表示从 i 开始长为 2^j 的区间的最值 预处理 查询

7 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]); } };

8 并查集

9 按秩合并 路径压缩 信息维护

10 可回滚并查集 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; } } }

11 持久化并查集 持久化数组 只能按秩合并