线段树

线段树 Segment tree 是一种二叉树形数据结构，1977年由 Jon Louis Bentley发明，用以存储区间或线段，并且允许快速查询结构内包含某一点的所有区间。

🌳 SegmentTree

先贴一段洛谷P3373的线段树模板：

题目描述
如题，已知一个数列，你需要进行下面三种操作：

将某区间每一个数乘上 xx

将某区间每一个数加上 xx

求出某区间每一个数的和

输入格式
第一行包含三个整数 n,m,p，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含若干个整数，表示一个操作，具体如下：

操作 1： 格式：1 x y k 含义：将区间 [x,y] 内每个数乘上 k

操作 2： 格式：2 x y k 含义：将区间 [x,y] 内每个数加上 k

操作 3： 格式：3 x y 含义：输出区间 [x,y] 内每个数的和对 p 取模所得的结果

#include<bits/stdc++.h>

//#define LOCAL
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'

#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int long long

const int inf = 0x3f3f3f3f;
const int MAXN = 1e5 + 5;
int n, A[MAXN];
int mod;
struct node {
    int l, r, add, mul, sum;
} s[MAXN * 4];

void push_up(int pos) {
    s[pos].sum = (s[pos * 2].sum + s[pos * 2 + 1].sum) % mod;
}

void push_down(int pos) {
    s[pos * 2].sum = (s[pos * 2].sum * s[pos].mul + s[pos].add * (s[pos * 2].r - s[pos * 2].l + 1)) % mod;
    s[pos * 2 + 1].sum =
            (s[pos * 2 + 1].sum * s[pos].mul + s[pos].add * (s[pos * 2 + 1].r - s[pos * 2 + 1].l + 1)) % mod;

    s[pos * 2].mul = (s[pos * 2].mul * s[pos].mul) % mod;
    s[pos * 2 + 1].mul = (s[pos * 2 + 1].mul * s[pos].mul) % mod;

    s[pos * 2].add = (s[pos * 2].add * s[pos].mul + s[pos].add) % mod;
    s[pos * 2 + 1].add = (s[pos * 2 + 1].add * s[pos].mul + s[pos].add) % mod;

    s[pos].add = 0;
    s[pos].mul = 1;
}

void build_tree(int pos, int l, int r) {
    s[pos].l = l;
    s[pos].r = r;
    s[pos].mul = 1;
    s[pos].add = 0;

    if (l == r) {
        s[pos].sum = A[l] % mod;
        return;
    }

    int mid = (l + r) / 2;
    build_tree(pos * 2, l, mid);
    build_tree(pos * 2 + 1, mid + 1, r);
    push_up(pos);
}

void mul(int pos, int x, int y, int k) { //区间乘法
    if (x <= s[pos].l && s[pos].r <= y) {
        s[pos].add = (s[pos].add * k) % mod;
        s[pos].mul = (s[pos].mul * k) % mod;
        s[pos].sum = (s[pos].sum * k) % mod;
        return;
    }

    push_down(pos);
    int mid = (s[pos].l + s[pos].r) / 2;
    if (x <= mid) mul(pos * 2, x, y, k);
    if (y > mid) mul(pos * 2 + 1, x, y, k);
    push_up(pos);
}

void add(int pos, int x, int y, int k) {
    if (x <= s[pos].l && s[pos].r <= y) {
        s[pos].add = (s[pos].add + k) % mod;
        s[pos].sum = (s[pos].sum + k * (s[pos].r - s[pos].l + 1)) % mod;
        return;
    }

    push_down(pos);
    int mid = (s[pos].l + s[pos].r) / 2;
    if (x <= mid) add(pos * 2, x, y, k);
    if (y > mid) add(pos * 2 + 1, x, y, k);
    push_up(pos);
}

int query(int pos, int x, int y) { //区间询问
    if (x <= s[pos].l && s[pos].r <= y) {
        return s[pos].sum;
    }

    push_down(pos);
    int val = 0;
    int mid = (s[pos].l + s[pos].r) / 2;
    if (x <= mid) val = (val + query(pos * 2, x, y)) % mod;
    if (y > mid) val = (val + query(pos * 2 + 1, x, y)) % mod;
    return val;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    int m, t, x, y, k;
    cin >> n >> m >> mod;
    for (int i = 1; i <= n; ++i) {
        cin >> A[i];
    }
    build_tree(1, 1, n);
    while (m--) {
        cin >> t >> x >> y;
        if (t == 1) {
            cin >> k;
            mul(1, x, y, k);
        } else if (t == 2) {
            cin >> k;
            add(1, x, y, k);
        } else {
            print(query(1, x, y));
        }
    }
}

比较核心的操作有两个：push_up负责将两个子区间的结果合并到父区间，而push_down负责更新子区间的结果值、子区间的lazytag以及将父区间的lazytag重置（而不是归零）。