栈与队列

• 单调栈：维护单调递增 / 递减下标，求「下一个更大元素」、柱状图最大矩形
• 单调队列：双端队列维护窗口最值，滑动窗口、DP 单调队列优化（转移窗口有滑动界时）

堆（优先队列）

priority_queue 动态维护最值：Dijkstra、哈夫曼合并、多路归并、对顶堆维护中位数。

priority_queue<int> max_heap;
priority_queue<int, vector<int>, greater<int>> min_heap;

树状数组（Fenwick）

支持单点修改 + 前缀和（或前缀最值等可逆运算），$O(\log n)$。

void add(int i, int v) { for (; i <= n; i += i & -i) bit[i] += v; }
int sum(int i) { int s = 0; for (; i; i -= i & -i) s += bit[i]; return s; }
// 区间 [l,r] 和：sum(r) - sum(l-1)

二维树状数组：矩阵单点改 + 子矩形和。

线段树

区间修改 / 查询（和、最值、gcd、按位或等），建树 $O(n)$，单次 $O(\log n)$。

• 懒标记：区间加、区间赋值时，延迟下传标记到子节点
• 动态开点：值域很大、使用点少时，指针式建树
• 权值线段树 / 主席树：可持久化，求区间第 $k$ 小

典型递归：build、pushup、pushdown、query(l,r)、update(l,r,val)。

ST 表

静态区间最值（或 gcd 等满足重叠性质的操作），查询 $O(1)$，预处理 $O(n \log n)$，不支持修改。

st[i][j] 表示从 $i$ 开始长度为 $2^j$ 的区间最值，合并：st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1])。

稀疏表 + 倍增

LCA：欧拉序 + dep[]，fa[i][k] 表示节点 $i$ 向上 $2^k$ 步的祖先，查询 $O(\log n)$。

字典树 Trie

每个节点存 26（或 2）个子指针，用于字符串集合、前缀统计、01-Trie 求最大异或和。

并查集 / 哈希表

并查集见「图论」；unordered_map 离散映射、计数时注意常数与 rehash。

选择建议

例题

例 1：柱状图中最大的矩形（单调栈）
给定各柱高度 $h_i$，求最大矩形面积。维护单调递增栈存下标，当前柱比栈顶矮时弹出，以弹出柱为高、宽度为「当前 $i$ 到栈顶下一位」计算面积并更新答案。每个下标入栈出栈各一次，$O(n)$。

例 2：区间修改区间求和（线段树 + 懒标记）
支持：区间 $[l,r]$ 加 $v$；查询区间 $[l,r]$ 和。线段树节点存区间和与「待下传加法标记」，pushdown 时把标记传给子节点。单次操作 $O(\log n)$。