树状数组：单点修改与区间查询

代码模板

树状数组的基础模型：用二进制长度的区间块支持单点加与动态区间和查询。

  • 数据结构
  • 树状数组
  • 前缀和
  • 区间查询

学习路线

树状数组的求和主线是：单点修改、区间查询（本篇） → 区间修改、单点查询 → 区间修改、区间查询。前缀最值 是选学分支。

一句话算法

树状数组把前缀拆成少量二进制长度的块，修改和查询都只在这些块之间跳转。

问题模型

给定长度为 nn 的数组 aa，操作会反复交替出现：

  1. 单点修改：a[x] += value；
  2. 区间查询：求 al+al+1+⋯+ara_l+a_{l+1}+\cdots+a_r。

静态前缀和可以 O(1)O(1) 查询区间和，但修改一个位置后，后面的所有前缀和都要更新，单次修改最坏是 O(n)O(n)。

树状数组把两种操作都降到 O(log⁡n)O(\log n)。

核心直觉

每个节点维护哪一段

定义：

cpp 
        
1

        lowbit(x) = x & -x

树状数组节点 tree[i] 维护：

ai−lowbit⁡(i)+1+⋯+ai a_{i-\operatorname{lowbit}(i)+1}+\cdots+a_i

也就是以 ii 为右端点、长度为 lowbit⁡(i)\operatorname{lowbit}(i) 的区间。

例如：

ii lowbit⁡(i)\operatorname{lowbit}(i) tree[i] 维护的区间
3 1 [3,3][3,3]
6 2 [5,6][5,6]
8 8 [1,8][1,8]
12 4 [9,12][9,12]

在 1…81\ldots 8 中，这些区间互相嵌套：

index:   1  2  3  4  5  6  7  8
node 1: [1]
node 2: [1--2]
node 3:       [3]
node 4: [1--------4]
node 5:             [5]
node 6:             [5--6]
node 7:                   [7]
node 8: [1--------------------8]

lowbit 为什么得到块长

-x 使用补码表示。x & -x 会清掉最低位 1 以外的所有位，只留下这个最低位 1 所代表的值。

例如：

 12 = 00001100
-12 = 11110100
 &  = 00000100 = 4

所以 lowbit(12)=4，节点 12 的块长就是 44。

算法步骤

单点修改

修改 a[pos] += value 时，所有覆盖 pos 的块都要增加 value：

cpp 
        
1
2
3

        for (int i = pos; i <= n; i += lowbit(i)) {
    tree[i] += value;
}

例如修改 a[3]，更新路径是：

3 --+1--> 4 --+4--> 8 --+8--> 16（越界停止）

3、4、8 对应的块都覆盖位置 33。每次执行 i += lowbit(i)，都会跳到下一个覆盖原位置的更大块。

前缀查询

查询前缀 a1+⋯+aposa_1+\cdots+a_{pos} 时，每次取走一个以当前位置结尾的完整块：

cpp 
        
1
2
3
4

        answer = 0;
for (int i = pos; i > 0; i -= lowbit(i)) {
    answer += tree[i];
}

例如查询前缀 [1,7][1,7]：

7 --1--> 6 --2--> 4 --4--> 0

[7,7] + [5,6] + [1,4] = [1,7]

这些块互不重叠，刚好拼成整个前缀。

区间查询

区间和仍然使用两个前缀相减：

sum⁡(l,r)=prefix⁡(r)−prefix⁡(l−1) \operatorname{sum}(l,r) =\operatorname{prefix}(r)-\operatorname{prefix}(l-1)

算法证明

核心不变量：tree[i] 始终等于区间

[i−lowbit⁡(i)+1,i] [i-\operatorname{lowbit}(i)+1,i]

内所有元素的和。

  1. 单点修改时，i += lowbit(i) 恰好枚举所有覆盖修改位置的节点，因此所有受影响的块都增加了 value，其他块不变。
  2. 前缀查询时，i -= lowbit(i) 每次取走当前前缀最右侧的完整块。取出的块两两不交，并且最终覆盖整个 [1,pos][1,pos]。
  3. 因为两个前缀和都正确，所以它们相减后得到 [l,r][l,r] 的区间和。

因此修改与查询都保持正确。

复杂度分析

下标每次跳转都会消去或进位一个二进制低位，因此一次循环最多执行 O(log⁡n)O(\log n) 次。

  • 初始化：逐点加入时为 O(nlog⁡n)O(n\log n)；
  • 单点修改：O(log⁡n)O(\log n)；
  • 前缀查询、区间查询：O(log⁡n)O(\log n)；
  • 空间复杂度：O(n)O(n)。

代码模板

下面的模板只保留可复用的 add、prefix_sum 和 range_sum 接口：

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

        #include <bits/stdc++.h>
using namespace std;

// 单点加、前缀和、区间和。
// 下标必须从 1 开始。
template <typename T>
struct Fenwick {
    int n = 0;
    vector<T> tree;

    Fenwick(int n = 0) { init(n); }

    void init(int size) {
        n = size;
        tree.assign(n + 1, 0);
    }

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

    void add(int pos, T value) {
        for (int i = pos; i <= n; i += lowbit(i)) {
            tree[i] += value;
        }
    }

    T prefix_sum(int pos) const {
        T answer = 0;
        for (int i = pos; i > 0; i -= lowbit(i)) {
            answer += tree[i];
        }
        return answer;
    }

    T range_sum(int left, int right) const {
        return prefix_sum(right) - prefix_sum(left - 1);
    }
};
Python

