P3372 【模板】线段树 1 | answerend42的Blog

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在$\mathcal{O}(log N)$的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

线段树维护的信息，需要满足可加性，即能以可以接受的速度合并信息和修改信息，包括在使用懒惰标记时，标记也要满足可加性（例如取模就不满足可加性，对取模然后对取模，两个操作就不能合并在一起做）。

——OI Wiki

update on 2020.2.27 修改了标程，适当的压行

update on 2020.8.5 完善了措辞，更改了示例图片

什么是线段树

线段树，即利用分块思想将序列分为若干段并储存为树。线段树的每一个节点都代表着整个序列中的一段子区间。

举例

给定序列 $1,2,3,4,5,6,7,8,9,10$ 那么我们的树就长这个样子。

注意，这里的节点中数字仅用于指示序列中元素位置，并非元素本身。“$1 \sim 10$”就是序列中 $1$ 号元素到 $10$ 号元素。

不难看出，如果我需要改动 $3$ 号节点，就需要依次向上更改每一个相关节点。

正式介绍

要想使用树，先得有棵树。

左右儿子的表示方式

通过上述介绍，我们可以看出，线段树是一颗二叉树，那么节点 $i$ 的两个儿子编号为 $2i$ 和 $2i+1$。

由于下文中将多次引用，且为了保障代码的可读性，我们可以写两个函数 ls 和 rs 来表示左右儿子。

1 2	inline int ls(ll p) {return p<<1;} inline int rs(ll p) {return p<<1\|1;}

左移一位末位必定为0

$p<<1|1 \iff (p<<1)+1$

向上传递参数

刚刚我们说过，需要依次向上更改每一个相关节点。因此，我们需要向上传递参数。

$\sum_{i=l}^ra_i=\sum_{i=l}^{r/2}a_i+\sum_{i=r/2+1}^{r}a_i$

也就是说，节点p的值等于它的儿子节点的值之和。可依此写出 push_up 函数。

1	inline void push_up(ll p) {ans[p]=ans[ls(p)]+ans[rs(p)];}

建树

有了这么三个函数，我们开始考虑建树。既然父亲节点的值取决于儿子节点的值，又是一棵二叉树，我们完全可以考虑递归建树。

思考：

建树函数需要几个参数？

我这里用到了三个，分别是：

p（当前节点编号） l（当前节点所代表的序列的左端点） r（当前节点所代表的序列的右端点）
递归终点呢？

不难看出，函数最终会运行到 $l=r$ 这种情况，对于这种单个的节点来说一定是没有儿子的，直接将其值储存就可以了，这也就是我们要找的递归终点。
回溯时我们应该做些什么？

直接将这一个节点已知的数据传递向父亲节点（push_up）。

给出建树的代码。

