树状数组-区间修改-区间查询

形式化题目

给定一个长度为 $n$ 的数组 $a_1, a_2, \ldots, a_n$ ，要求支持以下两种操作，共 $m$ 次：

区间修改：给定 $x, y, z$ ，对所有 $i \in [x, y]$ ，将 $a_i$ 加上 $z$ 。
区间查询：给定 $x, y$ ，求 $\sum_{i=x}^y a_i$ 并输出。

数据范围： $1 \le n \le 10^5$ ， $-1000 \le a_i, z \le 1000$ 。由于数组和可能较大，答案需要使用 64 位整数（long long）。

正解

思路

如果直接在原数组上进行操作，无论是修改还是查询，单次最坏的时间复杂度均为 $O(n)$ 。在 $n, m \le 10^5$ 的数据范围内会超时。

引入差分数组 $d_i = a_i - a_{i-1}$ ，其中 $a_0 = 0$ 。则原数组中的元素 $a_i$ 可以表示为：

a_i = \sum_{j=1}^i d_j

此时，区间修改操作“对

a[x \dots y]

加上

z

”可以直接转化为对差分数组的两个单点修改：

d_x \gets d_x + z

d_{y+1} \gets d_{y+1} - z

进而考虑区间查询操作，我们需要求前缀和 $S_x = \sum_{i=1}^x a_i$ ：

\begin{aligned} S_x &= \sum_{i=1}^x a_i = \sum_{i=1}^x \sum_{j=1}^i d_j \\ &= d_1 \times x + d_2 \times (x-1) + \dots + d_x \times 1 \\ &= \sum_{i=1}^x d_i \times (x - i + 1) \\ &= (x + 1) \sum_{i=1}^x d_i - \sum_{i=1}^x i \cdot d_i \end{aligned}

从上式可知，只需要使用两个树状数组，分别维护：

bit_diff 维护 $d_i$ 的前缀和；
bit_weighted 维护 $i \cdot d_i$ 的前缀和。

每次更新 $d_i$ 时，同步在这两个树状数组上做单点修改，注意权值树状数组在增加时乘以的系数是原始下标 $i$ 。区间求和 $\sum_{i=x}^y a_i$ 即为 $S_y - S_{x-1}$ 。这使得两种操作均能降至 $O(\log n)$ 。

代码

python

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#!/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-08 10:37
# update_at: 2026-10-08 11:02

# 区间加 + 区间求和。记差分 d_i = a_i - a_{i-1}（a_0 = 0），则
#   [x,y] 加 z  <=>  d_x += z、d_{y+1} -= z
#   前缀和 S_x = Σ a_i = Σ d_i·(x-i+1) = (x+1)·Σd_i - Σ i·d_i
# 于是用两棵树状数组分别维护 d_i 与 i·d_i，两种操作都降到 O(log n)。

import sys


def point_add(tree_d: list[int], tree_w: list[int], size: int, idx: int, val: int) -> None:
    """在差分下标 idx 处加 val：两棵树同步向上跳，权值树存 i·d_i。"""
    weighted = val * idx  # 权重是「原始下标」，不是树上的节点编号，别写成 val * i
    i = idx
    while i <= size:
        tree_d[i] += val
        tree_w[i] += weighted
        i += i & -i


def prefix_sum(tree_d: list[int], tree_w: list[int], idx: int) -> int:
    """下标 1..idx 的元素和 S_idx = (idx+1)·Σd_i - Σ i·d_i。"""
    sum_d = sum_w = 0
    i = idx
    while i > 0:
        sum_d += tree_d[i]
        sum_w += tree_w[i]
        i -= i & -i
    return (idx + 1) * sum_d - sum_w


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    tree_d = [0] * (n + 2)
    tree_w = [0] * (n + 2)

    # 边读入原数组边转成差分：d_i = a_i - a_{i-1}，a_0 视为 0
    last = 0
    for i in range(1, n + 1):
        a = next(data)
        point_add(tree_d, tree_w, n, i, a - last)
        last = a

    out: list[str] = []
    for _ in range(m):
        op = next(data)
        x, y = next(data), next(data)
        if op == 1:
            z = next(data)
            point_add(tree_d, tree_w, n, x, z)
            point_add(tree_d, tree_w, n, y + 1, -z)  # y+1 越界时 while 不执行，相当于只改 d_x
        else:
            out.append(str(prefix_sum(tree_d, tree_w, y) - prefix_sum(tree_d, tree_w, x - 1)))

    if out:
        print('\n'.join(out))


