原理解释

树状数组是一种通过前缀和和差分的思想所进行的维护数组，从而以 O(log⁡n)O(\log n) 的时间复杂度进行修改和查询。

一共有四种修改和查询的方式，分别是：

  • 单点修改 ++ 区间询问

  • 区间修改 ++ 单点询问

  • 单点修改 ++ 区间询问

  • （二维）区间修改 ++ 区间询问

    其中利用树状数组可以高效而简洁地处理第二、三个问题，第四个问题推荐使用【模板/笔记】线段树。

查询

查询可以计算左右区间的总和，通过它们的前缀和相减求出区间和。通过上图可以发现，如果要求 sum7sum_{7} 的值，可以发现 sum7=tree7+tree6+tree4sum_{7} = tree_{7} + tree_{6} + tree_{4}，而 7,6,47,6,4 之间有什么关联呢？

将其转化为二进制可以看出：7=(111)2,6=(110)2,4=(100)27=(111)_{2},6=(110)_{2},4=(100)_{2}，它们二进制中 11 的个数是不断减少的，而且减少的是最后一位，我们只需要在每一次加后将最后一位的 11 变为 $ 0 $ 即可。

维护

和查询一样，将一个数 treeitree_{i} 加上 kk，只需要将 ii 的二进制的最后的 11 加上 11，直到加的数超过了树状数组的大小。

可以定义一个函数 lowbit(x) 来求出一个二进制数的最后一位 11：

1
2
3
4
int lowbit(int x)
{
    return x & -x; // 一个数的原码与上补码
}

代码实现

单点修改

1
2
3
4
5
void update(int x, int d) // 在第x点上加上d
{
    for (int i = x; i <= n; i += lowbit(x))
        tr[i] += d;
}

单点查询

1
2
3
4
5
6
7
int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
       return res;
}

单点修改 + 查询 主函数

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
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        cin >> x;
        update(i, x);
    }
    while (m--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x, k; cin >> x >> k;
            update(x, k);
        }
        else
        {
            int x, y; cin >> x >> y;
            cout << sum(y) - sum(x - 1) << '\n';
        }
    }
    return 0;
}

区间修改 + 单点查询 主函数

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
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        update(i, a[i] - a[i - 1]);
    }
    while (m--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x, y, k; cin >> x >> y >> k;
            update(x, k);
            update(y + 1, -k);
        }
        else
        {
            int x; cin >> x;
            cout << sum(x) << '\n';
        }
    }
    return 0;
}