形式化题目

给定长度为 $N$ 的整数数列 $A_1, A_2, \ldots, A_N$，依次处理 $M$ 条指令：

• C l r d：令 $A_l, A_{l+1}, \ldots, A_r$ 每个数都加上 $d$；
• Q：输出某个区间当前的元素之和。

所有询问按输入顺序逐行输出答案。约束为 $1 \leqslant N, M \leqslant 10^5$， $|d| \leqslant 10^4$，$|A_i| \leqslant 10^9$。

以题面样例为例（此样例用的是 Q X 单点版本）：

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

样例输出为 4 1 2 5：前三条 Q 时还没发生过任何修改，所以答案就是原数列的 $A_4 = 4$、$A_1 = 1$、$A_2 = 2$；C 1 6 3 把前三项之外的前 $6$ 项各加 $3$， 于是最后一条 Q 2 读到的是 $2 + 3 = 5$。注意这次修改没有碰到 $A_7$， 它仍然是 $7$——「只影响区间内的数」正是下面推导的出发点。

正解

思路

1. 朴素做法与它的瓶颈

最直接的写法是维护原数组 $A$：

• C l r d：for i in range(l, r+1): A[i] += d，$O(N)$；
• Q X：直接读 A[X]，$O(1)$。

这个写法的问题是一次区间加要逐个改到区间里的每个元素。 $M$ 次操作最坏 $O(NM) = 10^{10}$，必然超时。

还有另一种朴素写法：维护差分数组 $d_i = A_i - A_{i-1}$（约定 $A_0 = 0$）， 于是区间加变成 $d_l$ 与 $d_{r+1}$ 两个位置的变化，$O(1)$； 但求值 $A_x = d_1 + \cdots + d_x$ 要线性累加，$O(N)$。

两种写法各留下一个 $O(N)$ 的环节。真正的问题是：相邻两次操作之间，绝大多数位置根本没变， 却每次都被重新扫了一遍。 所以需要一个结构，让「改一个点」和「求前缀和」都不用线性扫描。

2. 关键观察：区间加在差分上只动两个位置

对 $A_l, \ldots, A_r$ 统一加 $v$：

• $l \leqslant i \leqslant r$ 时，$A_i$ 与 $A_{i-1}$ 同时加 $v$，故 $d_i$ 不变；
• 只有跨越区间边界的两个位置变化：$d_l \mathrel{+}= v$，$d_{r+1} \mathrel{-}= v$。

而单点求值恰好是差分的前缀和：

于是「区间加 + 单点求值」被翻译成「单点改 + 前缀和」， 这正是树状数组最擅长的操作组合，两者都是 $O(\log N)$。

下面用题面样例把这条观察走一遍。表中加粗的是本次被改动的位置：

观察 C 1 6 3 那一行：$d$ 只在 $d_1$ 和 $d_7$ 两处变化（加粗）， 说明一次区间加真正改动的差分位置恒为 2 个（一般地就是 $d_l$ 与 $d_{r+1}$）。 再看两个 Q 行与它们的输出：$A_4 = d_1 + \cdots + d_4 = 1+1+1+1 = 4$， 而在 C 1 6 3 之后 $A_2 = 4 + 1 = 5$，都正好是差分的前缀和。 「改区间」已被翻译成「改两个点」，剩下的问题只有一个：如何快速求差分的前缀和。

3. 树状数组维护「单点改 + 前缀和」

树状数组的结点 $i$ 管辖区间 $[i - \operatorname{lowbit}(i) + 1,\, i]$， 其中 $\operatorname{lowbit}(i) = i \,\&\, (-i)$ 是 $i$ 的最低非零二进制位：

• 单点加：沿 $i \mathrel{+}= \operatorname{lowbit}(i)$ 上溯，更新所有覆盖该位置的结点；
• 前缀和：沿 $i \mathrel{-}= \operatorname{lowbit}(i)$ 下跳，累加沿途结点。

下表以 $n = 8$ 为例，列出每个结点的管辖范围，并标出「修改 $d_5$」（即一次区间加的端点落在 $5$ 处）与「求前缀和 $S(7)$」各自会访问哪些结点：

