数据结构: 线段树 (Lazy Propagation/Tag 延迟标记)

延迟标记提出的背景

对于一般单点修改, 区间查询的情况, 我们并不需要延迟标记, 只需要push_up操作就可以实现. 甚至对于区间加上一个数的区间修改单点查询的情况, 我们也可以用线段树进行维护. 但是对于一般的区间修改, 区间查询操作, 延迟标记就是不可避免的.

在线段树的“区间查询”指令中, 每当遇到被询问区间$[l,r]$完全覆盖的结点时, 可以立即把该结点上存储的信息作为候选答案返回, 我们已经证明, 被询问区间$[l,r]$在线段树上会被分成$O(logN)$个小区间(结点), 从而在$O(logN)$的时间内求出答案. 不过, 对于“区间修改”指令, 如果某个结点被修改区间$[l,r]$完全覆盖, 那么以该结点为根的子树中的所有结点存储的信息都会发生变化, 若逐一进行更新, 将使得一次区间修改指令的时间复杂度增加到$O(N)$, 这是我们不能接受的.

试想, 如果我们在一次修改指令中发现结点$p$代表的区间$[p_l, p_r]$被修改区间$[l,r]$完全覆盖, 并且逐一更新了子树$p$中的所有结点, 但是在之后的查询指令中却根本没有用到$[l,r]$的子区间(子树内的结点)作为候选答案, 那么更新$p$的整棵子树就是徒劳的.

换言之, 我们执行修改指令时, 同样可以在$l \leq p_l \leq p_r \leq r$的情况下立即返回, 只不过在回溯之前向结点$p$增加一个标记, 标识“该结点曾经被修改, 但其子结点尚未被更新”.

如果在后续的指令中(修改和查询), 需要从结点$p$向下递归, 我们再检查$p$是否具有标记. 若有标记, 就根据标记信息更新$p$的两个子结点, 同时为$p$的两个子结点增加标记，然后清除$p$的标记.

在修改中如果要继续向下进入更深层的递归, 那么我们就要先将两个子结点更新, 这样才能确保回溯的时候的push_up的正确性, 同时也能满足“延迟”这一特性,

同样的, 在查询中, 为了满足正确性, 我们需要将延迟标记的信息向下传递, 以便能得到正确的候选答案.

我们把将延迟标记的信息向下传递的操作叫做push_down.

也就是说, 除了在修改指令中直接划分的$O(logN)$个结点之外, 对任意结点的修改都延迟到“在后续操作中递归进入它的父结点时”再执行. 这样以来, 每条查询或修改指令的时间复杂度都降低到了$O(logN)$, 这样的标记被称为“延迟标记”. 延迟标记提供了线段树中从上到下传递信息的方式. 这种“延迟”也是设计算法与解决问题的一个重要思路.

需要指出的是, 延迟标记的含义为“该结点曾经被修改, 但其子结点尚未被更新”, 即延迟标记标识的是子结点等待更新的情况. 因此, 一个结点被打上“延迟标记”的同时, 它自身保存的信息应该已经修改完毕. 在编写代码的时候, 一定要注意“更新信息”与“打标记”之间的关系, 避免出现错误.

这里给出push_down操作的实现

struct Node {
    int l, r;
    type S // 信息
    type add; // 延迟标记
}

void push_down(int u) {
    Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1]; 
    if (root.add) { // 如果父结点有延迟标记
        // 更新左子结点的延迟标记, 更新左子结点的信息
        // 更新右子结点的延迟标记, 更新右子结点的信息
        root.add.clear // 清除父结点的延迟标记
    }
}

例题:一个简单的整数问题2

描述

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r，表示询问数列中第 l∼r 个数的和。
对于每个询问，输出一个整数表示答案。

输入格式
第一行两个整数 N,M。

第二行 N 个整数 A[i]。

接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。

输出格式
对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围
1≤N,M≤10^5,
|d|≤10000,
|A[i]|≤10^9

思路

本题涉及到区间修改和区间查询, 故我们可以使用带延迟标记.

同时由于查询的是区间和, 故我们在线段树中维护对应的区间和属性, 可以发现这个维护的属性是完备的.

代码:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL; 

const int N = 1e5 + 10; 

int n,m; 
int w[N]; 

struct Node {
    int l, r; 
    LL sum; 
    LL add; 
} tr[N * 4]; 

