线段树

1. 定义

线段树是一种基于分治思想的二叉树结构，常用于统计区间内的信息。

特征:

1. 线段树的每个节点都代表一个闭区间
2. 线段树具有唯一的根节点，代表的区间是整个统计范围
3. 线段树的每个叶节点都代表一个长度为1的元区间
4. 对于每个内部节点[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;
}