最近正好在学线段树，搞懂后写一篇博客记录一下模板，供日后自己学习参考
原题传送门：洛谷线段树模板题
在这里插入图片描述
经典的RMQ问题，我们用线段树来解决
线段树有一般两种写法，一种是结构体写法，还有一种是用堆结构来写
本蒟蒻采用堆结构来写
实现的操作：
区间修改，区间询问。
注意，堆写法数组要开原数组的四倍！！！(谨记！
此代码已在洛谷AC，可以放心食用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
// 洛谷传送门：https://www.luogu.com.cn/problem/P3372
// 线段树模板
// 区间修改+区间询问
#define maxn 100010
long long a[maxn];        //原数组
long long tree[maxn * 4]; //线段树
long long lazy[maxn * 4]; //懒数组
long long n, m;
void pushdown(int x, int left, int right) // pushdouw的作用是将x节点的lazy数组下传到左右儿子
{
    if (lazy[x] == 0) //如果为0，则该区间没有被修改，不需要下传
        return;
    int mid = (left + right) >> 1;
    lazy[x << 1] += lazy[x];
    tree[x << 1] += lazy[x] * (mid - left + 1);
    lazy[x << 1 | 1] += lazy[x];
    tree[x << 1 | 1] += lazy[x] * (right - mid);
    lazy[x] = 0; //记得清零！
}
void build(int x, int left, int right)
{
    // x代表线段树的节点号,left代表原数组的区间左端点，right代表原数组的区间右端点
    if (left == right)
    {
        tree[x] = a[left];
        return;
    }
    int mid = (left + right) >> 1;
    build(x << 1, left, mid);
    build(x << 1 | 1, mid + 1, right);
    tree[x] = tree[x << 1] + tree[x << 1 | 1];
}
long long query(int x, int left, int right, int tar_left, int tar_right)
{   
	// left和right代表目前访问的节点的区间左右，tar_left和tar_right代表目标区间
    if (left == tar_left && right == tar_right)
        return tree[x];
    // 要用到下一层
    pushdown(x, left, right);               //将上一层对这一层的影响清算完毕
    int mid = (left + right) >> 1;          //将影响延续，继续寻找
    if (tar_left <= mid && tar_right > mid) //右边是大于号才算横跨两个区间！
    {
        long long left_ans = query(x << 1, left, mid, tar_left, mid);
        long long right_ans = query(x << 1 | 1, mid + 1, right, mid + 1, tar_right);
        return left_ans + right_ans;
    }
    if (tar_left <= mid && tar_right <= mid)
    {
        return query(x << 1, left, mid, tar_left, tar_right);
    }
    if (tar_left >= mid)
    {
        return query(x << 1 | 1, mid + 1, right, tar_left, tar_right);
    }
}
void modify(int x, int left, int right, int tar_left, int tar_right, int y)
{
	//y代表修改值
    if (left == tar_left && right == tar_right)
    {
        tree[x] += (right - left + 1) * y;
        lazy[x] += y; //懒数组要标记！
        return;
    }
    // 到达这里，说明要继续向下访问，要将tree继续修改
    pushdown(x, left, right);
    int mid = (left + right) >> 1;
    if (tar_left <= mid && tar_right > mid) // tar_right>mid才是跨两个区间！
    {
        modify(x << 1, left, mid, tar_left, mid, y);
        modify(x << 1 | 1, mid + 1, right, mid + 1, tar_right, y);
    }
    else if (tar_right <= mid)
        modify(x << 1, left, mid, tar_left, tar_right, y);
    else
        modify(x << 1 | 1, mid + 1, right, tar_left, tar_right, y);
    tree[x] = tree[x << 1] + tree[x << 1 | 1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= m; i++)
    {
        int remp;
        cin >> remp;
        if (remp == 1)
        {
            int remp1, remp2, remp3;
            cin >> remp1 >> remp2 >> remp3;
            modify(1, 1, n, remp1, remp2, remp3);
        }
        else if (remp == 2)
        {
            int remp1, remp2;
            cin >> remp1 >> remp2;
            cout << query(1, 1, n, remp1, remp2) << endl;
        }
    }
    return 0;
}