void push_up(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void push_down(int u) {
    Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1]; 
    if (root.add) {
        left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add; 
        right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add; 
        root.add = 0; 
    }
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {l, r, w[l], 0}; 
    } else {
        tr[u] = {l, r}; 
        int mid = (l + r) >> 1; 
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); 
        push_up(u);
    }
}

void modify(int u, int l, int r, int d) {
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d; 
        tr[u].add += d; 
    } else {
        push_down(u);  // 递归子结点的时候执行push_down, 延迟的含义
        int mid = (tr[u].l + tr[u].r) >> 1; 
        if (l <= mid) modify(u << 1, l, r, d); 
        if (r > mid) modify(u << 1 | 1, l, r, d); 
        push_up(u); 
    }
}

LL query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) {
        return tr[u].sum; 
    } else {
        push_down(u); //递归子结点的时候执行push_down, 延迟的含义
        int mid = (tr[u].l + tr[u].r) >> 1; 
        LL sum = 0;
        if (l <= mid) sum += query(u << 1, l, r); 
        if (r > mid) sum += query(u << 1 | 1, l, r); 
        return sum; 
    }
}

int main() {
    scanf("%d %d",&n, &m);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]); 
    }
    
    build(1, 1, n); 
    
    int l, r, d; 
    char op[2]; 
    
    while(m --) {
        scanf("%s %d %d", op, &l, &r); 
        
        if(*op == 'C') {
            scanf("%d",&d); 
            
            modify(1, l, r, d); 
        } else {
            LL res = query(1, l, r);
            printf("%lld\n", res);
        }
    }
    
    return 0; 
}

扫描线(特殊情况)

这是一个非常经典的问题, 即要求给定平面直角坐标系中的$N$个矩形的面积并. 即这些矩形的并集在坐标系中覆盖的总面积. 如图所示

注意, 矩形的边应与坐标轴平行.

如何求面积并呢? 我们可以利用积分的思想. 试想, 如果我们用一条竖直直线从左到右扫过整个坐标系,那么直线上被并集图形覆盖的长度只会在每个矩形的左右边界处发生变化.

换言之, 整个并集图形可以被分成$2*N$段, 每一段在扫描线上覆盖的长度是固定的, 因此该段的面积就是$L*该段的宽度$, 各段面积之和即为所求. 这条直线就被成为扫描线, 这种思想为扫描线法.

具体来说, 我们可以取出$N$个矩形的左右边界. 若一个矩形的对角顶点坐标为$(x_1,y_1)$, $(x_2,y_2)$, 不妨设$x_1 < x_2$, $y_1 < y_2$. 且我们记左边界对应的边的权值为$1$, 可以用一个四元组表示, 即$(x_1, y_1, y_2, 1)$. 记右边界对应的边的权值为$-1$, 对应的四元组为$(x_2, y_1, y_2, -1)$.

我们不妨将这$2N$个三元组按照$x$坐标的大小进行排序, 这样可以直观的符合扫描线的遍历顺序. 故可以看出, 上述的面积公式$L*该段的宽度$, 即为$L*(x_i - x_{i-1})$. 其中$x_i$和$x_{i-1}$都是可以直接在排序后的数组中获得. 故我们只需要考虑如何计算$L$.

在图中, 我们将矩形的左边权值赋为$1$, 右边的权值赋为$-1$. 故当我们从左往右遍历时, 我们每次可以将矩形的边所对应的$y$轴区间上加上对应的权值, 我们称对应区间的权值大于$0$时为被覆盖. 此时在遍历每一个$x$的时候, 对应$y$区间被覆盖的长度和即为所求$L$.

那么在遍历$x$的过程中, 我们可以抽象出两个操作. 即, 1. 给一段$y$区间加上一个数. 2. 查询一段$y$区间的被覆盖的长度.

在数据范围很大的时候, 如果只用普通的数组来实现这两个操作的时间复杂度是不能接受的. 故我们可以用线段树来实现这两个操作.

离散化(给定y坐标是小数的一般情况)

在一般情况下, 给定的$y$的坐标可能是小数. 通常, 我们习惯于用线段树维护点的情况, 即我们可能会想到用线段树来维护$y$轴上的每一个点. 而维护每一个点意味着我们要去维护所有实数,由于实数是稠密的, 我们是不可能开出那么大空间的线段树的. 故我们可以使用离散化.这也适用于$y$的范围太大的情况.

