线段树入门：[JSOI2008] 最大数
题目描述
现在请求你维护一个数列，要求提供以下两种操作：
1. 查询操作
- 语法：
Q L - 功能：查询当前数列中末尾 L 个数中的最大的数，并输出这个数的值。
- 限制：L 不超过当前数列的长度（L > 0）
2. 插入操作
- 语法：
A n - 功能：将 n 加上 t，其中 t 是最近一次查询操作的答案（如果还未执行过查询操作，则 t = 0），并将所得结果对一个固定的常数 D 取模，将所得答案插入到数列的末尾。
- 限制：n 是整数（可能为负数）并且在长整范围内。
注意事项
- 初始时数列是空的，没有一个数。
基本概念：什么是线段树？
线段树简介
线段树（Segment Tree） 是一种二叉树结构，每个节点代表一个区间，用于高效地维护和查询区间信息。它是一种区间查询与修改的经典数据结构。
核心特点
- 完全二叉树：线段树是一棵完全二叉树
- 区间表示：每个节点存储一个区间的信息
- 高效操作：
- 单点修改：O(log n)
- 区间查询：O(log n)
- 区间修改：O(log n)
- 空间复杂度：O(n)
线段树的构建
区间 [1, 8]
├── [1, 4]
│ ├── [1, 2]
│ │ ├── [1, 1]
│ │ └── [2, 2]
│ └── [3, 4]
│ ├── [3, 3]
│ └── [4, 4]
└── [5, 8]
├── [5, 6]
│ ├── [5, 5]
│ └── [6, 6]
└── [7, 8]
├── [7, 7]
└── [8, 8]解题思路
题目分析
要求维护一个初始为空的数列，支持两种操作：
- 查询操作 Q L：查询当前数列中最后 L 个数的最大值
- 插入操作 A n：将 (n + t) % d 插入到数列末尾，其中 t 是上一次查询的结果（初始为 0），d 是给定的模数
关键问题
由于操作次数 M 最多为 200,000，每次查询如果遍历最后 L 个数会超时（O(M)）。
解决方案
使用线段树实现 O(log M) 时间的区间最大值查询和单点修改。
核心实现
1. 数据结构设计
struct Node {
int l, r; // 区间的左右边界
int v; // 该区间的最大值
} tr[N * 4]; // 线段树需要开 4 倍空间2. 初始化
void build(int u, int l, int r) {
tr[u].l = l, tr[u].r = r;
if (l == r) {
tr[u].v = INT_MIN; // 初始化为一个非常小的数
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid); // 递归构建左子树
build(u << 1 | 1, mid + 1, r); // 递归构建右子树
}重要细节：将所有节点初始化为 INT_MIN，因为查询的区间可能包含尚未插入数的位置，如果不初始化为极小值，这些位置的默认值 0 可能会影响负数情况下的查询结果。
3. 单点修改
void update(int u, int x, int v) {
if (tr[u].l == x && tr[u].r == x) { // 如果当前节点是叶子节点
tr[u].v = v; // 直接修改
return;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid)
update(u << 1, x, v); // 目标在左子树
else
update(u << 1 | 1, x, v); // 目标在右子树
pushup(u); // 子节点更新父节点的最大值
}4. 区间查询
int query(int u, int l, int r) {
// 如果当前区间完全包含在查询区间内，直接返回该节点的最大值
if (l <= tr[u].l && tr[u].r <= r)
return tr[u].v;
int mid = (tr[u].l + tr[u].r) >> 1;
int res = INT_MIN; // 有可能是负数
if (l <= mid)
res = max(res, query(u << 1, l, r)); // 左子树与查询区间有重叠
if (r > mid)
res = max(res, query(u << 1 | 1, l, r)); // 右子树与查询区间有重叠
return res;
}5. 向上更新
void pushup(int u) {
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v); // 左右子节点的最大值更新父节点
}完整代码实现
结构体版
#include <iostream>
#include <cstdio>
#include <climits>
using namespace std;
typedef long long LL; // x + a 可能是 LL
const int N = 2e5 + 10; // 最多操作次数也是线段树的最大长度
struct Node { // 线段树节点结构体
int l, r; // 节点所代表的区间 [l, r]
int v; // 该区间的最大值
} tr[N * 4]; // 线段树需要开 4 倍空间
int M; // 操作次数 M
int D; // 模数 D
void pushup(int u) { // 向上更新
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v); // 左右子节点的最大值更新父节点
}
void build(int u, int l, int r) { // 预先构建覆盖[1, M]的线段树
tr[u].l = l, tr[u].r = r;
if (l == r) {
tr[u].v = INT_MIN; // 初始化为一个非常小的数
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid); // 递归构建左子树
build(u << 1 | 1, mid + 1, r); // 递归构建右子树
}
// 单点修改：将位置 x 的值修改为 v
void update(int u, int x, int v) {
if (tr[u].l == x && tr[u].r == x) { // 如果当前节点是叶子节点
tr[u].v = v; // 直接修改
return;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid)
update(u << 1, x, v); // 目标在左子树
else
update(u << 1 | 1, x, v); // 目标在右子树
pushup(u); // 子节点更新父节点的最大值
}
// 区间查询：查询区间 [l, r] 的最大值
int query(int u, int l, int r) {
// 如果当前区间完全包含在查询区间内，直接返回该节点的最大值
if (l <= tr[u].l && tr[u].r <= r)
return tr[u].v;
int mid = (tr[u].l + tr[u].r) >> 1;
int res = INT_MIN; // 有可能是负数
if (l <= mid)
res = max(res, query(u << 1, l, r)); // 左子树与查询区间有重叠
if (r > mid)
res = max(res, query(u << 1 | 1, l, r)); // 右子树与查询区间有重叠
return res;
}
int main() {
scanf("%d%d", &M, &D);
int n = 0; // 当前数列的实际长度
int a = 0; // 上一次查询的结果 初始 0
build(1, 1, M); // 构建一棵大小为 M 的线段树(最多有 M 个数)
while (M--) { // M 次处理
char op[2]; // 操作类型
scanf("%s", op);
if (op[0] == 'A') { // 插入操作
LL x; // x 是整数（可能为负数）并且在长整范围内
scanf("%lld", &x);
++n; // 更新数列长度
int v = (x + a) % D; // 计算要更新的值
update(1, n, v); // 在位置 n 更新为 v
} else { // 查询操作
int L; // 末尾 L 个数
scanf("%d", &L);
a = query(1, n - L + 1, n); // 查询末尾 L 个数中的最大的数：[n - L + 1, n]
printf("%d\n", a);
}
}
return 0;
}非结构体版
#include <iostream>
#include <cstdio>
#include <climits>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int tr[N * 4]; // 线段树数组
// 单点更新：将 p 位置的值更新为 v
void update(int u, int l, int r, int p, int v) {
if (l == r) {
tr[u] = v; // 直接修改
return;
}
int mid = (l + r) >> 1;
if (p <= mid)
update(u << 1, l, mid, p, v); // 目标在左子树
else
update(u << 1 | 1, mid + 1, r, p, v); // 目标在右子树
tr[u] = max(tr[u << 1], tr[u << 1 | 1]); // 子节点更新父节点的最大值
}
// 区间查询 [L, R] 的最大值
int query(int u, int l, int r, int L, int R) {
if (L <= l && r <= R)
return tr[u];
int mid = (l + r) >> 1;
int v = INT_MIN; // 有可能是负数
if (L <= mid)
v = max(v, query(u << 1, l, mid, L, R)); // 左子树与查询区间有重叠
if (R > mid)
v = max(v, query(u << 1 | 1, mid + 1, r, L, R)); // 右子树与查询区间有重叠
return v;
}
int main() {
int m, d;
scanf("%d%d", &m, &d);
fill(tr, tr + N * 4, INT_MIN); // 初始化线段树所有节点为极小值
int a = 0; // 上一次查询的结果
int n = 0; // 当前数列长度
for (int i = 0; i < m; i++) { // 不能用 while(m--) m 不能变化
char op[2];
scanf("%s", op);
if (op[0] == 'A') { // 添加操作
LL x;
scanf("%lld", &x);
n++;
int v = (x + a) % d; // 需要取模
update(1, 1, m, n, v); // 最多有 m 个位置
} else { // 查询操作
int L; // 查询末尾 L 个数的最大值
scanf("%d", &L);
a = query(1, 1, m, n - L + 1, n);
printf("%d\n", a);
}
}
return 0;
}复杂度分析
时间复杂度
- 建树：O(M)
- 单点修改：O(log M)
- 区间查询：O(log M)
- 总复杂度：O(M log M)
空间复杂度
- 线段树空间：O(M)
- 总空间：O(M)
关键点总结
- 数组存储：使用数组存储树结构（非结构体）
- 动态插入：每次插入时，n 增加 1，调用单点更新
- 区间查询：查询区间 [n – L + 1, n] 的最大值
- 取模运算：插入的值是 (x + a) % d，其中 x 是输入的数
- 初始化：线段树一开始全部设成极小值，这样没插入的位置不会影响查询