宣传一下 算法提高课整理

CSDN个人主页：更好的阅读体验

原题链接

题目描述

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

1. C l r d，表示把 $A_l,A_{l+1},…,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

思路

懒标记

基本思想

当进行区间修改时，只修改当前区间，而它的子节点的修改先欠着，等用到了子节点的时候再往下传。

应用

将懒标记下传的操作：pushdown 函数

如果这个节点有懒标记，就把懒标记加到子节点的懒标记中，并把当前节点的懒标记清空。

代码：

void pushdown(LL u)
{
    Segment_Tree_Node &U = tr[u], &L = tr[u << 1], &R = tr[u << 1 | 1];
    if (tr[u].lazy) // 如果当前节点有懒标记
    {
        L.lazy += U.lazy, L.sum += (L.r - L.l + 1) * U.lazy; // 左儿子懒标记和区间和
        R.lazy += U.lazy, R.sum += (R.r - R.l + 1) * U.lazy; // 右儿子懒标记和区间和
        U.lazy = 0; // 清空当前节点懒标记
        // 显然，区间和在加的时候应该加上懒标记和区间长度的乘积
    }
}

区间修改

这里和 pushdown 差不多，修改懒标记和区间和。

代码：

void modify(LL u, LL l, LL r, LL d)
{
    if (tr[u].l >= l && tr[u].r <= r) // 如果这个区间被完全包含
    {
        tr[u].lazy += d; // 修改懒标记 
        tr[u].sum += (tr[u].r - tr[u].l + 1) * d; // 区间和 + d * 区间长度
    }
    else
    {
        pushdown(u);
        LL 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);
        pushup(u);
    }
}

算法时间复杂度 $O(n \log n)$

AC Code

$\text{C}++$

#include <iostream>

using namespace std;

typedef long long LL;

const LL N = 100010;

struct S_Tree
{
    LL l, r;
    LL sum, lazy;
}tr[N * 4];

LL n, m;
LL a[N];

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

void pushdown(LL u)
{
    S_Tree &U = tr[u], &L = tr[u << 1], &R = tr[u << 1 | 1];
    if (tr[u].lazy)
    {
        L.lazy += U.lazy, L.sum += (L.r - L.l + 1) * U.lazy;
        R.lazy += U.lazy, R.sum += (R.r - R.l + 1) * U.lazy;
        U.lazy = 0;
    }
}

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

void modify(LL u, LL l, LL r, LL d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].lazy += d;
        tr[u].sum += (tr[u].r - tr[u].l + 1) * d;
    }
    else
    {
        pushdown(u);
        LL 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);
        pushup(u);
    }
}

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

int main()
{
    scanf("%lld%lld", &n, &m);
    for (LL i = 1; i <= n; i ++ )
        scanf("%lld", &a[i]);

    build(1, 1, n);

    LL op, l, r, d;
    while (m -- )
    {
        scanf("%lld%lld%lld", &op, &l, &r);
        if (op == 1)
        {
            scanf("%lld", &d);
            modify(1, l, r, d);
        }
        else
        {
            LL t = query(1, l, r);
            printf("%lld\n", t);
        }
    }

    return 0;
}

最后，如果觉得对您有帮助的话，点个赞再走吧！