<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

给定一个长度为 $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

思路

这道题是非常经典的线段树问题。
不会线段树的请左转线段树详解

代码

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n,m;
int a[N];
struct segment_tree {
    int l,r;
    LL sum,tag;
}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) {
    auto &root = tr[u],&left = tr[u << 1],&right = tr[u << 1 | 1];
    if (root.tag) {
        left.tag += root.tag,left.sum += (LL)(left.r - left.l + 1) * root.tag;
        right.tag += root.tag,right.sum += (LL)(right.r - right.l + 1) * root.tag;
        root.tag = 0;
    }
}
void build (int u,int l,int r) {
    if (l == r) {
        tr[u] = {l,r,a[l],0};
        return ;
    }
    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].tag += d;
        return ;
    }
    push_down (u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify (u << 1,l,r,d);
    if (r >= mid + 1) modify (u << 1 | 1,l,r,d);
    push_up (u);
}
LL query_sum (int u,int l,int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    push_down (u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL sum = 0;
    if (l <= mid) sum += query_sum (u << 1,l,r);
    if (r >= mid + 1) sum += query_sum (u << 1 | 1,l,r);
    return sum;
}
int main () {
    scanf ("%d%d",&n,&m);
    for (int i = 1;i <= n;i++) scanf ("%d",&a[i]);
    build (1,1,n);
    while (m--) {
        char op;
        int l,r;
        cin >> op >> l >> r;
        if (op == 'C') {
            int d;
            cin >> d;
            modify (1,l,r,d);
        }
        else printf ("%lld\n",query_sum (1,l,r));
    }
    return 0;
}