「一本通 4.1 例 1」数列操作

题目描述

给定长度为 $n$ 的序列与 $m$ 个操作，每个操作给出 $k,a,b$ ： $k=1$ 时把第 $a$ 个数加 $b$ ；否则求子数列 $[a,b]$ 的连续和并输出。数据范围 $n,m\leqslant10^6$ 。

思路

树状数组维护前缀和：单点修改沿 $i+\mathrm{lowbit}(i)$ 向上更新，区间查询沿 $i-\mathrm{lowbit}(i)$ 向下拆段，两次前缀和相减得区间和。注意真实数据中查询操作码为 $2$ ，代码判据写成 $k=1$ 为加法、其余为查询即可兼容样例与真实数据。

参考代码

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

import sys
from itertools import accumulate


def prefix_sum(bit: list[int], i: int) -> int:
    """前缀和：累加 bit 中管辖 [1..i] 的 O(log n) 个结点。"""
    s = 0
    while i:
        s += bit[i]
        i -= i & -i  # lowbit：去掉最低位的 1，沿父链上跳
    return s


def add(bit: list[int], i: int, delta: int) -> None:
    """单点加：把 delta 累加到第 i 个元素，并更新所有管辖 i 的结点。"""
    while i < len(bit):
        bit[i] += delta
        i += i & -i  # lowbit：跳到把本段纳入区间的上层结点


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    values = [next(data) for _ in range(n)]

    # 树状数组建树：pre 是前缀和，bit[i] 恰为 (i-lowbit(i), i] 的区间和，一次推导式 O(n) 建好
    pre = list(accumulate(values, initial=0))
    bit = [0] + [pre[i] - pre[i - (i & -i)] for i in range(1, n + 1)]

    out: list[str] = []
    for _ in range(m):
        k, a, b = next(data), next(data), next(data)
        if k == 1:  # k=1：第 a 个数加 b
            add(bit, a, b)
        else:  # 其余 k 都是求子数列 [a,b] 的连续和（样例 k=0，真实数据 k=2）
            out.append(str(prefix_sum(bit, b) - prefix_sum(bit, a - 1)))
    print('\n'.join(out))


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/**
 * 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:35
 * update_at: 2026-10-06 00:35
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1000005; // 真实数据 n 最大到 1e6

int n, m;
ll bit[MAXN]; // bit[i] 存区间 (i - lowbit(i), i] 的元素和

// 返回 x 的最低位 1 代表的值
inline int lowbit(int x) {
    return x & (-x);
}

// 在位置 i 加上 v
void add(int i, ll v) {
    for (; i <= n; i += lowbit(i))
        bit[i] += v;
}

// 求前缀和 [1, i]
ll query(int i) {
    ll res = 0;
    for (; i > 0; i -= lowbit(i))
        res += bit[i];
    return res;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        ll x;
        cin >> x;
        add(i, x); // 树状数组单点插入建树
    }

    for (int i = 1; i <= m; ++i) {
        int k, a, b;
        cin >> k >> a >> b;
        if (k == 1) {
            add(a, b); // 单点加
        } else {
            cout << query(b) - query(a - 1) << '\n'; // 区间求和
        }
    }
    return 0;
}

「一本通 4.1 例 1」数列操作

目录

题目描述

思路

参考代码