c
casperwu
V1
2022/07/18阅读:9主题:橙心
线段树
1. 定义
线段树是一种基于分治思想的二叉树结构,常用于统计区间内的信息。
特征:
-
线段树的每个节点都代表一个闭区间 -
线段树具有唯一的根节点,代表的区间是整个统计范围 -
线段树的每个叶节点都代表一个长度为1的元区间 -
对于每个内部节点[l, r], 它的左子节点是[l, mid], 右子节点是[mid+1, r], 其中mid = (l + r) / 2 向下取整

2. 线段树的存储
由于线段树是一棵二叉树,根据定义可以得到除了最后一层的结点外,它是一棵满二叉树,因此可以使用数组来存储线段树。
假设原始数组的长度是N,使用线段树存储时需要开4N长度。
证明: 由于倒数第二层的结点数 < N,就取上限为N,则从倒数第二层到根节点最多有2N - 1个结点,最后一层的结点数 < 2N,因此总共的节点数不会超过4N。
3. 模板题目

3.1 思路
根据题意,每次输入的数据是动态的,但是在建立树状数组时需要提前知道数据的长度。因此可以先预先假设需要建立的树状数组的长度是 m 个, 每次添加一个新的数据时,可以看做是在相应的位置上将该值修改为添加的值。即先占坑,在需要时修改该值即可。
3.2 模板代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
struct Node {
int l, r;
int dat; // 存储区间[l, r] 之间的最大值
} tr[N * 4]; // 线段树需要开4倍空间
int m, p;
// 用于从子节点更新父节点的数据, 根据具体的需求实现会不一样
// 本题是设置最大值
void pushup(int p) {
tr[p].dat = max(tr[p << 1].dat, tr[p << 1 | 1].dat);
}
// 由于本题中最开始初始化的线段树是用来占位的, 没有值
void build(int p, int l, int r) {
tr[p].l = l, tr[p].r = r;
if(l == r) {
// 用于占位, 没有值, 因此可以不赋值
return;
}
int mid = l + r >> 1;
// p << 1 等价于 p * 2, p << 1 | 1 等价于 P * 2 + 1
build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
// 也不需要pushup赋值操作
}
void update(int p, int x, int v) {
if(tr[p].l == tr[p].r) { // 递归边界, 递归到了叶子节点
tr[p].dat = v;
return;
}
int mid = tr[p].l + tr[p].r >> 1;
if(x <= mid) update(p << 1, x, v); // 递归左侧
else update(p << 1 | 1, x, v); // 递归右侧
pushup(p); // 更新当前节点的值
}
int query(int p, int left, int right) {
// 树上的区间完全包含在目标区间中, 直接返回
if(left <= tr[p].l && tr[p].r <= right) return tr[p].dat;
int ans = 0; // 由于输入的值一定是大于0的, 因此可以用0来表示最小值
int mid = tr[p].l + tr[p].r >> 1;
if(left <= mid) ans = max(ans, query(p << 1, left, right));
if(right > mid) ans = max(ans, query(p << 1 | 1, left, right));
return ans;
}
int main() {
cin >> m >> p;
// 构建线段树
build(1, 1, m);
int n = 0, last = 0; // n 用于记录当前输入的数据个数, last 记录上次查询的结果
string type; int x;
while(m--) {
cin >> type >> x;
if(type == "Q") { // 查询操作
last = query(1, n - x + 1, n);
cout << last << endl;
} else {
n++; // 输入的数的个数 +1
update(1, n, ((LL)x + last) % p);
}
}
return 0;
}
作者介绍
c
casperwu
V1