「一本通 4.3 例 1」区间和

题目描述

给定长度为 $n$ 的数列与 $m$ 个操作，操作分两类：k=1 a b 表示把 $a$ 处数字加上 $b$ ；k=2 a b 表示询问区间 $[a,b]$ 内所有数的和。输入第一行是 $n, m$ （ $n \le 100000$ ， $m \le 500000$ ），第二行 $n$ 个整数为数列初值，随后 $m$ 行每行三个正整数 $k, a, b$ （ $1 \le a \le b \le n$ ）。对每个询问输出对应答案。例如初值 1 2 3 4，依次执行 1 3 10、2 1 3、2 2 4，输出为 16、19。

思路

单点加 + 区间和用树状数组： $tree[i]$ 管辖 $(i-\mathrm{lowbit}(i), i]$ ，查询沿 $i \mathrel{-}= \mathrm{lowbit}(i)$ 把前缀拆成 $O(\log n)$ 段、修改沿 $i \mathrel{+}= \mathrm{lowbit}(i)$ 上跳更新，区间和即两次前缀和相减；建树按 $i=1..n$ 正序把段和推给父结点 $i+\mathrm{lowbit}(i)$ ，一趟 $O(n)$ 完成。真实数据 $n, m$ 可达 $10^6$ ，区间和会超 int，须用 ll。

参考代码

Python 版：

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#!/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-09-30 17:55
# update_at: 2026-09-30 17:55

import sys

ADD = 1     # 操作码：在 a 处累加 b
QUERY = 2   # 操作码：询问闭区间 [a, b] 的和


def build_bit(values: list[int]) -> list[int]:
    """用初始数组直接建树状数组：tree[i] 管辖 (i - lowbit(i), i] 这一段的和。

    从小到大把每个点的贡献推给它的父亲 i + lowbit(i)，一趟 O(n) 建完，不必 n 次插入。
    """
    size = len(values)
    tree = values[:]                              # 下标 1..n，tree[0] 留作占位
    for i in range(1, size):
        parent = i + (i & -i)
        if parent < size:
            tree[parent] += tree[i]
    return tree


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

    tree = build_bit([0] + [next(data) for _ in range(n)])  # 补一个下标 0 占位

    out: list[str] = []
    for _ in range(m):
        k, a, b = next(data), next(data), next(data)
        if k == QUERY:
            # 前缀和之差：先向后跳着消掉低位，累出 [1, b] 与 [1, a-1] 的和
            total = 0
            i = b
            while i > 0:
                total += tree[i]
                i -= i & -i
            i = a - 1
            while i > 0:
                total -= tree[i]
                i -= i & -i
            out.append(str(total))
        else:
            # 单点累加：沿 i += lowbit(i) 把增量加到所有管辖 a 的位置上
            i = a
            while i <= n:
                tree[i] += b
                i += i & -i

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


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-06 00:49
 * update_at: 2026-10-06 00:49
 */

// main.cpp：单点加 + 区间和，树状数组（Fenwick）模板题。
// tree[i] 管辖 (i - lowbit(i), i] 这一段的和。

#include <cstdio>

typedef long long ll;

const int MAXN = 1000005; // 真实数据 n 最大 1e6，比题面写的 1e5 大，按大的开

ll tree[MAXN]; // 树状数组，tree[i] = sum of (i - lowbit(i), i]
ll val[MAXN];  // 数列初值，val[i] 表示第 i 个数的初值
ll n, m;       // 数列长度、操作数

// 求前缀和 S(i) = a[1] + ... + a[i]，沿 i -= lowbit(i) 拆成 O(log n) 段
ll query_prefix(ll i) {
    ll sum = 0;
    while (i > 0) {
        sum += tree[i];
        i -= i & (-i);
    }
    return sum;
}

// 单点加：a[pos] += delta，沿 pos += lowbit(pos) 更新所有管辖 pos 的段
void update(ll pos, ll delta) {
    for (; pos <= n; pos += pos & (-pos))
        tree[pos] += delta;
}

int main() {
    scanf("%lld %lld", &n, &m);

    // 读入初值
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &val[i]);

    // O(n) 建树：正序把 tree[i] 的完整段和推给父结点 i + lowbit(i)
    for (ll i = 1; i <= n; i++) {
        tree[i] += val[i];
        ll parent = i + (i & (-i));
        if (parent <= n)
            tree[parent] += tree[i];
    }

    // 处理 m 个操作：真实数据 k=1 单点加、k=2 区间求和
    for (ll t = 1; t <= m; t++) {
        ll k, a, b;
        scanf("%lld %lld %lld", &k, &a, &b);
        if (k == 1) {
            update(a, b); // 在 a 处累加 b
        } else {
            // 区间和 = 两次前缀和相减
            ll ans = query_prefix(b) - query_prefix(a - 1);
            printf("%lld\n", ans);
        }
    }
    return 0;
}