运用离散化的思想, 我们就需要抛开点的意义转而维护区间, 即所有在问题中提及到的区间. 即我们需要对所有的$y$坐标进行离散化, 假设离散化后的数组为$ys$. 那么在下标$i$的意义下$0 \leq i < 2*n$其中$n$为矩形个数. 下标$i$就对应着一段$y$区间, 即$ys[i]$到$ys[i+1]$, 注意$ys[i]$即为原始$y$坐标.

离散化后, 我们需要用$find$函数二分查找原始值$y$在$ys$中对应的下标. 同时, 根据$i$在离散化后的数组$ys$中的意义(表示一段区间).

修改操作的下标

如果我们想要对于一段区间$[row_l, row_{r}]$进行修改. 那么对应到$ys$数组中就是$[find(row_l), find(row_{r}) - 1]$, 其中$row$表示原始$y$的坐标值. 最后的$-1$是因为离散化后, $find(row_{r})$表示的其实是$row_r$到$row_{r+1}$中区间的值, 我们让其$-1$才能表示$row_{r-1}$到$row_{r}$的区间.

线段树的维护范围

在线段树中, 我们只需要维护对应的区间(离散化后的数组)就行了, 即每个叶子结点都对应着一段离散化数组中的区间, 由于$ys$有$2*n$个, 即$2*n$个端点. 那么区间的个数就为$2*n-1$. 由于离散化数组从下标$0$开始, 那么线段树只需要从$0$到$2*n-2$的范围建树就行.

此时线段树中即$tr[第一个叶子结点]$的意义就是$ys$数组中的$ys[0]$, 即第一段区间, $ys[0]$到$ys[1]$, 即$y$原始坐标对应的区间(注意ys是排序过的).

线段树中结点信息

由于线段树中维护的是区间, 那么线段树中结点存储的左端点$l$,右端点$r$就是根据离散化数组的下标而来. 同时需要额外存储一个$cnt$信息, 表示该区间是否已经被覆盖(即权值是否大于$0$). 以及一个$len$信息, 表示该区间中被覆盖的长度.

由于存储信息的特殊性, 我们需要额外讨论一下如何维护父子信息. 首先, 如果当前父结点已经被覆盖了, 即$cnt>0$, 那么其就不需要用子结点计算了, 可以直接将其$len$赋值为对应的原始$y$坐标区间的长度$ys[tr[u].r + 1] - ys[tr[u].l]$, $+1$是因为线段树中维护的是区间, 想要得到对应的原始$y$的坐标值, 在$ys$数组中需要$+1$. 否则, 就是当前父结点没有被覆盖, 如果当前不是叶子结点的话, 那么当前区间的被覆盖长度$len$就需要从左右子结点中计算而来. 如果当前是叶子结点的话, 就将当前的区间的$len$赋为$0$. (最后一个情况实际对应了当我们扫描线经过右边界以后, 右边界的权值为$-1$.)

延迟/懒标记和push_down操作的必要性

由于本题涉及到区间的修改和查询, 就算在离散化后也是有需要在维护区间的线段树中意义下的一段区间进行修改. 那么自然的, 我们会想到使用push_down操作在修改和查询中必要的时候将添加的标记往下递归.

但是push_down操作在该特殊情况下的扫描线是不需要的. 首先, 当我们在query时, 我们每次都会对整个区间进行查询, 那么其必定包含线段树中根结点的整个左右区间, 而我们的入口就是线段树的根结点, 那么其在一开始就会直接return. 不会使用modify操作. 其实, 由于每次只会对整个区间进行查询, 我们可以不用显示地写出query, 而是用$tr[1].len$进行代替.

其次, 当我们在modify区间时(为区间整体加上一个数). 由于push_down在modify中同时扮演着降低时间复杂度和正确更新, 我们只需要说明不会存在被错误更新就行.

不妨考虑一个结点对, $u,l,r$. 首先由于线段树区间的修改是成对出现的, 同时区间加一定是在区间减前面出现. 若$u.cnt = 0$, 其能用两个子结点的信息进行更新, 故正确. 若$u.cnt > 0$, 那么其信息就无关子结点的信息了, 因为其之前一定是整段区间被加上了一个数, 子结点无论如何修改其意义就是在一个大矩形中的小矩形, 故该情况答案也是正确的.

综上所述, 我们并不需要懒标记和push_down操作也能得到正确的答案. 观察代码可以发现时间复杂度也是不变的.

