题解：P3373 【模板】线段树 2

· · 题解

引入

这道题我们需要维护区间加、区间乘、区间和，由于序列长度和询问次数都比较大，暴力显然不行。那么我们这里需要一种数据结构，维护区间。这正是线段树所能维护的东西。

介绍

线段树是一种二叉树数据结构，用于高效处理区间查询和区间更新操作。它将区间递归地划分为子区间，每个节点代表一个区间，并存储该区间的相关信息（如区间和、最大值等）。

对于长度为 n 的序列，线段树就是一棵满二叉树，线段树高度为 O(\log n)，所以每次操作的复杂度为 O(\log n)，足以通过此题。

懒标记

懒标记介绍

对于每个修改操作，如果我们将所有标记下传到叶子，这会导致时间复杂度爆炸。所以我们能否有更优的标记方式？正如我所说，这就是懒标记。对于每个节点，我们维护它的乘法标记和加法标记，每次查询或修改需要用到这个标记之后再下传即可。由于我们每次操作都是从树根开始操作，所以每个标记都必定会正确传到某个节点。这样使得标记的时间复杂度是常数级别。

懒标记的顺序

这里懒标记的顺序并不能交换。当只有乘法标记或者加法标记的时候，直接下传。如果都有，请注意，需要先传乘法再传加法。证明如下：

假设有一个值 x，我们先加 a 再乘 m，结果是 (x + a) \times m。而如果先乘 m 再加 a，结果是 x \times m + a，这显然不等价。那么必须要通过先乘再加的传递方式进行传递。

操作方法

所有的操作我们都使用同样的结构：

  1. 如果当前节点区间完全包含在目标区间内，直接更新或返回结果。
  2. 否则，先下放标记，然后递归处理子节点。
  3. 最后合并子节点的结果。

时间复杂度

如上已经分析。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
struct Tree {
    int l, r;
    long long sum, add, mul;
}tree[N << 2];
long long n, q, m, a[N];

void build(int p, int l, int r) {
    tree[p].l = l;
    tree[p].r = r;
    tree[p].mul = 1;
    if (l == r) {
        tree[p].sum = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}

void spread(int p) {
    if (tree[p].mul != 1) {
        tree[p << 1].sum = tree[p << 1].sum * tree[p].mul % m;
        tree[p << 1].add = tree[p << 1].add * tree[p].mul % m;
        tree[p << 1].mul = tree[p << 1].mul * tree[p].mul % m;
        tree[p << 1 | 1].sum = tree[p << 1 | 1].sum * tree[p].mul % m;
        tree[p << 1 | 1].add = tree[p << 1 | 1].add * tree[p].mul % m;
        tree[p << 1 | 1].mul = tree[p << 1 | 1].mul * tree[p].mul % m;
        tree[p].mul = 1;
    }
    if (tree[p].add) {
        tree[p << 1].sum = (tree[p << 1].sum + tree[p].add * (tree[p << 1].r - tree[p << 1].l + 1)) % m;
        tree[p << 1].add = (tree[p << 1].add + tree[p].add) % m;
        tree[p << 1 | 1].sum = (tree[p << 1 | 1].sum + tree[p].add * (tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1)) % m;
        tree[p << 1 | 1].add = (tree[p << 1 | 1].add + tree[p].add) % m;
        tree[p].add = 0;
    }
}

void add(int p, int l, int r, long long k) {
    if (tree[p].r < l || tree[p].l > r)
        return;
    if (l <= tree[p].l && tree[p].r <= r) {
        tree[p].sum = (tree[p].sum + k * (tree[p].r - tree[p].l + 1)) % m;
        tree[p].add = (tree[p].add + k) % m;
        return;
    }
    spread(p);
    add(p << 1, l, r, k);
    add(p << 1 | 1, l, r, k);
    tree[p].sum = (tree[p << 1].sum + tree[p << 1 | 1].sum) % m;
}

void mul(int p, int l, int r, long long k) {
    if (tree[p].r < l || tree[p].l > r)
        return;
    if (l <= tree[p].l && tree[p].r <= r) {
        tree[p].sum = tree[p].sum * k % m;
        tree[p].add = tree[p].add * k % m;
        tree[p].mul = tree[p].mul * k % m;
        return;
    }
    spread(p);
    mul(p << 1, l, r, k);
    mul(p << 1 | 1, l, r, k);
    tree[p].sum = (tree[p << 1].sum + tree[p << 1 | 1].sum) % m;
}

long long query(int p, int l, int r) {
    if (tree[p].r < l || tree[p].l > r)
        return 0;
    if (l <= tree[p].l && tree[p].r <= r)
        return tree[p].sum % m;
    spread(p);
    return (query(p << 1, l, r) + query(p << 1 | 1, l, r)) % m;
}

int main() {
    cin >> n >> q >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int op, l, r;
        long long k;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> k;
            mul(1, l, r, k);
        } else if (op == 2) {
            cin >> k;
            add(1, l, r, k);
        } else
            cout << query(1, l, r) << '\n';
    }
}

提醒

在一道题中，树状数组的常数相对线段树小很多，如果树状数组比较好实现，最好不要用线段树。容易被卡常。

线段树空间需要开到 n \times 4 的四倍，在 n=2^k+1 的情况下，例如 n=9，需要 31 个节点，接近 4 倍。（如果你用的是动态开点的话当我没说）

Update：

懒标记传递顺序有笔误，现已修改。