作者：\(9Cirno\)

零、什么是线段树

线段树 \((Segment\ Tree)\) 是算法竞赛中最常用的数据结构之一。线段树之所以称为“树”，是因为其具有树的结构特性。

线段树主要用于处理区间问题，实际上，线段树可以维护所有满足区间 结合律 的问题，功能十分甚至九分的强大（

比如说区间求和就可以用线段树来实现: a[1]+a[2]+a[3]+a[4]+a[5]=(a[1]+a[2]+a[3])+(a[4]+a[5])

对于每一个子节点而言，都表示整个序列中的一段子区间；对于每个叶子节点而言，都表示序列中的单个元素信息；子节点不断向自己的父亲节点传递信息，而父节点存储的信息则是其子节点整合的信息。

线段树强大的一点是它可以实现 \(O(n\log{n})\) 的区间修改和区间查询，在时间复杂度上优于 \(O(n\sqrt{n})\) 的分块，在实用性上超过树状数组，适用于区间 \(\max,\min,\text{xor},\sum\) 等，更具通用性。

为了方便理解，本周报的代码部分以主域的 P1047 原始人，启动 / 【模板】线段树 为例。

一、基于特殊情况下的线段树的构造与实现

0、题面分析

本题的题意可化简为：

已知一个数列 \(a\)，你需要进行下面两种操作：
1. 将区间 \([L, R]\) 内每个数加上 \(k\)；
2. 求出区间 \([L, R]\) 中每一个数的和。

如果使用数组直接储存维护这个数列，虽然修改的效率是 \(O(1)\) 的，但求和的效率就是 \(O(n)\) 的了，总共的复杂度就是 \(O(nm)\)。那么我们便可以使用本周报所介绍的数据结构—— 线段树。

线段树的思想在于将序列中若干个区间在树上用节点表示，其中 \([1, n]\) 区间（\(n\) 表示序列长度）是树的根。而对一个表示区间 \([l, r]\) 的节点（\(l \neq r\)），设 \(mid = \lfloor \frac{l + r}{2} \rfloor\)，将 \([l, mid]\) 和 \([mid + 1, r]\) 作为该节点的左儿子和右儿子节点。

1、准备工作

在算法中使用宏定义有时能起到很大的作用(?)。
因为线段树在区间求和中很可能会爆 \(int\)，所以不妨有：

#define MAXN 100010
#define ll long long

ll n, m;
ll a[MAXN];
ll tree[MAXN << 2]; // 一定要开 4 倍空间
ll lazy[MAXN << 2]; // lazy_tag 之后再讲

2、建树

千万别忘了线段树本质上还是一颗树，对于每一个编号为 \(i\) 的节点，都有编号为 \(i \times 2\) 左儿子以及编号为 \(i \times 2 + 1\) 的右儿子节点，所以考虑有以下代码：

inline ll ls(ll p) { // 获取右儿子节点编号
    return p << 1; // 与 p * 2 等价
}

inline ll rs(ll p) { //获取左儿子节点编号
    return p << 1 | 1; //与 p * 2 + 1 等价
}

当然，也可以写为:

#define ls(p) p << 1
#define rs(p) p << 1 | 1

那么，根据线段树的服务对象，我们便可以得到向上的维护：

inline void push_up(ll p) {
    tree[p] = tree[ls(p)] + tree[rs(p)]; // 维护区间求和
    //tree[p] = std::max(tree[ls(p)], tree[rs(p)]); // 维护区间最大值
    //tree[p] = std::min(tree[ls(p)], tree[rs(p)]); // 维护区间最小值
}

从这里可以看出，push_up 实际上是为了维护父子节点之间的逻辑关系，因此我们可以通过修改 push_up 操作来令线段树服务不同的对象，同时我们也可以从这里看出线段树只能维护满足区间 结合律 的问题。

每个编号为 \(p\) 叶子节点的左右节点为 \(2 \times p\) 和 \(2 \times 2 + 1\)，在本题中，\(tree_{p}\) 存储了区间 \([l,r]\) 的和，那么有 \(mid = \lfloor\frac{l + r}{2}\rfloor\)，\(tree_{p \times 2}\) 存储区间 \([l,mid]\) 的和，\(tree_{p \times 2 + 1}\) 存储区间 \([mid + 1.r]\) 的和。