例题:Atlantis

描述

有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。

其中一些甚至包括岛屿部分地图。

但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。

您的朋友 Bill 必须知道地图的总面积。

你自告奋勇写了一个计算这个总面积的程序。

输入格式
输入包含多组测试用例。

对于每组测试用例，第一行包含整数 n，表示总的地图数量。

接下来 n 行，描绘了每张地图，每行包含四个数字 x1,y1,x2,y2（不一定是整数），(x1,y1) 和 (x2,y2) 分别是地图的左上角位置和右下角位置。

注意，坐标轴 x 轴从上向下延伸，y 轴从左向右延伸。

当输入用例 n=0 时，表示输入终止，该用例无需处理。

输出格式
每组测试用例输出两行。

第一行输出 Test case #k，其中 k 是测试用例的编号，从 1 开始。

第二行输出 Total explored area: a，其中 a 是总地图面积（即此测试用例中所有矩形的面积并，注意如果一片区域被多个地图包含，则在计算总面积时只计算一次），精确到小数点后两位数。

在每个测试用例后输出一个空行。

数据范围
1≤n≤10000,
0≤x1<x2≤100000,
0≤y1<y2≤100000
注意，本题 n 的范围上限加强至 10000。

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e4 + 10; 

int n; 
vector<double> ys; 

struct Segment { // 四元组
    double x, y1, y2; 
    int k; 
    
    bool operator< (const Segment &t) const{
        return x < t.x; 
    }
    
} seg[N * 2]; 

struct Node { // 线段树中的结点
    int l, r; 
    int cnt; 
    double len; 
} tr[N * 8]; 

int find(double y) { // find操作, 寻找离散化后的值
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin(); 
}

void push_up(int u) { // push_up操作, 根据信息考虑结点对进行计算
    if (tr[u].cnt) {
        tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l]; 
    } else if (tr[u].l != tr[u].r) {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len; 
    } else {
        tr[u].len = 0; 
    }
}

void build(int u, int l, int r) { // 建立空树
    if (l == r) {
        tr[u] = {l, r, 0, 0}; 
    } else {
        tr[u] = {l, r}; 
        int mid = (l + r) >> 1; 
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); 
    }
}

void modify(int u, int l, int r, int v) { // 区间修改
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].cnt += v; 
        push_up(u); // 加上一个数以后要push_up, 重新计算一下信息
    } else {
        int mid = (tr[u].l + tr[u].r) >> 1; 
        if (l <= mid) modify(u << 1, l, r, v); 
        if (r > mid) modify(u << 1 | 1, l, r, v); 
        push_up(u); 
    }
}


int main() {
    
    int T = 1; 
    while(scanf("%d",&n), n) {
        
        ys.clear(); 
        
        for (int i = 0, j = 0; i < n; i++) {
            double x1, y1, x2, y2; 
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            
            seg[j++] = {x1, y1, y2, 1}; 
            seg[j++] = {x2, y1, y2, -1}; 
            
            ys.push_back(y1); 
            ys.push_back(y2); 
        }
        
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());  // 离散化
        
        sort(seg, seg + 2 * n); // 2*n个x下标
        
        build(1, 0, ys.size() - 2); // 线段树的范围, 上面讨论过
        
        double res = 0; 
        for (int i = 0; i < 2 * n; i++) {
            if (i > 0) res += tr[1].len *  (seg[i].x - seg[i - 1].x); // 从第二个x开始计算答案
            modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k); // 根据当前的y进行区间修改
        }
        
        printf("Test case #%d\n", T++); 
        printf("Total explored area: %.2lf\n\n", res); 
    
    }
}

线段树维护维护区间加和区间乘操作

有时候我们会遇到需要同时维护两种类型的区间修改, 即一段区间$[l,r]$同时加上一个数$a$, 或者乘上一个数$b$. 然后需要询问一段区间的和.

在前面我们讨论了对于区间加上一个数的操作. 如果只是单一的要我们也对于区间乘上一个数作类比, 那么我们可以用一个乘法的延迟标记$mul$. $mul$标记了当前结点已经被修改了而以该结点为根的整棵子树的还未被修改. 发现对于延迟标记的传递也是类比于加法的, 我们让左右子结点的$mul$, 即$tr[u << 1].mul$和$$tr[u « 1

1].mul$分别乘以$mul$, 然后将其$sum$也进行相对应的改变, 即$sum*mul$$.