先看覆盖区间一列：结点管辖的长度按 $\operatorname{lowbit}$ 成倍增长， 所以任一位置最多被 $\log_2 n$ 个结点覆盖，修改 $d_5$ 只需更新 3 个结点。 再看角色一列：前缀和 $S(7)$ 只需累加 3 个结点， 它们负责的区间恰好不重不漏地拼成 $A_1 \cdots A_7$。 两个循环都只跑 $O(\log n)$ 步，这就是把线性扫描换成树状数组的全部收益。

4. 评测数据要区间和：再展开一层前缀和

数据实际要求 $\sum_{i=l}^{r} A_i = S(r) - S(l-1)$，其中 $S(x) = \sum_{i \le x} A_i$。 把 $A_i = \sum_{j \le i} d_j$ 代进去并交换求和次序：

（等号后的直观解释：每个 $d_j$ 在 $i = j, j+1, \ldots, x$ 中共被计入 $x - j + 1$ 次。）

右边是两个前缀和，各自都能用一棵树状数组维护：

• bit1 维护 $d_j$；
• bit2 维护 $j \cdot d_j$。

一次区间加要同步改两棵树（共 4 次单点加）：

一次区间和查询要 4 次前缀和：$\big[S(r)\big] - \big[S(l-1)\big]$， 其中每个 $S(x) = (x+1) \cdot \texttt{bit1.sum}(x) - \texttt{bit2.sum}(x)$。

5. 初始化与两个实现细节

初始化：由 $A$ 反推 $d_i = A_i - A_{i-1}$，对每个 $i$ 执行 bit1.add(i, d_i) 与 bit2.add(i, d_i * i)，共 $O(N \log N)$。

首次实现时一个容易忽略的边界：当 $r = N$ 时不能再去改 $d_{N+1}$。 差分序列到 $d_N$ 就结束了，$d_{N+1} = A_{N+1} - A_N$ 没有意义。 代码用 if r < n: 拦住，否则会写到序列之外并污染后续查询。

第二个细节是让单点 Q X 与区间 Q l r 共用同一条查询路径。 因为 $\sum_{i=x}^{x} A_i = A_x$，单点询问就是退化区间 $[x, x]$； 两种输入的区别只是 Q 行少了一个操作数， 所以按行切分后判断操作数个数即可：right = int(parts[2]) if len(parts) > 2 else left。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 区间加 + 区间和：两个树状数组维护差分序列 d[i] 与 i·d[i]。
#include <cstdio>
#include <string>
#include <sstream>
#include <iostream>
#include <vector>

typedef long long ll;

const ll MAXN = 100005;

ll n, m;
ll bit1[MAXN]; // 差分数组 d 的树状数组
ll bit2[MAXN]; // i·d[i] 的树状数组

// 在下标 i 处加 delta：沿 i += i & -i 上溯
void bit_add(ll* bit, ll i, ll delta) {
    while (i <= n) {
        bit[i] += delta;
        i += i & -i;
    }
}

// 求 bit 维护序列的前 i 项和
ll bit_sum(ll* bit, ll i) {
    ll total = 0;
    while (i > 0) {
        total += bit[i];
        i -= i & -i;
    }
    return total;
}

// 把 [l, r] 整体加 delta：差分序列上只需改 d[l] 和 d[r+1] 两个位置
void range_add(ll l, ll r, ll delta) {
    bit_add(bit1, l, delta);
    bit_add(bit2, l, delta * l);
    if (r < n) { // r = n 时 d[n+1] 落在序列之外，不记录
        bit_add(bit1, r + 1, -delta);
        bit_add(bit2, r + 1, -delta * (r + 1));
    }
}

// Σ_{i≤x} A[i] = (x+1)·Σ d[j] - Σ j·d[j]
ll prefix_sum(ll x) {
    return (x + 1) * bit_sum(bit1, x) - bit_sum(bit2, x);
}

