线段树将每个长度不为 1 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

算法模板如下：

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// 懒标记线段树
#define MAX 10000 // 原数组的大小
int todo[4 * MAX + 1]; // 每个节点（区间）要做的事情，即懒标记，例如区间加上某个数、区间取反等
int value[4 * MAX + 1]; // 每个节点（区间）的信息，例如区间和等

/**
 * @brief 维护节点（区间） value，例如计算区间和
 * @param root 当前区间根节点
 */
void maintain(int root)
{
    value[root] = value[root * 2] + value[root * 2 + 1];
}

/**
 * @brief 递归构建树
 * @param a 原数组
 * @param root 当前区间根节点
 * @param l 当前区间左端点
 * @param r 当前区间右端点
 */
void build(vector<int> &a , int root, int l, int r)
{
    todo[root] = 0; // 初始化 todo
    if(l == r)
    {
        value[root] = a[l - 1]; // 叶节点时对 value 的初始化
        return;
    }
    int m = (l + r) >> 1;
    build(a, root * 2, l, m); // 递归构建左子树
    build(a, root * 2 + 1, m + 1, r); // 递归构建右子树
    maintain(root); // 非叶节点时对 value 的初始化
}

/**
 * @brief 对某个节点（区间 [l, r]）的操作，如加上某个数
 * @param root 当前区间根节点
 * @param l 当前区间左端点
 * @param r 当前区间右端点
 * @param add 需要增加的值
 */
void do_(int root, int l, int r, int add)
{
    value[root] += (r - l + 1) * add; // 该区间的和增加了 add * 区间元素数量
    todo[root] += add; // 打上标记：整个区间所有元素加上 add
}

/**
 * @brief 根据需求对区间 [L, R] 操作，如加上某个数
 * @param root 当前区间根节点
 * @param l 当前区间左端点
 * @param r 当前区间右端点
 * @param L 需要操作的整个区间左端点
 * @param R 需要操作的整个区间右端点
 * @param add 需要增加的值
 */
void update(int root, int l, int r, int L, int R, int add)
{
    // 进入此函数，则 [l, r] 和 [L, R] 必然有交集，且有 3 种情况：
    // 1、L <= l <= r <= R: 当前区间完全在要操作的区间之内，无需递归往下操作
    // [l, r] 被拆分为两个子区间：[l, m]、[m + 1, r]，需要下传懒标记并递归操作
    // 2、m >= L: [l, m] 区间与 [L, R] 必然有交集，递归之
    // 3、m < R : [m + 1, r] 区间与 [L, R] 必然有交集，递归之
    // 注意在去除情况 1 后，情况 2 和 3 仍然可以同时成立
    if(L <= l && r <= R) // 情况 1
    {
        do_(root, l, r, add);
        return;
    }
    // 当前区间的一部分在需要操作的区间内
    int m = (l + r) >> 1;
    // 将懒标记下传到子树，并清除自身懒标记，下传懒标记时，将之前子区间欠下的区间和也更新，所以之后子数组也只需处理 add
    if(todo[root])
    {
        do_(root * 2, l, m, todo[root]);
        do_(root * 2 + 1, m + 1, r, todo[root]);
        todo[root] = 0;
    }
    if(m >= L) // 满足情况 2
        update(root * 2, l, m, L, R, add);
    if (m < R) // 满足情况 3
        update(root * 2 + 1, m + 1, r, L, R, add);
    maintain(root); // 情况 2 和 3 下对 value 的更新（情况 1 的更新新在 do_ 中完成）
}

/**
 * @brief 获取区间 [L, R] 的值，如区间和
 * @param root 当前区间根节点
 * @param l 当前区间左端点
 * @param r 当前区间右端点
 * @param L 需要获取的整个区间左端点
 * @param R 需要获取的整个区间右端点
 * @return 当前区间 [l, r] 和操作区间 [L, R] 交集的和
 */
int get(int root, int l, int r, int L, int R)
{
    // 和 update 类似
    // 进入此函数，则 [l, r] 和 [L, R] 必然有交集，且有 3 种情况：
    // 1、L <= l <= r <= R: 当前区间完全在要操作的区间之内，无需递归往下操作
    // [l, r] 被拆分为两个子区间：[l, m]、[m + 1, r]，需要下传懒标记并递归操作
    // 2、m >= L: [l, m] 区间与 [L, R] 必然有交集，递归之
    // 3、m < R : [m + 1, r] 区间与 [L, R] 必然有交集，递归之
    // 注意在去除情况 1 后，情况 2 和 3 仍然可以同时成立
    if (L <= l && r <= R) // 情况 1
        return value[root];
    int rst = 0;
    // 当前区间的一部分在需要操作的区间内
    int m = (l + r) >> 1;
    // 将懒标记下传到子树，并清除自身懒标记，将之前子区间欠下的区间和也更新
    if (todo[root])
    {
        do_(root * 2, l, m, todo[root]);
        do_(root * 2 + 1, m + 1, r, todo[root]);
        todo[root] = 0;
    }
    if (m >= L) // 满足情况 2
        rst += get(root * 2, l, m, L, R);
    if (m < R) // 满足情况 3
        rst += get(root * 2 + 1, m + 1, r, L, R);
    return rst;
}