3921 字
20 分钟
高级数据结构详解：从CSP-S到IOI
高级数据结构详解：从CSP-S到IOI
在算法竞赛中，数据结构是解决复杂问题的关键工具。本文将系统讲解从CSP-S到IOI级别的高级数据结构，包括原理分析、代码实现和实战应用。
1. 线段树（Segment Tree）
线段树是一种用于解决区间查询和修改问题的树形数据结构，支持O(log n)的查询和修改操作。
1.1 基本原理
线段树将区间递归地二分，每个节点维护一个区间的信息（如和、最大值、最小值等）。对于长度为n的数组，线段树是一棵完全二叉树，高度为log n。
核心性质：
- 父节点区间是子节点区间的并集
- 叶子节点对应数组的单个元素
- 空间复杂度：O(4n)
1.2 基础实现（区间求和）
class SegmentTree {private: vector<long long> tree; vector<long long> arr; int n;
void build(int node, int start, int end) { if (start == end) { tree[node] = arr[start]; return; } int mid = (start + end) / 2; int leftNode = 2 * node; int rightNode = 2 * node + 1;
build(leftNode, start, mid); build(rightNode, mid + 1, end); tree[node] = tree[leftNode] + tree[rightNode]; }
void updateRange(int node, int start, int end, int l, int r, long long val) { if (start > r || end < l) return; if (start == end) { tree[node] += val; return; } int mid = (start + end) / 2; updateRange(2 * node, start, mid, l, r, val); updateRange(2 * node + 1, mid + 1, end, l, r, val); tree[node] = tree[2 * node] + tree[2 * node + 1]; }
long long queryRange(int node, int start, int end, int l, int r) { if (start > r || end < l) return 0; if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2; long long leftSum = queryRange(2 * node, start, mid, l, r); long long rightSum = queryRange(2 * node + 1, mid + 1, end, l, r); return leftSum + rightSum; }
public: SegmentTree(vector<long long>& nums) { n = nums.size(); arr = nums; tree.resize(4 * n); build(1, 0, n - 1); }
void update(int l, int r, long long val) { updateRange(1, 0, n - 1, l, r, val); }
long long query(int l, int r) { return queryRange(1, 0, n - 1, l, r); }};1.3 懒惰标记（Lazy Propagation）
对于区间修改操作，使用懒惰标记可以将时间复杂度从O(n log n)优化到O(log n)。
class LazySegmentTree {private: vector<long long> tree, lazy; int n;
void pushDown(int node, int start, int end) { if (lazy[node] != 0) { tree[node] += (end - start + 1) * lazy[node]; if (start != end) { lazy[2 * node] += lazy[node]; lazy[2 * node + 1] += lazy[node]; } lazy[node] = 0; } }
void updateRange(int node, int start, int end, int l, int r, long long val) { pushDown(node, start, end); if (start > r || end < l) return;
if (l <= start && end <= r) { lazy[node] += val; pushDown(node, start, end); return; }
int mid = (start + end) / 2; updateRange(2 * node, start, mid, l, r, val); updateRange(2 * node + 1, mid + 1, end, l, r, val);
pushDown(2 * node, start, mid); pushDown(2 * node + 1, mid + 1, end); tree[node] = tree[2 * node] + tree[2 * node + 1]; }
long long queryRange(int node, int start, int end, int l, int r) { if (start > r || end < l) return 0; pushDown(node, start, end);
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2; return queryRange(2 * node, start, mid, l, r) + queryRange(2 * node + 1, mid + 1, end, l, r); }
public: LazySegmentTree(int size) : n(size) { tree.resize(4 * n); lazy.resize(4 * n); }
void update(int l, int r, long long val) { updateRange(1, 0, n - 1, l, r, val); }
long long query(int l, int r) { return queryRange(1, 0, n - 1, l, r); }};复杂度分析：
- 建树：O(n)
- 单点/区间修改：O(log n)
- 区间查询：O(log n)
- 空间：O(4n)
适用场景：区间和、区间最值、区间GCD、区间加、区间乘等。
2. 树状数组（Binary Indexed Tree / Fenwick Tree）
树状数组是一种代码简洁、常数小的数据结构，主要用于高效地进行前缀和查询和单点修改。
2.1 基本原理
树状数组利用二进制的性质，每个位置存储一段区间的和。核心函数：
lowbit(x) = x & (-x)：获取x的最低位1
性质：
- tree[i] 管理区间 [i - lowbit(i) + 1, i]
- 空间复杂度：O(n)
2.2 基础实现
class BIT {private: vector<long long> tree; int n;
int lowbit(int x) { return x & (-x); }
public: BIT(int size) : n(size) { tree.resize(n + 1); }
// 单点修改：位置 pos 增加 val void update(int pos, long long val) { for (int i = pos; i <= n; i += lowbit(i)) { tree[i] += val; } }
// 查询前缀和 [1, pos] long long query(int pos) { long long sum = 0; for (int i = pos; i > 0; i -= lowbit(i)) { sum += tree[i]; } return sum; }
// 查询区间和 [l, r] long long queryRange(int l, int r) { return query(r) - query(l - 1); }};2.3 高级应用
1. 区间修改，单点查询（差分数组）
class RangeUpdateBIT {private: BIT diff; int n;
public: RangeUpdateBIT(int size) : n(size), diff(size) {}
// 区间 [l, r] 增加 val void updateRange(int l, int r, long long val) { diff.update(l, val); diff.update(r + 1, -val); }
// 查询单点值 long long query(int pos) { return diff.query(pos); }};2. 区间修改，区间查询（双树状数组）
class RangeUpdateRangeQuery {private: BIT tree1, tree2; // tree1存d[i], tree2存i*d[i] int n;
public: RangeUpdateRangeQuery(int size) : n(size), tree1(size), tree2(size) {}
void updateRange(int l, int r, long long val) { tree1.update(l, val); tree1.update(r + 1, -val); tree2.update(l, val * (l - 1)); tree2.update(r + 1, -val * r); }
long long query(int pos) { return pos * tree1.query(pos) - tree2.query(pos); }
long long queryRange(int l, int r) { return query(r) - query(l - 1); }};复杂度分析：
- 修改/查询：O(log n)
- 空间：O(n)
适用场景：前缀和、逆序对、动态中位数、二维区间和。
3. 并查集（Union-Find / Disjoint Set Union）
并查集是一种用于处理不相交集合合并和查询问题的数据结构。
3.1 优化实现
class UnionFind {private: vector<int> parent, rank; int count; // 连通分量个数
public: UnionFind(int n) : count(n) { parent.resize(n); rank.resize(n, 1); for (int i = 0; i < n; i++) { parent[i] = i; } }
// 路径压缩 int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; }
// 按秩合并 bool unite(int x, int y) { int rootX = find(x); int rootY = find(y);
if (rootX == rootY) return false;
if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } count--; return true; }
bool connected(int x, int y) { return find(x) == find(y); }
int getCount() { return count; }};3.2 带权并查集
class WeightedUnionFind {private: vector<int> parent; vector<long long> weight; // 到父节点的权值
public: WeightedUnionFind(int n) { parent.resize(n); weight.resize(n, 0); for (int i = 0; i < n; i++) { parent[i] = i; } }
int find(int x) { if (parent[x] != x) { int root = find(parent[x]); weight[x] += weight[parent[x]]; parent[x] = root; } return parent[x]; }
bool unite(int x, int y, long long w) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) return false;
parent[rootX] = rootY; weight[rootX] = weight[y] - weight[x] + w; return true; }
long long getWeight(int x, int y) { if (find(x) != find(y)) return LLONG_MAX; return weight[x] - weight[y]; }};复杂度分析：
- find/unite：O(α(n))，α为阿克曼函数的反函数，近似O(1)
- 空间：O(n)
适用场景：连通性判断、最小生成树（Kruskal）、动态连通性。
4. 单调栈和单调队列
4.1 单调栈
单调栈用于解决”下一个更大元素”类问题。
// 找每个元素右边第一个比它大的元素vector<int> nextGreaterElement(vector<int>& nums) { int n = nums.size(); vector<int> result(n, -1); stack<int> st; // 存储下标，单调递减
for (int i = 0; i < n; i++) { while (!st.empty() && nums[st.top()] < nums[i]) { result[st.top()] = i; st.pop(); } st.push(i); } return result;}
// 最大矩形面积（经典题）int largestRectangleArea(vector<int>& heights) { stack<int> st; heights.push_back(0); int maxArea = 0;
for (int i = 0; i < heights.size(); i++) { while (!st.empty() && heights[st.top()] > heights[i]) { int h = heights[st.top()]; st.pop(); int w = st.empty() ? i : i - st.top() - 1; maxArea = max(maxArea, h * w); } st.push(i); } return maxArea;}4.2 单调队列
用于滑动窗口最值问题。
class MonotonicQueue {private: deque<int> dq; // 存储下标 vector<int>& arr;
public: MonotonicQueue(vector<int>& nums) : arr(nums) {}
void push(int idx) { while (!dq.empty() && arr[dq.back()] < arr[idx]) { dq.pop_back(); } dq.push_back(idx); }
void pop(int idx) { if (!dq.empty() && dq.front() == idx) { dq.pop_front(); } }
int getMax() { return arr[dq.front()]; }};
// 滑动窗口最大值vector<int> maxSlidingWindow(vector<int>& nums, int k) { MonotonicQueue mq(nums); vector<int> result;
for (int i = 0; i < nums.size(); i++) { mq.push(i); if (i >= k - 1) { result.push_back(mq.getMax()); mq.pop(i - k + 1); } } return result;}复杂度：O(n)，每个元素最多入队出队一次。
5. ST表（Sparse Table）
ST表用于解决RMQ（区间最值查询）问题，支持O(1)查询，但不支持修改。
5.1 实现
class SparseTable {private: vector<vector<int>> st; vector<int> lg; int n;
public: SparseTable(vector<int>& arr) { n = arr.size(); lg.resize(n + 1); lg[1] = 0; for (int i = 2; i <= n; i++) { lg[i] = lg[i / 2] + 1; }
int maxLog = lg[n] + 1; st.assign(n, vector<int>(maxLog));
// 初始化 for (int i = 0; i < n; i++) { st[i][0] = arr[i]; }
// 动态规划 for (int j = 1; j < maxLog; j++) { for (int i = 0; i + (1 << j) <= n; i++) { st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } } }
// 查询区间 [l, r] 最大值 int query(int l, int r) { int j = lg[r - l + 1]; return max(st[l][j], st[r - (1 << j) + 1][j]); }};复杂度分析：
- 预处理：O(n log n)
- 查询：O(1)
- 空间：O(n log n)
适用场景：静态RMQ、LCA（最近公共祖先）。
6. 主席树（可持久化线段树）
主席树可以查询历史版本的数据，是可持久化数据结构的代表。
6.1 静态区间第k小
struct Node { int lson, rson; int sum;};
class PersistentSegmentTree {private: vector<Node> tree; vector<int> roots; int cnt;
int build(int l, int r) { int root = cnt++; tree[root].sum = 0; if (l == r) return root;
int mid = (l + r) / 2; tree[root].lson = build(l, mid); tree[root].rson = build(mid + 1, r); return root; }
int update(int pre, int l, int r, int pos) { int root = cnt++; tree[root] = tree[pre]; tree[root].sum++;
if (l == r) return root;
int mid = (l + r) / 2; if (pos <= mid) { tree[root].lson = update(tree[pre].lson, l, mid, pos); } else { tree[root].rson = update(tree[pre].rson, mid + 1, r, pos); } return root; }
int query(int u, int v, int l, int r, int k) { if (l == r) return l;
int mid = (l + r) / 2; int leftSum = tree[tree[v].lson].sum - tree[tree[u].lson].sum;
if (k <= leftSum) { return query(tree[u].lson, tree[v].lson, l, mid, k); } else { return query(tree[u].rson, tree[v].rson, mid + 1, r, k - leftSum); } }
public: PersistentSegmentTree(int maxSize) { tree.resize(maxSize * 40); cnt = 0; }
void buildTree(vector<int>& arr, vector<int>& sorted) { int n = arr.size(); int m = sorted.size(); roots.resize(n + 1);
roots[0] = build(0, m - 1); for (int i = 0; i < n; i++) { int pos = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin(); roots[i + 1] = update(roots[i], 0, m - 1, pos); } }
int kthSmallest(int l, int r, int k, vector<int>& sorted) { int idx = query(roots[l - 1], roots[r], 0, sorted.size() - 1, k); return sorted[idx]; }};复杂度分析：
- 建树：O(n log n)
- 查询：O(log n)
- 空间：O(n log n)
7. 平衡树
7.1 Treap（树堆）
struct TreapNode { int val, priority; int size; TreapNode *left, *right;
TreapNode(int v) : val(v), priority(rand()), size(1), left(nullptr), right(nullptr) {}};
class Treap {private: TreapNode* root;
int getSize(TreapNode* node) { return node ? node->size : 0; }
void updateSize(TreapNode* node) { if (node) { node->size = getSize(node->left) + getSize(node->right) + 1; } }
TreapNode* rotateLeft(TreapNode* node) { TreapNode* right = node->right; node->right = right->left; right->left = node; updateSize(node); updateSize(right); return right; }
TreapNode* rotateRight(TreapNode* node) { TreapNode* left = node->left; node->left = left->right; left->right = node; updateSize(node); updateSize(left); return left; }
TreapNode* insert(TreapNode* node, int val) { if (!node) return new TreapNode(val);
if (val < node->val) { node->left = insert(node->left, val); if (node->left->priority > node->priority) { node = rotateRight(node); } } else { node->right = insert(node->right, val); if (node->right->priority > node->priority) { node = rotateLeft(node); } } updateSize(node); return node; }
int getRank(TreapNode* node, int val) { if (!node) return 0; if (val <= node->val) { return getRank(node->left, val); } else { return getSize(node->left) + 1 + getRank(node->right, val); } }
public: Treap() : root(nullptr) {}
void insert(int val) { root = insert(root, val); }
int rank(int val) { return getRank(root, val) + 1; }};复杂度：期望O(log n)，最坏O(n)。
8. 分块
分块是一种暴力优化思想，将数组分成√n块。
class BlockArray {private: vector<int> arr; vector<long long> blockSum; int n, blockSize, blockCount;
public: BlockArray(vector<int>& nums) { arr = nums; n = arr.size(); blockSize = sqrt(n) + 1; blockCount = (n + blockSize - 1) / blockSize; blockSum.resize(blockCount);
for (int i = 0; i < n; i++) { blockSum[i / blockSize] += arr[i]; } }
void update(int pos, int val) { blockSum[pos / blockSize] += val - arr[pos]; arr[pos] = val; }
long long query(int l, int r) { long long sum = 0; int blockL = l / blockSize; int blockR = r / blockSize;
if (blockL == blockR) { for (int i = l; i <= r; i++) { sum += arr[i]; } } else { for (int i = l; i < (blockL + 1) * blockSize; i++) { sum += arr[i]; } for (int i = blockL + 1; i < blockR; i++) { sum += blockSum[i]; } for (int i = blockR * blockSize; i <= r; i++) { sum += arr[i]; } } return sum; }};复杂度：修改O(1)，查询O(√n)。
9. 树链剖分
树链剖分将树分解为若干条链，结合线段树实现树上路径查询和修改。
class HeavyLightDecomposition {private: vector<vector<int>> adj; vector<int> parent, depth, heavy, head, pos; LazySegmentTree seg; int currentPos;
int dfs(int u) { int size = 1, maxSubtree = 0; for (int v : adj[u]) { if (v == parent[u]) continue; parent[v] = u; depth[v] = depth[u] + 1; int subtree = dfs(v); size += subtree; if (subtree > maxSubtree) { maxSubtree = subtree; heavy[u] = v; } } return size; }
void decompose(int u, int h) { head[u] = h; pos[u] = currentPos++; if (heavy[u] != -1) { decompose(heavy[u], h); } for (int v : adj[u]) { if (v != parent[u] && v != heavy[u]) { decompose(v, v); } } }
public: HeavyLightDecomposition(int n) : seg(n) { adj.resize(n); parent.resize(n); depth.resize(n); heavy.assign(n, -1); head.resize(n); pos.resize(n); currentPos = 0; }
void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); }
void build(int root = 0) { dfs(root); decompose(root, root); }
void updatePath(int u, int v, long long val) { while (head[u] != head[v]) { if (depth[head[u]] < depth[head[v]]) swap(u, v); seg.update(pos[head[u]], pos[u], val); u = parent[head[u]]; } if (depth[u] > depth[v]) swap(u, v); seg.update(pos[u], pos[v], val); }
long long queryPath(int u, int v) { long long res = 0; while (head[u] != head[v]) { if (depth[head[u]] < depth[head[v]]) swap(u, v); res += seg.query(pos[head[u]], pos[u]); u = parent[head[u]]; } if (depth[u] > depth[v]) swap(u, v); res += seg.query(pos[u], pos[v]); return res; }};复杂度：修改/查询O(log² n)。
10. Link-Cut Tree（LCT）
LCT是动态树结构，支持动态加边删边和路径查询。
struct LCTNode { LCTNode *ch[2], *fa; int val, sum; bool rev;
LCTNode(int v = 0) : val(v), sum(v), rev(false) { ch[0] = ch[1] = fa = nullptr; }
bool isRoot() { return !fa || (fa->ch[0] != this && fa->ch[1] != this); }
void pushDown() { if (rev) { swap(ch[0], ch[1]); if (ch[0]) ch[0]->rev ^= 1; if (ch[1]) ch[1]->rev ^= 1; rev = false; } }
void update() { sum = val; if (ch[0]) sum += ch[0]->sum; if (ch[1]) sum += ch[1]->sum; }};
class LinkCutTree {private: void rotate(LCTNode* x) { LCTNode* y = x->fa; LCTNode* z = y->fa; int k = y->ch[1] == x;
if (!y->isRoot()) z->ch[z->ch[1] == y] = x; x->fa = z;
y->ch[k] = x->ch[k ^ 1]; if (x->ch[k ^ 1]) x->ch[k ^ 1]->fa = y;
x->ch[k ^ 1] = y; y->fa = x;
y->update(); x->update(); }
void splay(LCTNode* x) { while (!x->isRoot()) { LCTNode* y = x->fa; if (!y->isRoot()) { (y->fa->ch[0] == y) ^ (y->ch[0] == x) ? rotate(x) : rotate(y); } rotate(x); } }
void access(LCTNode* x) { for (LCTNode* y = nullptr; x; y = x, x = x->fa) { splay(x); x->ch[1] = y; x->update(); } }
void makeRoot(LCTNode* x) { access(x); splay(x); x->rev ^= 1; }
public: void link(LCTNode* x, LCTNode* y) { makeRoot(x); x->fa = y; }
void cut(LCTNode* x, LCTNode* y) { makeRoot(x); access(y); splay(y); y->ch[0]->fa = nullptr; y->ch[0] = nullptr; y->update(); }
int query(LCTNode* x, LCTNode* y) { makeRoot(x); access(y); splay(y); return y->sum; }};复杂度：均摊O(log n)。
11. 经典竞赛应用
11.1 线段树应用
例题1：区间修改区间求和
- 洛谷 P3372
- 使用懒惰标记的线段树
例题2：区间最大子段和
- 维护区间最大值、最大前缀、最大后缀、总和
11.2 树状数组应用
例题：逆序对
long long countInversions(vector<int>& arr) { vector<int> sorted = arr; sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
BIT bit(sorted.size()); long long inversions = 0;
for (int i = arr.size() - 1; i >= 0; i--) { int pos = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin() + 1; inversions += bit.query(pos - 1); bit.update(pos, 1); } return inversions;}11.3 主席树应用
例题：区间第k小
- POJ 2104
- 使用可持久化线段树
11.4 树链剖分应用
例题：树上路径和
- 支持修改节点权值
- 查询路径和
12. 总结与进阶
12.1 数据结构选择指南
| 问题类型 | 推荐数据结构 | 复杂度 |
|---|---|---|
| 区间和查询，单点修改 | 树状数组 | O(log n) |
| 区间和查询，区间修改 | 线段树（懒标记） | O(log n) |
| 静态区间最值 | ST表 | O(1) |
| 动态区间最值 | 线段树 | O(log n) |
| 区间第k小 | 主席树 | O(log n) |
| 动态维护有序集合 | 平衡树 | O(log n) |
| 树上路径操作 | 树链剖分/LCT | O(log² n) / O(log n) |
| 连通性维护 | 并查集 | O(α(n)) |
12.2 学习路径建议
CSP-S级别：
- 树状数组基础
- 线段树基础
- 并查集
- 单调栈/队列
- ST表
省选/NOI级别：
- 线段树进阶（懒标记、动态开点）
- 主席树
- 树链剖分
- 基础平衡树
IOI/WC级别：
- LCT
- 可持久化数据结构
- 高级平衡树（Splay）
- 分块进阶
12.3 练习建议
- 基础巩固：Codeforces Div2 C/D, 洛谷普及+/提高
- 专项训练：按数据结构类型刷专题
- 综合应用：NOI/IOI真题
- 码量训练：手写常用模板至少5遍
掌握这些高级数据结构，是在算法竞赛中取得好成绩的关键。建议从基础开始，逐步进阶，多做题多总结，形成自己的代码模板库。
推荐资源：
- 《算法竞赛进阶指南》
- OI Wiki
- Codeforces
- 洛谷题库
- USACO Guide
高级数据结构详解：从CSP-S到IOI
https://myblog-590.pages.dev/posts/algorithm-data-structures/