我们考虑递归建树：

inline void build(ll p, ll l, ll r) {
    if (l == r) {
        tree[p] = a[l];
        return;
    } // 如果左右端点相同，那么必然为叶子节点，而叶子节点会被真实赋值
    ll mid = (l + r) >> 1; // 等价于 (l + r) / 2
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    // 二分递归建树，这也是线段树最大的优化操作
    push_up(p);
    // 别忘了在回溯时维护父亲节点
}

3、区间修改

在讲区间修改前，要先引入一个“懒标记” \((lazy\ tag)\) 的概念。懒标记是线段树的精髓所在。对于区间修改，朴素的想法是用递归的方式一层层修改（类似于线段树的建立），但这样的时间复杂度比较高。使用懒标记后，对于那些正好是线段树节点的区间，我们不继续递归下去，而是打上一个标记，将来要用到它的子区间的时候，再向下传递。

关于区间的修改很像分块，在代码中详细解释吧：

inline void add_lazy(ll p, ll l, ll r, ll k) {
    lazy[p] += k; // 打上懒标记
    tree[p] += k * (r - l + 1); // 修改区间
}

inline void push_down(ll p, ll l, ll r) { // 向下维护
    if (lazy[p]) { // 加入需要修改
        ll mid = (l + r) >> 1;
        add_lazy(ls(p), l, mid, lazy[p]);
        add_lazy(rs(p), mid + 1, r, lazy[p]);
        // 二分修改
        lazy[p] = 0; // 一定别忘了清零
    }
}

inline void update(ll L, ll R, ll p, ll l, ll r, ll k) {
    if (L <= l && R >= r) { // 当前节点对应的区间包含在目标区间中
        add_lazy(p, l, r, k); // 修改
        return;
    }
    push_down(p, l, r); // 在回溯之前向下传递更新
    ll mid = (l + r) >> 1;
    if (L <= mid) update(L, R, ls(p), l, mid, k);
    if (R > mid) update(L, R, rs(p), mid + 1, r, k);
    // 二分更新
    push_up(p);
    // 别忘了在回溯时维护父亲节点
}

对于复杂度，由于完全二叉树的深度不超过 \(O(\log{n})\)，那么单点修改显然是 \(O(\log{n})\)。

4、区间查询

区间查询的方法与区间修改几乎完全一致，直接上代码了：

inline ll query(ll L, ll R, ll p, ll l, ll r) {
    if (L <= l && R >= r) return tree[p]; // 当前节点对应的区间包含在目标区间中，直接返回
    push_down(p, l, r); // 在回溯之前向下传递更新
    ll mid = (l + r) >> 1;
    ll res = 0;
    if (L <= mid) res += query(L, R, ls(p), l, mid);
    if (R > mid) res += query(L, R, rs(p), mid + 1, r);
    // 二分查找
    return res;
}

5、主函数部分

int main () {
    scanf("%lld %lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    // 简单的输入
    build(1, 1, n); // 建树
    while (m--) {
        ll opt, l, r, k;
        scanf("%lld", &opt);
        if (opt == 1) {
            scanf("%lld %lld %lld", &l, &r, &k);
            update(l, r, 1, 1, n, k); // 更新
        } else {
            scanf("%lld %lld", &l, &r);
            ll ans = query(l, r, 1, 1, n);
            printf("%lld %lld\n", ans, (ans << 1) + (ans << 2)); //题面的坑 and 出题人的恶趣味
        }
    }
    return 0;
}

二、最后

因为鄙人水平有限，本文只介绍了最基本的线段树用法。

在维护不同的信息时，需要注意是否需要乘区间长度、不同的标记之间是否相互影响等。

其实线段树的题目千奇百怪，有很多技巧——在你真正理解线段树之后，可以用它来实现许多骚操作（如主域的 P1001 A + B Problem（笑））。

最后的最后，永远膜拜 \(\text{XzyStudio}\) \(dalao\)