if __name__ == "__main__":
    solve()

cpp

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/**
 * 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-08 10:57
 * update_at: 2026-10-08 10:57
 */
// main.cpp：区间加 + 区间求和，用「差分 + 双树状数组」在 O(log n) 内完成两种操作。
//
// 记差分 d_i = a_i - a_{i-1}（a_0 = 0）。区间加 [x,y] 加 z 变成两个单点修改：
// d_x += z、d_{y+1} -= z；区间查询则要把前缀和用差分表示：
//   S_x = Σ_{i=1}^{x} a_i = Σ_{i=1}^{x} d_i·(x-i+1) = (x+1)·Σ d_i - Σ i·d_i
// 所以只要两棵树状数组分别维护 d_i 与 i·d_i，即可 O(log n) 求任意前缀和。

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 100005; // 题目 n <= 1e5

int n, m;
ll bit_diff[MAXN];     // 树状数组一：维护差分 d_i
ll bit_weighted[MAXN]; // 树状数组二：维护 i·d_i

// 在差分 d 的下标 idx 处加 val：两棵树同时向上更新，权值树要带上 idx 这个系数
void add_point(int idx, ll val) {
    for (int i = idx; i <= n; i += i & -i) {
        bit_diff[i] += val;
        bit_weighted[i] += val * idx;
    }
}

// 前 idx 项的和：S_idx = (idx+1)·Σd_i - Σ i·d_i（两棵树一起向下跳）
ll prefix_sum(int idx) {
    ll sum_d = 0, sum_w = 0;
    for (int i = idx; i > 0; i -= i & -i) {
        sum_d += bit_diff[i];
        sum_w += bit_weighted[i];
    }
    return (idx + 1) * sum_d - sum_w;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    // 边读入原数组边转成差分：a_i - a_{i-1}，a_0 视为 0
    ll last = 0;
    for (int i = 1; i <= n; i++) {
        ll a;
        cin >> a;
        add_point(i, a - last);
        last = a;
    }

    for (int q = 0; q < m; q++) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            ll z;
            cin >> z;
            add_point(x, z);
            add_point(y + 1, -z); // y+1 超过 n 时循环条件直接跳过，相当于不加
        } else {
            cout << prefix_sum(y) - prefix_sum(x - 1) << '\n';
        }
    }

    return 0;
}

复杂度

时间复杂度：无论是区间修改还是区间查询，只需要在树状数组上单次向上或向下跳跃，单次操作时间复杂度为 $O(\log n)$ 。总时间复杂度为 $O(n \log n + m \log n)$ 。
空间复杂度：需要维护两个长度为 $n+2$ 的树状数组（或全局数组），空间复杂度为 $O(n)$ 。

总结

为何使用差分与双树状数组：这题由于既有区间加法操作，又有区间求和查询。普通的单个树状数组只能做到单点修改+区间求和，或者结合差分做到区间修改+单点查询。为了实现“区间修改+区间求和”，必须将前缀和表达式用差分数组展开，推导出需要维护的 $\sum d_i$ 以及 $\sum i \cdot d_i$ 。
权值系数必须是原始下标：在给第二个树状数组（维护 $i \cdot d_i$ ）加值的时候，增加的具体数值应为 val * idx（其中 idx 为操作的原始目标下标），而不是树状数组向后跳跃更新时的节点下标 i。
需要用 long long 的必要性：树状数组维护的累加和尤其是 $i \cdot d_i$ 很容易超过 32 位带符号整型（int）的范围。为了防止溢出，求和变量以及参数等处都需要使用 long long（Python 自带大整数，C++ 则需注意类型定义）。
关于原题描述与测试数据：
- 题面中的原输出格式描述（“全部过河的最少耗时”）是从别处复制遗留的错误，需要通过样例推断真实意图。
- 本题 data/ 测试数据原先由带有 scanf("%d%d%d") 错误格式符读取 long long 的标程生成，导致“如果第一个操作刚好是区间加，更新会被因垃圾高位值越界而静默丢弃”。该问题已被修复。

树状数组-区间修改-区间查询

目录

形式化题目

正解

思路

代码

复杂度

总结