数据结构全家桶：树状数组、平衡树、分块与莫队算法

继续数据结构系列，本期带来中级数据结构的全面讲解。

一、树状数组（Fenwick Tree）
小巧精悍，代码量极小。

• 单点修改 + 前缀查询（最基本）


• 区间修改 + 单点查询（差分）


• 区间修改 + 区间查询（维护两个 BIT）


• 二维树状数组

// 单点加，前缀和查询
void add(int x, int v) { for (; x <= n; x += x & -x) c[x] += v; }
int sum(int x) { int s = 0; for (; x; x -= x & -x) s += c[x]; return s; }

• Treap：BST + 堆性质，通过随机优先级保持平衡


• Splay：伸展树，常用于 LCT 的辅助数据结构


• FHQ Treap（非旋 Treap）：基于分裂/合并，支持可持久化


• 对于竞赛，推荐学习 FHQ Treap，功能强大且代码简洁

• 区间修改 + 区间查询分块


• 莫队算法（本质是离线分块）

• 路径压缩 + 按秩合并


• 带权并查集（维护边权关系）


• 可撤销并查集（按时间回溯）


• 种类并查集（维护对立关系）

1. 树状数组：洛谷 P3374 入门


2. FHQ Treap：洛谷 P3369 普通平衡树


3. 莫队：洛谷 P1494 小Z的袜子


4. 可撤销并查集：洛谷 P3402 可持久化并查集