Python 版把同一份接口封装成 Fenwick 类，tree 仍然是从下标 11 开始的 list，位运算与循环边界和 C++ 版逐行对应：

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

        # 单点加、前缀和、区间和。
# 下标必须从 1 开始：lowbit(0) = 0，会让修改循环原地打转。
# Python 的 int 是任意精度，不必像 C++ 那样担心 long long 溢出。


class Fenwick:
    """树状数组：tree[i] 维护 a[i - lowbit(i) + 1 .. i] 的元素和。"""

    n: int
    tree: list[int]

    def __init__(self, size: int = 0) -> None:
        self.init(size)

    def init(self, size: int) -> None:
        """重置为长度 size 的空数组，方便同一个对象换一组数据复用。"""
        self.n = size
        self.tree = [0] * (size + 1)

    @staticmethod
    def lowbit(x: int) -> int:
        """块长：x 二进制最低位那个 1 代表的值，也就是 x & -x。"""
        return x & -x

    def add(self, pos: int, value: int) -> None:
        """单点加：a[pos] += value。所有覆盖 pos 的块都要加上 value。"""
        i = pos
        while i <= self.n:
            self.tree[i] += value
            i += self.lowbit(i)

    def prefix_sum(self, pos: int) -> int:
        """前缀和：a[1] + a[2] + ... + a[pos]，每次取走一个以 i 结尾的完整块。"""
        answer = 0
        i = pos
        while i > 0:
            answer += self.tree[i]
            i -= self.lowbit(i)
        return answer

    def range_sum(self, left: int, right: int) -> int:
        """区间和：a[left] + ... + a[right]，用两个前缀和相减得到。"""
        return self.prefix_sum(right) - self.prefix_sum(left - 1)

完整代码

输入格式与 Luogu P3374 一致：

  • 1 x k：执行 a[x] += k；
  • 2 l r：查询 [l,r][l,r] 的区间和。
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
67

        #include <bits/stdc++.h>
using namespace std;

template <typename T>
struct Fenwick {
    int n = 0;
    vector<T> tree;

    Fenwick(int n = 0) { init(n); }

    void init(int size) {
        n = size;
        tree.assign(n + 1, 0);
    }

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

    void add(int pos, T value) {
        for (int i = pos; i <= n; i += lowbit(i)) {
            tree[i] += value;
        }
    }

    T prefix_sum(int pos) const {
        T answer = 0;
        for (int i = pos; i > 0; i -= lowbit(i)) {
            answer += tree[i];
        }
        return answer;
    }

    T range_sum(int left, int right) const {
        return prefix_sum(right) - prefix_sum(left - 1);
    }
};

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

    int n, m;
    cin >> n >> m;

    Fenwick<long long> bit(n);
    for (int i = 1; i <= n; ++i) {
        long long value;
        cin >> value;
        bit.add(i, value);
    }

    while (m--) {
        int operation;
        cin >> operation;
        if (operation == 1) {
            int pos;
            long long value;
            cin >> pos >> value;
            bit.add(pos, value);
        } else {
            int left, right;
            cin >> left >> right;
            cout << bit.range_sum(left, right) << '\n';
        }
    }

    return 0;
}
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
61
62
63
64
65
66
67
68

        # 洛谷 P3374 树状数组 1：单点加 + 区间和。
# 下标从 1 开始，lowbit(0) = 0 会让修改循环原地打转。
# C++ 用 long long 防溢出；Python int 是任意精度，不必特判。

import sys


class Fenwick:
    """tree[i] 维护 a[i - lowbit(i) + 1 .. i] 的元素和。"""

    def __init__(self, size: int = 0) -> None:
        self.n = size
        self.tree = [0] * (size + 1)

    @staticmethod
    def lowbit(x: int) -> int:
        # 最低位那个 1 代表的块长，即 x & -x。
        return x & -x

    def add(self, pos: int, value: int) -> None:
        i = pos
        while i <= self.n:
            self.tree[i] += value
            i += self.lowbit(i)

    def prefix_sum(self, pos: int) -> int:
        answer = 0
        i = pos
        while i > 0:
            answer += self.tree[i]
            i -= self.lowbit(i)
        return answer

    def range_sum(self, left: int, right: int) -> int:
        return self.prefix_sum(right) - self.prefix_sum(left - 1)


def main() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(map(int, data))

    n = next(it)
    m = next(it)

    bit = Fenwick(n)
    for i in range(1, n + 1):
        bit.add(i, next(it))

    out: list[str] = []
    for _ in range(m):
        operation = next(it)
        if operation == 1:
            pos = next(it)
            value = next(it)
            bit.add(pos, value)
        else:
            left = next(it)
            right = next(it)
            out.append(str(bit.range_sum(left, right)))

    if out:
        sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    main()

测试用例

输入：

5 5
1 2 3 4 5
2 1 5
1 3 2
2 2 4
1 5 -1
2 4 5

输出：

15
11
8

第二次查询时，数组已经变成 [1,2,5,4,5][1,2,5,4,5]，所以 a2+a3+a4=11a_2+a_3+a_4=11。

易错点

  1. 树状数组必须使用从 11 开始的下标；lowbit(0)=0 会让修改循环无法前进。
  2. 区间 [l,r][l,r] 要写成 prefix_sum(r) - prefix_sum(l - 1)。
  3. 元素和可能超过 int，竞赛中通常使用 long long。
  4. add(pos, value) 表示增加 value，不是把 a[pos] 赋值为 value。

主练习与下一步

luogu-P3374 题解

这道题与本篇接口完全一致。完成后应能独立写出三个操作：单点加、前缀和、区间和。

下一篇：树状数组与差分：区间修改与单点查询。

相关练习题