2. 题意概述

给定一个长度为 n 的数列，需要完成 m 次操作。操作一共有两种：

操作1:单点修改 1 x k  表示：a[x] += k; 也就是把第 x 个数加上 k。

操作2:区间求和 2 x y 表示求区间[x, y]内所有数的和：a[x] + a[x + 1] + ... + a[y]

3. 解题思路

1. 不能直接暴力

普通数组,单点修改很方便：a[x] += k; 只需要改一个位置。查询区间 [x, y] 的和时,就需要从 x 加到 y：一次查询最坏需要 O(n)。本题最多有 5 * 10^5 次操作,时间复杂度会非常高。

2. 普通前缀和也不合适

普通前缀和可以快速查询区间和。设：s[i] = a[1] + a[2] + ... + a[i]那么区间 [x, y] 的和可以写成：s[y] - s[x - 1]查询很快。但是本题有修改操作。如果修改了 a[x]，那么：s[x], s[x + 1], s[x + 2], ..., s[n] 这些前缀和都会受到影响。也就是说：

• 普通数组：修改快,查询慢
• 普通前缀和：查询快,修改慢
• 树状数组：修改和查询都比较快

3. 树状数组

树状数组中的 tree[i] 不是直接存 a[i]。它存的是一段区间的和。例如,当 n = 8 时：

tree[1] 管 [1]tree[2] 管 [1, 2]tree[3] 管 [3]tree[4] 管 [1, 2, 3, 4]tree[5] 管 [5]tree[6] 管 [5, 6]tree[7] 管 [7]tree[8] 管 [1, 2, 3, 4, 5, 6, 7, 8]

也就是说,树状数组提前保存了一些“小区间的和”。查询时,不需要一个一个数相加,只需要拿几个已经算好的区间和拼起来。

4. lowbit 的作用

树状数组的核心函数是：

int lowbit(int x) {    return x & -x;}

lowbit(x) 的作用是：找到 x 的二进制中最低位的 1 所代表的值。例如：

lowbit(1) = 1lowbit(2) = 2lowbit(3) = 1lowbit(4) = 4lowbit(6) = 2lowbit(8) = 8

在树状数组中：lowbit(i) 决定了：tree[i] 管几个数。比如：lowbit(6) = 2说明：tree[6] 管 2 个数,也就是 [5, 6]。比如：lowbit(8) = 8说明：tree[8] 管 8 个数,也就是 [1, 8]

5. 单点修改 add 函数

把第 x 个数加上 k,也就是：a[x] += k; 不能只修改 tree[x]。因为 a[x] 可能被多个 tree 节点统计进去。例如修改 a[3],会影响：

tree[3] 管 [3]tree[4] 管 [1, 2, 3, 4]tree[8] 管 [1, 2, 3, 4, 5, 6, 7, 8]

所以这些节点都要加上 k。代码如下：

void add(int x, long long k) {    while (x <= n) {        tree[x] += k;        x += lowbit(x);    }}

tree[x] 管理的区间包含了被修改的位置,所以它的区间和也要加上 k。x += lowbit(x); 表示跳到下一个也会受到影响的位置。例如执行：add(3, k); 更新路线是：3 -> 4 -> 8 -> ... 也就是：

tree[3] += k;tree[4] += k;tree[8] += k;

直到超过 n 为止。这里的核心是：修改一个点时,要向后更新所有包含这个点的区间。

6. 前缀和查询 query 函数

树状数组先求前缀和。也就是：a[1] + a[2] + ... + a[x] 代码如下：

long long query(int x) {    long long sum = 0;    while (x > 0) {        sum += tree[x];        x -= lowbit(x);    }    return sum;}

sum += tree[x]; 表示把当前 tree[x] 管理的这一段区间和加入答案。x -= lowbit(x);表示当前这一段已经统计完了,跳到前面还没有统计的位置继续算。例如查询：query(7);访问路线是：7 -> 6 -> 4 -> 0 对应的区间是：

tree[7] 管 [7]tree[6] 管 [5, 6]tree[4] 管 [1, 2, 3, 4]

这三段合起来正好是：[1, 7] 没有重复,也没有遗漏。

7. 区间和

树状数组的 query(x) 求的是前缀和：query(x) = a[1] + a[2] + ... + a[x] 。题目要求的是区间 [x, y] 的和。可以转化成：query(y) - query(x - 1) 。例如要求 [3, 7] 的和：query(7) = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7],query(2) = a[1] + a[2]。两者相减后,剩下的就是：a[3] + a[4] + a[5] + a[6] + a[7] 所以区间查询代码是：query(y) - query(x - 1)。

4. 完整 AC 代码

#include<bits/stdc++.h>using namespace std;const int MAXN = 500000 + 5;int n, m;long long tree[MAXN];  // 树状数组// lowbit：取出最低位的 1intlowbit(int x){    return x & (-x);}// 单点增加：在位置 x 加上 kvoidadd(int x, longlong k){    while (x <= n) {        tree[x] += k;        x += lowbit(x);  // 跳到下一个受影响的位置    }}// 查询前缀和：1 到 x 的和 longlongquery(int x){    long long res = 0;    while (x > 0) {        res += tree[x];        x -= lowbit(x);  // 往上跳    }    return res;}intmain(){    ios::sync_with_stdio(0);    cin.tie(0);    cin >> n >> m;    // 读入初始数组,并构建树状数组    for (int i = 1; i <= n; i++) {        long long x;  cin >> x;        add(i, x);  // 初始化    }    while (m--) {        int op, x, y; cin >> op >> x >> y;        if (op == 1) add(x, y); // 单点加         else cout << query(y) - query(x - 1) << '\n';// 区间查询     }    return 0;}

点击↓ 阅读原文 可提交代码