Appearance
问题
数组
- 单点修改:将
修改为 ; - 区间查询:查询
的最小值; - 区间修改:将
每个数加上 。
cpp
int a[];
// 单点修改
void set(int id, int v) {
a[id] = v;
}
// 区间查询
int ask(int l, int r) {
int ans = 0;
for (int i = l; i <= r; i ++)
ans = min(ans, a[i]);
return ans;
}
// 区间修改
void add(int l, int r, int v) {
for (int i = l; i <= r; i ++)
a[i] += v;
}
暴力算法( | 线段树( | |
---|---|---|
单点修改 | ||
区间查询 | ||
区间修改 | ||
构造
查询数组
graph TD A((6)) B((2)) C((3)) D((7)) E((1)) F((5)) G((4)) H((2))
I((2)) --> A I --> B
J((3)) --> C J --> D
K((1)) --> E K --> F
L((2)) --> G L --> H
M((2)) --> I M --> J
N((1)) --> K N --> L
O((1)) --> M O --> N
这么做有什么好处呢?假如
graph TD A((6)) B((2)) C((3)) D((7)) E((7)) F((5)) G((4)) H((2))
I((2)) --> A I --> B
J((3)) --> C J --> D
K((5)) --> E K --> F
L((2)) --> G L --> H
M((2)) --> I M --> J
N((2)) --> K N --> L
O((2)) --> M O --> N
classDef red fill:#fff3c2, stroke:#e57d21;
class E,K,N,O red;
线段树就是这样的一颗二叉树,它的每个节点都代表一段区间中的最小值。
线段树具有以下性质:
- 根节点的值为
,代表整个数组的最小值; 的左子节点为 ,右子节点为 ; 。
因此,每个节点需要保存以下信息:
- 节点的值:
; - 节点代表的区间:
。
从根节点开始,自顶向下递归构建线段树。时间复杂度为
cpp
struct Node {
int val, l, r;
#define t(u) t[u].val
#define l(u) t[u].l
#define r(u) t[u].r
} t[];
void build(int u, int l, int r) {
l(u) = l, r(u) = r;
if (l == r) { // 当前节点为叶节点
t(u) = a[l]; return;
}
int m = (l + r) / 2;
build(2 * u, l, m); // 递归构建左子树
build(2 * u + 1, m + 1, r); // 递归构建右子树
t(u) = min(t(2 * u), t(2 * u + 1));
}
单点修改
假设你要将
- 令
; - 若
,则 在左子树中,搜索左子树; - 若
,则 在右子树中,搜索右子树; - 更新当前节点值:
。
时间复杂度为
根节点是搜索的入口。执行
cpp
void set(int u, int id, int v) { // 将 a[id] 改为 v
if (l(u) == r(u)) { // 叶节点
a[id] = t(u) = v; return;
}
int m = (l(u) + r(u)) / 2;
if (id <= m) set(2 * u, id, v); // 搜索左子树
else set(2 * u + 1, id, v); // 搜索右子树
t(u) = min(t(2 * u), t(2 * u + 1));
}
区间查询
线段树中,每个节点代表一个区间,每个区间都可通过若干节点实现完全覆盖。
例如
从根节点开始,自顶向下搜索出范围在
- 若
的范围在 之内,直接返回 ; - 若
的范围与 不重叠,返回 [1]; - 否则递归搜索
的两个子节点。
时间复杂度为
执行
cpp
int get(int u, int l, int r) {
if (l <= l(u) && r(u) <= r) return t(u); // 1. 被包含
if (l(u) > r || r(u) < l) return 0x3f3f3f; // 2. 不重叠
return min(get(2 * u, l, r), get(2 * u + 1, l, r)); // 3. 递归搜索
}
区间修改 + 延迟标记
如果一次性将
事实上,大部分节点用不着马上更新——直到它们再次被访问。于是我们可以先给部分节点打标记。
在本例中,
当访问
代码与 区间查询 类似。时间复杂度为
cpp
int mark[];
// 更新 u 的子节点,并下传标记
void spread(int u) {
if (mark[u]) {
t(2 * u) += mark[u];
t(2 * u + 1) += mark[u];
mark[2 * u] += mark[u];
mark[2 * u + 1] += mark[u];
mark[u] = 0;
}
}
// 将 A[l] ... A[r] 加上 v
void add(int u, int l, int r, int v) {
if (l <= l(u) && r(u) <= r) { // 完全覆盖
t(u) += v, mark[u] += v; return; // 标记
}
else if (l(u) > r || r(u) < l) return;
spread(u); // 下传标记
int m = (l + r) / 2;
add(2 * u, l, r, v);
add(2 * u + 1, l, r, v);
t(u) = min(t(2 * u), t(2 * u + 1));
}
cpp
void set(int u, int id, int v) {
if (l(u) == r(u)) {
a[id] = t(u) = v; return;
}
spread(u); // 下传标记
int m = (l(u) + r(u)) / 2;
if (id <= m) set(2 * u, id, v);
else set(2 * u + 1, id, v);
t(u) = min(t(2 * u), t(2 * u + 1));
}
int get(int u, int l, int r) {
if (l <= l(u) && r(u) <= r) return t(u);
else if (l(u) > r || r(u) < l) return 0x3f3f3f;
spread(u); // 下传标记
int m = (l + r) / 2;
return min(get(2 * u, l, m), get(2 * u + 1, m + 1, r));
}
模板
cpp
struct Node {
int val, l, r;
#define t(u) t[u].val
#define l(u) t[u].l
#define r(u) t[u].r
} t[];
int mark[];
void build(int u, int l, int r) {
l(u) = l, r(u) = r;
if (l == r) {
t(u) = a[l]; return;
}
int m = (l + r) / 2;
build(2 * u, l, m);
build(2 * u + 1, m + 1, r);
t(u) = min(t(2 * u), t(2 * u + 1));
}
void spread(int u) {
if (mark[u]) {
t(2 * u) += mark[u];
t(2 * u + 1) += mark[u];
mark[2 * u] += mark[u];
mark[2 * u + 1] += mark[u];
mark[u] = 0;
}
}
void set(int u, int id, int v) {
if (l(u) == r(u)) {
a[id] = t(u) = v; return;
}
spread(u);
int m = (l(u) + r(u)) / 2;
if (id <= m) set(2 * u, id, v);
else set (2 * u + 1, id, v);
t(u) = min(t(2 * u), t(2 * u + 1));
}
int get(int u, int l, int r) {
if (l <= l(u) && r(u) <= r) return t(u);
else if (l(u) > r || r(u) < l) return 0x3f3f3f;
spread(u);
int m = (l + r) / 2;
return min(get(2 * u, l, m), get(2 * u + 1, m + 1, r));
}
void add(int u, int l, int r, int v) {
if (l <= l(u) && r(u) <= r) {
t(u) += v, mark[u] += v; return;
}
else if (l(u) > r || r(u) < l) return;
spread(u);
int m = (l + r) / 2;
add(2 * u, l, r, v);
add(2 * u + 1, l, r, v);
t(u) = min(t(2 * u), t(2 * u + 1));
}
区间和线段树
线段树还可以查询区间和。
令每个节点代表一段区间的元素和,递推方程应为
若
cpp
void spread(int u) {
if (mark[u]) {
t(2 * u) += mark[u] * (l(2 * u) - r(2 * u) + 1);
t(2 * u + 1) += mark[u] * (l(2 * u + 1) - r(2 * u + 1) + 1);
mark[2 * u] += mark[u];
mark[2 * u + 1] += mark[u];
mark[u] = 0;
}
}
,因此返回 相当于不参与最小值的比较。 ↩︎