int main() {
    std::string line;
    // 第一行：n m（跳过空行）
    while (std::getline(std::cin, line)) {
        std::istringstream iss(line);
        if (iss >> n >> m) {
            break;
        }
    }

    // 数列可能被折成多行，读满 n 个数为止
    std::vector<ll> values;
    while ((ll)values.size() < n && std::getline(std::cin, line)) {
        std::istringstream iss(line);
        ll v;
        while (iss >> v) {
            values.push_back(v);
        }
    }

    ll prev = 0; // 前一个数，用来就地算差分 d[i] = A[i] - A[i-1]
    for (ll i = 1; i <= n; i++) {
        ll diff = values[i - 1] - prev;
        prev = values[i - 1];
        bit_add(bit1, i, diff);
        bit_add(bit2, i, diff * i);
    }

    std::vector<std::string> out;
    for (ll q = 0; q < m; q++) {
        if (!std::getline(std::cin, line)) {
            break;
        }
        std::istringstream iss(line);
        std::string op;
        ll parts[8];
        ll cnt = 0;
        if (!(iss >> op)) {
            q--; // 空行不算一条指令
            continue;
        }
        while (cnt < 8 && iss >> parts[cnt]) {
            cnt++;
        }
        ll left = parts[0];
        if (op == "C") {
            ll right = parts[1], delta = parts[2];
            range_add(left, right, delta);
        } else { // 单点询问少一个操作数，取 right = left
            ll right = (cnt > 1) ? parts[1] : left;
            std::ostringstream oss;
            oss << (prefix_sum(right) - prefix_sum(left - 1));
            out.push_back(oss.str());
        }
    }

    for (size_t i = 0; i < out.size(); i++) {
        printf("%s\n", out[i].c_str());
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 17:40
# update_at: 2026-10-01 17:54

import sys
from collections.abc import Iterator

ADD = b"C"  # 区间加指令 C l r d；询问指令是 "Q"，题面写 "Q X"（单点值），评测数据写 "Q l r"（区间和）


def bit_add(bit: list[int], i: int, delta: int, limit: int) -> None:
    """在下标 i 处加 delta：沿 i += i & -i 上溯，更新所有覆盖 i 的结点。"""
    while i <= limit:
        bit[i] += delta
        i += i & -i


def bit_sum(bit: list[int], i: int) -> int:
    """求 bit 维护序列的前 i 项和：沿 i -= i & -i 下跳，把沿途结点累加。"""
    total = 0
    while i > 0:
        total += bit[i]
        i -= i & -i
    return total


def range_add(bit1: list[int], bit2: list[int], n: int, l: int, r: int, delta: int) -> None:
    """把 [l, r] 整体加 delta：差分序列上只需改 d[l] 和 d[r+1] 两个位置。

    bit1 维护 d[i]，bit2 维护 i·d[i]。r = n 时 d[n+1] 落在序列之外，
    差分本来到这里就结束了，不必也不能记录。
    """
    bit_add(bit1, l, delta, n)
    bit_add(bit2, l, delta * l, n)
    if r < n:
        bit_add(bit1, r + 1, -delta, n)
        bit_add(bit2, r + 1, -delta * (r + 1), n)


def prefix_sum(bit1: list[int], bit2: list[int], x: int) -> int:
    """求 A[1..x] 的和。

    交换求和次序：Σ_{i≤x} A[i] = Σ_{i≤x} Σ_{j≤i} d[j] = Σ_{j≤x} d[j]·(x-j+1)
    = (x+1)·Σ d[j] - Σ j·d[j]；两个和式分别由 bit1、bit2 查询得到。
    """
    return (x + 1) * bit_sum(bit1, x) - bit_sum(bit2, x)


def solve() -> None:
    stdin = sys.stdin.buffer
    # 按行切分并滤掉空行：bytes.split 无参切分与 line.split() 等价，用 map 只需切一次。
    lines: Iterator[list[bytes]] = (parts for parts in map(bytes.split, stdin) if parts)

    n, m = map(int, next(lines))

    bit1 = [0] * (n + 2)  # 差分数组 d 的树状数组
    bit2 = [0] * (n + 2)  # i·d[i] 的树状数组

    values: list[int] = []
    while len(values) < n:  # 数列可能被折成多行，读满 n 个数为止
        values += map(int, next(lines))

    prev = 0  # 前一个数，用来就地算差分 d[i] = A[i] - A[i-1]（A[0] 视作 0）
    for i, value in enumerate(values, 1):
        diff = value - prev
        prev = value
        bit_add(bit1, i, diff, n)
        bit_add(bit2, i, diff * i, n)

    out: list[str] = []
    for _ in range(m):
        parts = next(lines)
        op, left = parts[0], int(parts[1])
        if op == ADD:
            right, delta = int(parts[2]), int(parts[3])
            range_add(bit1, bit2, n, left, right, delta)
        else:  # 单点询问少一个操作数，取 right = left 就退化成区间和 [x, x]
            right = int(parts[2]) if len(parts) > 2 else left
            out.append(str(prefix_sum(bit1, bit2, right) - prefix_sum(bit1, bit2, left - 1)))

    sys.stdout.write('\n'.join(out) + '\n' if out else '')


if __name__ == "__main__":
    solve()

结构与上面的推导一一对应：

• bit_add / bit_sum 是树状数组的两个基本操作，对应第 3 步的一上溯、一下跳；
• range_add 是第 2 步的落地，其中 if r < n: 处理「$r = N$ 不改 $d_{N+1}$」；
• prefix_sum 是第 4 步的公式，(x + 1) * bit_sum(bit1, x) - bit_sum(bit2, x) 一眼对应 $S(x) = (x+1)\sum d_j - \sum j\,d_j$；
• solve 里的 prev 记录 $A_{i-1}$，就地算出差分完成初始化； 指令分流处的 len(parts) > 2 处理两种询问格式。

复杂度

• 时间复杂度：初始化 $O(N \log N)$，单次区间加或区间和查询均为 $O(\log N)$， 总计 $O\big((N + M) \log N\big)$。 取 $N = M = 10^5$ 约 $3.4 \times 10^6$ 次内层循环，实测最慢用例 0.38 s （限制 1000 ms）。对比朴素做法 $O(NM) = 10^{10}$，差了约 3000 倍。
• 空间复杂度：两棵长度 $N + 2$ 的树状数组，加读入的数列与答案列表，共 $O(N + M)$。 实测峰值 34 MB（限制 128 MB）。
• 数值范围：区间和最大约 $2 \times 10^{14}$，Python 整数无溢出； 若用 C++ 实现，bit1、bit2 与答案都必须用 long long。

总结

• 朴素做法的瓶颈是「一次区间加要逐个改元素」；而整个区间加的是同一个 $d$， 改动本身高度局部，应当换个角度记录它。
• 关键观察一：差分把区间加压缩成 $d_l \mathrel{+}= v$、$d_{r+1} \mathrel{-}= v$ 两个点； 同时把单点求值变成差分的前缀和。
• 关键观察二：树状数组让「单点改 + 前缀和」都变成 $O(\log N)$， 正好匹配观察一留下的操作组合。
• 区间和的推广：展开 $S(x)$ 得 $(x+1)\sum d_j - \sum j\,d_j$， 用两棵树状数组分别维护 $d_j$ 与 $j \cdot d_j$，即「区间加 + 区间求和」的标准双 BIT 模型。
• 边界：$r = N$ 时不改 $d_{N+1}$；Q X 是 Q l r 在 $l = r$ 时的退化情形。
• 复杂度 $O\big((N+M)\log N\big)$ 时间、$O(N + M)$ 空间。

图示解析

这张图串起本题从建模到得到答案的主线：

1
2
3
4
5
6
7
8
9
10区间加 + 单点求值 (Q X)
`- 定义差分 d_i = A_i - A_(i-1)
   |- 区间加 A_l..A_r += v  等价于  d_l += v, d_(r+1) -= v   (只有 2 个点)
   `- 单点求值 A_x           等价于  d_1 + ... + d_x        (前缀和)
      `- 点修改 + 前缀和 -> 树状数组, O(log N)

评测数据实际要求区间求和 (Q l r)
`- 再展开一层: S(x) = (x+1)·Σd_j - Σj·d_j
   `- 两个前缀和 -> 两棵树状数组 bit1 维护 d, bit2 维护 i·d_i
      `- 答案 = S(r) - S(l-1), 单点询问是 l = r 的退化区间

先看第一段分支：它把「整段加」换成「两个点加」，把「取一个数」换成「求前缀和」， 这一步消掉了朴素解法的 $O(N)$ 瓶颈，代价只是换了一个角度看同一个数组。 再看第二段：评测数据要区间和，于是把前缀和再套一层， 同一个恒等式给出用两棵树分别维护 $d_j$ 与 $j \cdot d_j$ 的方案—— 这正是双树状数组维护区间加的由来，而不是背下来的模板。