一、并查集

1. 普通并查集

const int N = 100010;
int fa[N];
// 初始化
void init() { for(int i = 0; i < N;) fa[i] = i ++; }
// 合并 x 与 y 所在的集合
void merge(int x, int y) { fa[get(x)] = y; }
// 获取 x 的祖先
int get(int x) { return (fa[x] != x ? get(fa[x]) : fa[x]); }

2. 路径压缩 + 按秩归并

const int N = 100010;
int fa[N], s[N];
// 初始化
void init() { for(int i = 0; i < N;) s[i] = 1, fa[i] = i ++; }
// 合并 x 与 y 所在的集合
void merge(int x, int y) { (s[x] > s[y] ? fa[get(x)] = get(y), s[y] += s[x] : fa[get(y)] = get(x), s[x] += s[y]); }
// 获取 x 的祖先并进行路径压缩
int get(int x) { return (fa[x] != x ? fa[x] = get(fa[x]) : fa[x]); }

ToDo:

1. 并查集
   a. √ 普通并查集
   b. √ 路径压缩 + 按秩归并
   c. next 数组优化
   d. 带权并查集
   e. 拓展域并查集
2. 树状数组
   a. 单点修改 + 区间查询
   b. 单点查询 + 区间修改
   c. 区间查询 + 区间修改
   d. 二维单点修改 + 区间查询
   e. 二维单点查询 + 区间修改
3. 线段树
4. Trie 树
   a. 普通 Trie 树
   b. 0-1 Trie
5. 堆
   a. 普通堆
   b. 对顶堆
6. 平衡树
   a. 笛卡尔树
   b. Treap
   a. 普通 Treap
   b. FHQ-Treap
   c. Splay