树状数组或二元索引树（英语：Binary Indexed Tree，Fenwick Tree），是一种用于高效处理对一个存储数字的列表进行更新及求前缀和的数据结构。

树状数组的元素所管理的序列结构如下图所示：

g9RY7V.md.png

树状数组（单点修改）

模板题：洛谷 P3374 | [模板] 树状数组 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  • 将某一个数加上 xx

  • 求出某区间每一个数的和

输入格式

第一行包含两个正整数 n,mn,m ，分别表示该数列数字的个数和操作的总个数。

第二行包含 nn 个用空格分隔的整数，其中第 ii 个数字表示数列第 ii 项的初始值。

接下来 mm 行每行包含 33 个整数，表示一个操作，具体如下：

  • 1 x k 含义：将第 xx 个数加上 kk

  • 2 x y 含义：输出区间 [x,y][x,y] 内每个数的和

输出格式

输入输出样例

输入
1
2
3
4
5
6
7
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出
1
2
14
16

说明/提示

【数据范围】

对于 30%30\% 的数据， 1≤n≤81 \le n \le 8 ， 1≤m≤101\le m \le 10 ；

对于 70%70\% 的数据， 1≤n,m≤1041\le n,m \le 10^4 ；

对于 100%100\% 的数据， 1≤n,m≤5×1051\le n,m \le 5\times 10^5 。

解决方案

代码

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
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 500500;
int n, m;
long long c[maxn];
int lowbit(int x)
{
    return x & -x;
}
void add(int x, long long k)
{
    while (x <= n)
    {
        c[x] += k;
        x += lowbit(x);
    }
}
long long query(int x, int y)
{
    long long ans1 = 0, ans2 = 0;
    x--;
    while (x >= 1)
    {
        ans1 += c[x];
        x -= lowbit(x);
    }
    while (y >= 1)
    {
        ans2 += c[y];
        y -= lowbit(y);
    }
    return ans2 - ans1;
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        long long x;
        scanf("%lld", &x);
        add(i, x);
    }
    for (int i = 1; i <= m; i++)
    {
        int op, x, k;
        scanf("%d %d %d", &op, &x, &k);
        if (op == 1)
        {
            add(x, (long long)k);
        }
        if (op == 2)
        {
            printf("%lld\n", query(x, k));
        }
    }
    return 0;
}

树状数组（区间操作）

请参阅