对于初始的状态, 我们需要让$mul=1$. 这样就不会有修改的意义, 因为$1$在乘法中作一元.

值得提出的是, 当我们在考虑延迟标记的传递时, 也需要遵守一下系统的更新方法. 即在一般情况下, 优先考虑需要修改的信息, 将这些信息存储为延迟标记. 然后考虑更新时, 可以先考虑push_down操作, 考虑如何从父结点出发传递延迟标记给儿子结点. 此时不光要更新存储的候选答案信息, 还有延迟标记. 对于延迟标记的更新, 需要特别注意延迟标记的意义, 其表示该结点已经被更新, 但是以该结点为根的树的子结点还未被更新. 故我们的延迟标记要在更新上要有一个累计的意义.

比如说我们要计算一段区间的$sum$, 而我们被要求区间加一个数$c$, 那么我们在往下传递延迟标记的时候就需要让子结点的延迟标记$add$加上$c$. 这样以后子结点递归更新的时候, 子结点的子结点的$sum$就能被正确更新, 这也是延迟的意义. 再比如, 我们如果被要求在区间内乘以一个数$d$, 那么我们在传递延迟标记的时候就需要相对应的让子结点的延迟标记$mul$乘以$d$. 更要指出的是, 延迟标记的更新应该满足区间备选信息的更新. 同时, 结点被声明了懒标记的意义下, 该结点的备选信息的更新应该是以备选信息和懒标记表示出, 换言之, 备选信息本身是以备选信息和懒标记表示的. 比如, 在上面的区间加上一个数, 那么备选信息就应该是一个$sum + add$的形式, 一开始$add$为$0$. 乘以一个数, 就为$sum*mul$的形式，一开始$mul$为$1$. 我们会在下面看到这个形式与延迟标记的更新有很大的关联.

现在回到我们的问题上来, 如果我们同时被要求维护区间加和区间乘两个操作. 首先, 我们需要声明两个延迟标记, $add$和$sum$. 一个最大的问题就是如何来更新$sum$, 如果将两个操作分开维护, 那么我们可以发现, 延迟标记的更新会依赖于$sum$是如何被更新的. 我们在前面讨论过备选信息本身应该是以其自身和懒标记表示的. 但是我们当前有两个延迟标记, 该表达式就有二义性了, 一个是$(sum + add) *mul$, 另外一个是$sum*mul+add$. 我们需要确定选择哪一种表达式作为当前$sum$的意义, 以便能方便以后的更新.

假设我们定义$sum$为第一种$(sum + add) *mul$, 如果我们要进行区间乘操作, 假设区间被乘上了数$mul'$, 那么$sum$需要被更新为$(sum + add)*mul*mul'$.为了方便我们的计算, 我们想让区间加和区间乘具有“封闭性”, 也就是说进行了这两个操作以后仍然能保持$(sum + add) *mul$的结构. 可以发现对于$sum$更新只需要乘上一个$mul$, 懒标记的更新$add$不需要修改, 只需要让$mul*mul'$就行. 而对于$add$操作, 其并不具有“封闭性”, 如果不具有封闭性, 这意味着我们很难找到延迟标记的更新通式.

现在假设我们定义$sum$为第二种$sum*mul+add$. 假设我们要进行区间加上一个$add'$操作, 那么只需要让$add+add'$. 如果要进行区间乘以$mul'`操作,$(summul +add)mul’$, 我们将其展开$summulmul’+addmul’$. 发现只需要将$mulmul’$, 让$add*mul’$$就行. 可以发现这种定义方式是符合封闭性的.

那么我们可以选择第二种的表达式的定义方式,选择的方式就是利用我们更新$sum$, $add$ 以及$mul$的方式来给其下定义. 即每次判断操作, 若为$add'$, 则更新$sum+add*(r-l+1)$, $add+add'$, $mul$不变. 如果为$mul'$, 则更新$sum*mul'$, $add*mul'$ 以及$mul*mul'$.

简化写法, 合并加乘

发现每一次判断操作有非常多的冗余, 可以发现这是symantic coupling. 我们可以将加乘合并到一个函数中, 那么意味着每一次的更新我们需要按照一个$add$和$mul$的表达式来更新.

这样合并更新的可行性由$add=0$以及$mul=1$分别作一元得出. 故每次更新不需要判断, 如果是$add$操作, 就让$mul=1$, 如果是$mul$操作就让$add=0$.