void build(ll p,ll l,ll r)
{
    if(l==r)
    {
        ans[p]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}

区间修改

懒标记

线段树支持修改，但要按照基本法来修改。基本法就是：尽量不去更新区间所包含的单点。

这句话也忒不像人话了，还是来解释一下。如果我们需要修改1~5这个区间，将该区间的值全部加上k。

正常想法是将每一个节点都加上k并上传，这样的时间复杂度是$\mathcal{O}(N)$的，我们不能接受。于是就有了偷懒的办法，也就是Lazy Propagation。

我们注意到1~5是正好被一个节点包含的一个区间，我们只需要将这个节点的值加上k*(5-1+1)就可以了，然后我们为它打上值为k的懒标记，并将标记传递下去，告知这个区间内所有节点都加上了k。时间复杂度也就变成了$\mathcal{O}(logN)$。

这种更改的操作我们用一个 f 函数来表示如下。

inline void f(ll p, ll l, ll r, ll k) {
    tag[p] += k;                //这个节点加上了k
    ans[p] += k * (r - l + 1);  //这个节点的实际更改
}

传递懒标记

我们还需要向下传递，这种操作也就是类似于 push_up ，不过方向要相反。同时还要注意，向上传递时只有一条路，向下传递却有许多路，介于线段树是二叉树这种结构，我们可以对向下传递操作进行二分。

这里给出 push_down 函数

inline void push_down(ll p, ll l, ll r) {
    ll mid = (l + r) >> 1;
    f(ls(p), l, mid, tag[p]);
    f(rs(p), mid + 1, r, tag[p]);
    tag[p] = 0;  //传递向下了之后p本身的标记就需要清零了
}

实现区间修改

终于可以区间修改了，和 push_down 一样，我们对修改的区间进行二分，分别处理每一段区间。

inline void update(ll nl, ll nr, ll l, ll r, ll p, ll k) {
    if (nl <= l && r <= nr) {
        /*
        如果这一区间被整个需修改区间所包含
        直接对这一区间进行修改
        */
        f(p, l, r, k);
        return;
    }
    //否则就向下传递，进行二分
    push_down(p, l, r);
    ll mid = (l + r) >> 1;
    if (nl <= mid)
        update(nl, nr, l, mid, ls(p), k);
    if (nr > mid)
        update(nl, nr, mid + 1, r, rs(p), k);
    push_up(p);  //当然，下层的修改在回溯时需要有序返回上层
}

区间查询

区间的查询类似于修改，同样是基于二分的思想，这里直接给出代码。

ll query(ll q_x, ll q_y, ll l, ll r, ll p) {
    ll res = 0;
    if (q_x <= l && r <= q_y)
        return ans[p];
    //查询的区间包含了这一区间，直接返回，大大提高效率
    ll mid = (l + r) >> 1;
    //在查询时将Lazy Propagation不断向下传递
    push_down(p, l, r);
    //二分查询
    if (q_x <= mid)
        res += query(q_x, q_y, l, mid, ls(p));
    if (q_y > mid)
        res += query(q_x, q_y, mid + 1, r, rs(p));
    return res;
}

标程

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1000005;
ll n, m;
unsigned ll a[N], ans[N << 2], tag[N << 2];
inline int ls(ll p) { return p << 1; }
inline int rs(ll p) { return p << 1 | 1; }
inline void push_up(ll p) { ans[p] = ans[ls(p)] + ans[rs(p)]; }
void build(ll p, ll l, ll r) {
    tag[p] = 0;
    if (l == r) {
        ans[p] = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    push_up(p);
}
inline void f(ll p, ll l, ll r, ll k) {
    tag[p] += k;
    ans[p] += k * (r - l + 1);
}
inline void push_down(ll p, ll l, ll r) {
    ll mid = (l + r) >> 1;
    f(ls(p), l, mid, tag[p]);
    f(rs(p), mid + 1, r, tag[p]);
    tag[p] = 0;
}
inline void update(ll nl, ll nr, ll l, ll r, ll p, ll k) {
    if (nl <= l && r <= nr) {
        f(p, l, r, k);
        return;
    }
    push_down(p, l, r);
    ll mid = (l + r) >> 1;
    if (nl <= mid)
        update(nl, nr, l, mid, ls(p), k);
    if (nr > mid)
        update(nl, nr, mid + 1, r, rs(p), k);
    push_up(p);
}
ll query(ll q_x, ll q_y, ll l, ll r, ll p) {
    if (q_x <= l && r <= q_y)
        return ans[p];
    push_down(p, l, r);
    ll mid = (l + r) >> 1, res = 0;
    if (q_x <= mid)
        res += query(q_x, q_y, l, mid, ls(p));
    if (q_y > mid)
        res += query(q_x, q_y, mid + 1, r, rs(p));
    return res;
}
int main() {
    ll x, y, xx, yy, k, a1;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        scanf("%lld", &a1);
        if (a1 == 1) {
            scanf("%lld%lld%lld", &x, &y, &k);
            update(x, y, 1, n, 1, k);
        } else {
            scanf("%lld%lld", &xx, &yy);
            printf("%llu\n", query(xx, yy, 1, n, 1));
        }
    }
    return 0;
}

学习心得

线段树对于绝大部分水平和我一样刚刚pj1=左右的选手都是很难一下搞懂的知识点，即使是对整个算法有着清晰的认识也很难一次就打对，一定要多打几次，多理解几次。可以适当尝试背诵并用笔默写整个代码，对于迅速找到自己卡壳的地方很有成效。

感谢

本文参考了皎月半洒花的博客，特此感谢。

同时感谢观看本篇博客的朋友们，希望对本篇博客提出意见并指出我的不足之处。