线段树

线段树

标题：https://www.acwing.com/problem/content/1277/

1. /*
2.     题目：https://www.acwing.com/problem/content/1277/
3.     给定一个正整数数列 a1,a2,…,an，每一个数都在 0∼p−1 之间。
4.     可以对这列数进行两种操作：
5.     添加操作：向序列后添加一个数，序列长度变成 n+1；
6.     询问操作：询问这个序列中最后 L 个数中最大的数是多少。
7. */
8. #include <bits/stdc++.h>
9. #define lc u << 1
10. #define rc u << 1 | 1
11. using u32 = unsigned;
12. using i64 = long long;
13. using u64 = unsigned long long;
14. const int N = 2e5+10;
15. int m;
16. i64 p;
17. int n;
18. int last;
19. struct node {
20.     int l, r;
21.     int v; // 如果是叶子节点，存储他的值；否则存储左右儿子的最大值
22. }tr[4*N];
23. void build(int u, int l, int r) {
24.     tr[u] = {l, r}; // 为当前节点定义左右边界，但是不加入值，因为值是在线加入的
25.     if (l == r) return; // 如果当前节点是叶子节点，那么我们就直接返回
26.     int mid = l + r >> 1; // 裂开
27.     build(lc, l, mid), build(rc, mid + 1, r);
28. }
29. void pushup(int u) {
30.     // pushup是根据左右子节点的值传递给父节点，这道题是求左右子节点的最大值
31.     tr[u].v = std::max(tr[lc].v, tr[rc].v);
32. }
33. int query(int u, int l, int r) {
34.     if (l <= tr[u].l && tr[u].r <= r) return tr[u].v; // 如果当前区间完全包含在要查询的区间中，直接返回
35.     // 否则，裂开
36.     int mid = tr[u].l + tr[u].r >> 1;
37.     int v = 0; // 存储当前节点的值
38.     if (l <= mid) v = std::max(v, query(lc, l, r)); // 如果[l, r]与u的左子树有交集，就去找左子树中的最大值，并且更新返回值
39.     if (r >= mid + 1) v = std::max(v, query(rc, l, r)); // 如果[l, r]与u的右子树有交集，就去找右子树中的最大值，并且更新返回值
40.     return v;
41. }
42. void modify(int u, int x, int v) {
43.     // 判断当前节点是不是叶子节点，如果是叶子节点，那么我们就直接更新
44.     // 需要注意的是，如果这个节点是叶子节点，那么它的值一定是x，因为我们一直是根据x作为线索来进行搜索的，所以搜索到的叶子节点一定是x
45.     // if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
46.     if (tr[u].l == tr[u].r) tr[u].v = v;// 如果当前节点是叶子节点并且值为x，那么此节点就是待更新的节点，更新v的值
47.     else {
48.         // 否则，这个节点就只可能是非叶子节点，继续裂开
49.         int mid = tr[u].l + tr[u].r >> 1;
50.         if (x <= mid) {
51.             // 要修改的节点在左子树
52.             modify(lc, x, v);
53.         } else {
54.             // 要修改的节点在右子树
55.             modify(rc, x, v);
56.         }
57.         pushup(u); // 修改完成之后，再次把左右节点的较大值更新到父节点
58.     }
59. }
60. void solve() {
61.     std::cin >> m >> p;
62.     build(1, 1, m); // 建树
63.     char op[2];
64.     while (m --) {
65.         scanf("%s", op);
66.         if (*op == 'Q') {
67.             int l;
68.             std::cin >> l;
69.             last = query(1, n - l + 1, n);
70.             std::cout << last << "\n";
71.         } else {
72.             int x;
73.             std::cin >> x;
74.             modify(1, n + 1, ((i64)x + last) % p);
75.             n ++;
76.         }
77.     }
78. }
79. int main()
80. {
81.     int t = 1;
82.     while (t --) {
83.         solve();
84.     }
85.     return 0;
86. }

复制代码

接下来对线段树的几个操作进行详解：
1、build创建操作

1. void build(int u, int l, int r) {
2.     tr[u] = {l, r}; // 为当前节点定义左右边界，但是不加入值，因为值是在线加入的
3.     if (l == r) return; // 如果当前节点是叶子节点，那么我们就直接返回
4.     int mid = l + r >> 1; // 裂开
5.     build(lc, l, mid), build(rc, mid + 1, r);
6. }

复制代码

起首，我们从节点1开始，为区间的每个节点赋值。
当我们遍历到节点k，当前节点有两种情况：
1、当前节点的l == r，那么当前节点就是叶子节点，我们对其赋相应的值之后，就直接返回，否则会陷入死循环
2、否则，当前节点就是非叶子节点，由于我们要找到叶子节点才能结束，所以我们对当前节点继续分裂，对左右子节点进行递归创建操作

2、pushup操作

1. void pushup(int u) {
2.     // pushup是根据左右子节点的值传递给父节点，这道题是求左右子节点的最大值
3.     tr[u].v = std::max(tr[lc].v, tr[rc].v);
4. }

复制代码

pushup操作一般用于我们修改了u的子节点的值之后，对u进行Pushup操作，就可以在非常短的时间内对所有必要做出修改的节点的值进行修改

3、query查询操作

1. int query(int u, int l, int r) {
2.     if (l <= tr[u].l && tr[u].r <= r) return tr[u].v; // 如果当前区间完全包含在要查询的区间中，直接返回
3.     // 否则，裂开
4.     int mid = tr[u].l + tr[u].r >> 1;
5.     int v = 0; // 存储当前节点的值
6.     if (l <= mid) v = std::max(v, query(lc, l, r)); // 如果[l, r]与u的左子树有交集，就去找左子树中的最大值，并且更新返回值
7.     if (r >= mid + 1) v = std::max(v, query(rc, l, r)); // 如果[l, r]与u的右子树有交集，就去找右子树中的最大值，并且更新返回值
8.     return v;
9. }

复制代码

query查询操作，求出[l, r]的最大值
此处有两种情况：
1、当前节点的左右范围完全包含在必要查询的区间中，那么我们就没必要再继续往下递归，直接返回当前节点的值就行了
2、否则，当前节点的范围没有完全包含到必要查询的区间中，再次对当前节点进行分裂 =>如果[]l, r]与左子树有交集，那么我们就在左子树的[l, mid]范围内求出一个max1；如果[l, r]与右子树有交集，我们在[mid+1, r]范围内求出一个max2，于是当前节点包含在[l, r]中那部分的最大值就是max(max1, max2)，然后返回

4、modify修改操作
[code]void modify(int u, int x, int v) {    // 判断当前节点是不是叶子节点，如果是叶子节点，那么我们就直接更新    // 必要注意的是，如果这个节点是叶子节点，那么它的值一定是x，因为我们一直是根据x作为线索来进行搜刮的，所以搜刮到的叶子节点一定是x    // if (tr.l == x && tr.r == x) tr.v = v;    if (tr.l == tr.r) tr.v = v;// 如果当前节点是叶子节点并且值为x，那么此节点就是待更新的节点，更新v的值    else {        // 否则，这个节点就只大概是非叶子节点，继续裂开        int mid = tr.l + tr.r >> 1;        if (x