因为每次合并了操作, 故我们需要重新来看一下延迟标记和$sum$的更新.

前面我们讨论了备选信息和延迟标记的表达式应该定义为$sum*mul + add$. 由于我们合并更新了加乘, 故为$(sum*mul+add)*mul'+add'$, 展开$sum*mul*mul'+add*mul'+add'$. 故我们要让$mul*mul'$, $add*mul'+add'$.

总结, 我们发现了备选信息和延迟标记之间的关系, 得出了备选信息可以用其自身和延迟标记的表达式表示出. 同时我们发现了多个延迟标记存在时, 我们应该选取一个表达式去消除多义性, 该表达式的选取应该需要满足封闭性, 使得延迟标记可以方便地更新.

例题:维护序列

描述

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。

有长为 N 的数列，不妨设为 a1,a2,…,aN。

有如下三种操作形式：

把数列中的一段数全部乘一个值；
把数列中的一段数全部加一个值；
询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 P 的值。
输入格式
第一行两个整数 N 和 P；

第二行含有 N 个非负整数，从左到右依次为 a1,a2,…,aN；

第三行有一个整数 M，表示操作总数；

从第四行开始每行描述一个操作，输入的操作有以下三种形式：

操作 1：1 t g c，表示把所有满足 t≤i≤g 的 ai 改为 ai×c；
操作 2：2 t g c，表示把所有满足 t≤i≤g 的 ai 改为 ai+c；
操作 3：3 t g，询问所有满足 t≤i≤g 的 ai 的和模 P 的值。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

输出格式
对每个操作 3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

数据范围
1≤N,M≤10^5,
1≤t≤g≤N,
0≤c,ai≤10^9,
1≤P≤10^9

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL; 

const int N = 1e5 + 10; 

int n, m, p; 
int w[N]; 

struct Node {
    int l, r; 
    int sum; 
    int add, mul; 
} tr[N * 4]; 

void push_up(int u) {
    tr[u].sum = ((LL)tr[u << 1].sum + tr[u << 1 | 1].sum) % p; 
}

void eval(int u, int add, int mul) {
    tr[u].sum = ((LL)tr[u].sum * mul + (LL)(tr[u].r - tr[u].l + 1) * add) % p; 
    tr[u].mul = ((LL)tr[u].mul * mul) % p; 
    tr[u].add = ((LL)tr[u].add * mul + add) % p; 
}

void push_down(int u) {
    eval(u << 1, tr[u].add, tr[u].mul); 
    eval(u << 1 | 1, tr[u].add, tr[u].mul); 
    tr[u].add = 0, tr[u].mul = 1; 
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {l, r, w[l], 0, 1};
    } else {
        tr[u] = {l, r, 0, 0, 1}; 
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); 
        push_up(u);
    }
}

void modify(int u, int l, int r, int add, int mul) {
    if (l <= tr[u].l && tr[u].r <= r) {
        eval(u, add, mul); 
    } else {
        push_down(u);
        int mid = (tr[u].l + tr[u].r) >> 1; 
        if (l <= mid) modify(u << 1, l, r, add, mul); 
        if (r > mid) modify(u << 1 | 1, l, r, add, mul); 
        push_up(u);
    }   
}

int query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) {
        return tr[u].sum; 
    } else {
        push_down(u); 
        int mid = (tr[u].l + tr[u].r) >> 1;
        int sum = 0; 
        if (l <= mid) sum = query(u << 1, l, r); 
        if (r > mid) sum = ((LL)sum + query(u << 1 | 1, l, r)) % p; 
        return sum; 
    }
}

int main() {
    scanf("%d %d", &n, &p); 
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]); 
    }
     
    build(1, 1, n); 
    
    scanf("%d", &m); 
    
    while (m--) {
        int op; 
        scanf("%d", &op);
            
        int t, g, c; 
        if (op == 1) {
            scanf("%d %d %d", &t, &g, &c);
            
            modify(1, t, g, 0, c); 
        } else if (op == 2) {
            scanf("%d %d %d", &t, &g, &c); 
            
            modify(1, t, g, c, 1); 
        } else {
            scanf("%d %d", &t, &g);
            printf("%d\n", query(1, t, g)); 
        }
    }
    
    return 0;
    
}

参考

李煜东《算法竞赛进阶指南》