一个简单的整数问题2

区间查询 区间修改 线段树区间修改懒标记 T3 线段树 243. 一个简单的整数问题2 - AcWing题库

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

1. C l r d，表示把 $A[l],A[l+1],\dots ,A[r]$ 都加上 $d$。
2. Q l r，表示询问数列中第 $l\sim r$ 个数的和。

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

输入格式

第一行两个整数 $N,M$。

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

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

输出格式

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

每个答案占一行。

数据范围

$1\le N,M\le 10^5$,
$|d|\le 10000$,
$|A[i]|\le 10^9$

输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出样例：

4
55
9
15

思路

之前是用差分的小技巧拿树状数组做区间修改。这里直接用线段树来写。

在正常的单点查询模板中加上 lazy 技巧 和 pushdown 操作即可实现, 核心思想是当在 修改 $L,R$ 区间时, 不去直接走到底把所有叶子结点改一遍, 而是只修改 代表$L,R$整个区间的几个节点, 并在其上面标记 lazy 记录, 代表要把这个区间内修改。

标记完并更新节点的sum值后就直接返回, 当update或者query需要用到 $L,R$ 区间里面的节点时, 在经过 $L,R$ 节点便会执行 pushdown 操作, 把 之前记录的 lazy 标记扩散给子节点并更新子节点的sun值。 此时也不会直接更新到底部, 只是按需更新。

由此便可以优化很多时间复杂度。

pushdown函数中需要实现从当前节点的lazy修改子节点的sum和lazy：

Node &u = t[u], &l = t[u << 1], &r = t[u << | 1];
l.lazy += u.lazy, l.sum += u.lazy * (l.r - l.l + 1); // 左儿子区间共 l.r - l.l + 1 个数, 故需要都算上
r.lazy += u.lazy, r.sum += u.lazy * (r.r - r.l + 1);
u.lazy = 0; // 别忘了重置

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#define lson l,mid,u << 1
#define rson mid + 1, r, u << 1 | 1
using namespace std;
const int N = 1e5+ 10;
typedef long long ll;
struct Node {
    int l,r;
    ll sum, lazy;
}t[N << 2];
 
int n,m;
int a[N];
 
void pushup(int u)
{
    t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
}
 
 
 
void pushdown(int u)
{
    Node &l = t[u << 1], &r = t[u << 1 | 1];
    if(t[u].lazy)
    {
        l.sum += (ll)t[u].lazy * (l.r - l.l + 1);
        l.lazy += t[u].lazy;
        r.sum += (ll)t[u].lazy * (r.r - r.l + 1);
        r.lazy += t[u].lazy;
        t[u].lazy = 0;
    }
}
 
void build(int l, int r, int u = 1)
{
    t[u] = {l,r,0,0};
    if(l == r)
    {
        t[u] = {l,r,a[l], 0};
        return;
    }
    int mid = l + r >> 1;
    build(lson), build(rson);
    pushup(u);
}
 
void update(int L, int R, int val, int l = 1, int r = n, int u = 1)
{
    if(L <= l && r <= R)
    {
        t[u].sum += (ll)val * (t[u].r - t[u].l + 1);
        t[u].lazy += val;
        return;
    }
    pushdown(u);
    int mid = l + r >> 1;
    if(L <= mid) update(L,R,val,lson);
    if(R > mid) update(L,R,val,rson);
    pushup(u);
}
 
ll query(int L, int R, int l = 1, int r= n, int u = 1)
{
    if(L <= l && r <= R)
        return t[u].sum;
    pushdown(u);
    int mid =l + r >> 1;
    ll sum = 0;
    if(L <= mid) sum += query(L, R, lson);
    if(R > mid) sum += query(L,R, rson);
    pushup(u);
    return sum;
}
 
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    build(1,n);
    char op[2];
    int l,r,x;
    while(m--)
    {
        cin >> op >> l >> r;
        if(op[0] == 'Q')
        {
            cout << query(l,r) << endl;
        }
        else {
            cin >> x;
            update(l,r,x);
        }
    }
    return 0;
}