树状数组

树状数组

说明

普通树状数组维护的信息及运算要满足 结合律 且 可差分，如加法（和）、乘法（积）、异或等。
需要注意的是:

  • 模意义下的乘法若要可差分，需保证每个数都存在逆元（模数为质数时一定存在）；
  • 例如$gcd,max$ 这些信息不可差分，所以不能用普通树状数组处理,但是
    • 使用两个树状数组可以用于处理区间最值,详情见volume9.pdf (te.lv)
    • 对于不可差分的信息查询，有一种$Olog(^2n)$的拓展树状数组

事实上，树状数组能解决的问题是线段树能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。然而，树状数组的代码要远比线段树短，时间效率常数也更小，因此仍有学习价值。

前置知识

前缀和

前缀和与差分

lowbit

lowbit函数会求出一个二进制数字的最低位代表的那个数字

这是20的二进制 :$0010100$
而要获取最低的 $0000100$ 可以取反再加一变成 $1101100$ 之后再 进行按位与操作即可得到0010100 & 1101100 = 0000100
因为在计算机中有补码的存在所以取反加1其实就是对应的负数，所以lowbit函数的写法即为:

1
2
3
4
int lowbit(int x)
{
	return x & -x;
}

问题引入

给出一个长度为n的数组，完成以下两种操作

  • 将第x个数加上k
  • 输出区间[l,r]内每个数的和

朴素做法

朴素做法单点修改的时间复杂度是 $O(1)$ ,但是查询区间和的时间复杂度是 $O(n)$ 所以如果有 $n$ 次询问的话，时间复杂度为 $O(n^2)$ 。

前缀和做法

前缀和做法在查询区间和的时间复杂度是 $O(1)$ ,但是因为需要单点修改，导致修改一次就需要重新预处理一次，时间复杂度为 $O(n)$ 所以如果有n次修改，同样时间复杂度为 $O(n^2)$

树状数组介绍

而树状数组这一数据结构，可以很好解决这个问题，它在修改和查询上时间复杂度都为 $O(logn)$ 所以n次询问也仅仅只有 $O(nlogn)$ 。一般在 $10^6$的数据规模下使用。

推导过程

假如数组目前是为当前这个状态:
img
如果朴素做法是很慢的，我们可能会想到一个优化，即为让它们两两求和，保存起来，这样在求和的时候可以节约一半的时间，修改数据的时候也只是会多修改一个数字而已:
img
以此类推，我们可以得到这样的一张图:
img
这样我们在求前缀和的时候可以很简单的利用这些额外的速度快速的求出来，也是所谓的空间换时间了，但是通过观察我们可以发现表当中有一些数据是没有用的，或者说不是必须的。比如第二行的第一个5，我们在计算 $[3,4]$的区间和的时候，可以用 $19 - 14$ 来计算。所有层的第偶数个数字都是没用的，即使去掉也不影响:
img
然后观察剩下的数，可以发现正好有 $n$ 个，所以我们可以把这些数按照最靠右的位置放进一个数组,称为b数组:

img
所以在求前缀和时，我们只需要找到对应的几个区间，把这些区间相加即可找到答案。
修改某个数据时，我们也只需要向上找到包含它的区间进行修改即可。

我们把每行的区间长度列出来，并观察其下标的$lowbit$ 可以发现是相同的:
img
例如 b[12]，长度正好为lowbit(12) -> bin(1100)

如果我们要计算前14个元素的和，可以得到lowbit(14) = 12,所以就可以通过计算前12个的和，然后再加上b[14]就好了。

还有一个性质即为 序列b[i] 正上方的序列，正好就是 b[i + lowbit(i) ],所以我们在修改某一个位置的时候，就可以通过这个性质找到上方的序列，并进行修改。

这样我们便能很简单的写出查询和修改的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int ask(int x)//查询x的前缀和
    {
        int ans = 0;
        for (; x; x -= lowbit(x))
            ans += b[x];
        return ans;
    }
int ask(int x, int y)
    { // 区间查询
        return ask(y) - ask(x - 1);
    }
void add(int x, int k)//在x位置上加上k
    {
        for (; x <= n; x += lowbit(x))
            b[x] += k;
    }

拓展

区间修改|单点查询

普通的树状数组可以实现

  • 区间查询
  • 单点修改
    但是想要可以区间修改和单点查询该怎么办，我们可以利用差分来做，因为差分是前缀和的逆运算。
    所以我们要是维护的是一个差分数组，这样对单点修改就等同于对区间修改，同样的查询前缀和的时候也等同于查单点的原数据。
单点查询

设原数组为a[i],设的d[i] = a[i] - a[i-1] (a[0] = 0) ，则$a[i] = \sum_{j = 1}^{i}d[j]$ ,可以通过d[i]的前缀和查询。

区间修改

当给区间[l,r]加上x的时候，a[l]与前一个元素a[l-1]增加了 $x$ ,a[r + 1] 与 a[r]的差减少了$x$。根据d[i]数组的定义，只需要给d[l]加上$x$，给d[r+1]减去$x$,即可。

所以便有了单点查询和区间修改:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void add(int x, int k)
    {
        for (; x <= n; x += x & -x)
        {
            w[x] += k;
        }
    }

void add(int x, int y, int k)
{ // 区间修改
    add(x, k), add(y, -k);
}
int ask(int x)
{
    int ans = 0;
    for (; x; x -= x & -x)
    {
       ans += w[x];
    }
    return ans;
}

区间修改|区间查询

这是最常见的部分，也是线段树写着最麻烦的部分，但是我们可以用树状数组实现。
我们基于上面差分的思路，考虑一下如何构建前缀和。

  • $a_1 = d_1$
  • $a_2 = d_1 + d_2$
  • $a_3 = d_1 + d_2 + d_3$
  • $a_4 = d_1 + d_2 + d_3 + d_4$
  • $a_n = d_1 + d_2 + … + d_{n-1} +d_n$
    观察原数组$a$而言，单点查询就是$d$数组的前缀和。
    我们可以把这个表补全变成
    img
    设$s_n$为$a_n$的前缀和:$$s_n = \sum_{i = 1}^{n}d_i * (n + 1) - \sum_{i=1}^{n}i*d_i$$
    所以我们需要额外维护一个树状数组$i * d_i$ 这样使用两个树状数组就可以实现区间查询了，区间修改的话，就和使用差分的思路的时候是一样的。
    1
    2
    3
    i64 query(int x) {
            return sum(tr1, x) * (x + 1) - sum(tr2, x);
        }

二维树状数组

二维树状数组，也被称作树状数组套树状数组，用来维护二维数组上的单点修改和前缀信息问题。
这里暂时只给出封装模板

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
 struct BIT_2D {
    int n, m;
    vector<vector<int>> b1, b2, b3, b4;
    
    BIT_2D(int n, int m) : n(n), m(m) {
        b1.resize(n + 1, vector<int>(m + 1));
        b2.resize(n + 1, vector<int>(m + 1));
        b3.resize(n + 1, vector<int>(m + 1));
        b4.resize(n + 1, vector<int>(m + 1));
    }
    void add(auto &w, int x, int y, int k) { // 单点修改
        for (int i = x; i <= n; i += i & -i) {
            for (int j = y; j <= m; j += j & -j) {
                w[i][j] += k;
            }
        }
    }
    void add(int x, int y, int k) { 
        add(b1, x, y, k);
        add(b2, x, y, k * (x - 1));
        add(b3, x, y, k * (y - 1));
        add(b4, x, y, k * (x - 1) * (y - 1));
    }
    void add(int x, int y, int X, int Y, int k) { // 区块修改：二维差分
        X++, Y++;
        add(x, y, k), add(X, y, -k);
        add(X, Y, k), add(x, Y, -k);
    }
    int ask(auto &w, int x, int y) { // 单点查询
        int ans = 0;
        for (int i = x; i; i -= i & -i) {
            for (int j = y; j; j -= j & -j) {
                ans += w[i][j];
            }
        }
        return ans;
    }
    int ask(int x, int y) { 
        int ans = 0;
        ans += x * y * ask(b1, x, y);
        ans -= y * ask(b2, x, y);
        ans -= x * ask(b3, x, y);
        ans += ask(b4, x, y);
        return ans;
    }
    int ask(int x, int y, int X, int Y) { // 区块查询：二维前缀和
        x--, y--;
        return ask(X, Y) - ask(x, Y) - ask(X, y) + ask(x, y);
    }
};

封装代码

基础封装

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
struct BIT
{
    int n;
    vector<int> w;
    BIT(int n)
    {
        this->n = n; // 这里必须写 n ，否则会RE
        w.resize(n + 1);
    }
    void add(int x, int k)
    {
        for (; x <= n; x += x & -x)
        {
            w[x] += k;
        }
    }

    void add(int x, int y, int k)
    { // 区间修改
        add(x, k), add(y, -k);
    }
    int ask(int x)
    {
        int ans = 0;
        for (; x; x -= x & -x)
        {
            ans += w[x];
        }
        return ans;
    }
    int ask(int x, int y)
    { // 区间查询
        return ask(y) - ask(x - 1);
    }
};

升级封装

支持区间修改，区间求和，单点修改，单点查询。

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
class S_BIT
{
private:
    int n;
    vector<i64> tr1, tr2;
    i64 lowbit(i64 x)
    {
        return x & -x;
    }
    void __add(vector<i64> &tr, int x, i64 k)
    {
        for (; x <= n; x += lowbit(x))
            tr[x] += k;
    }
    i64 __ask(const vector<i64> &tr, int x)
    {
        i64 res = 0;
        for (; x; x -= lowbit(x))
            res += tr[x];
        return res;
    }
    i64 __sum(int x)
    {
        return __ask(tr1, x) * (x + 1) - __ask(tr2, x);
    }
public:
    S_BIT(int size) : n(size), tr1(size + 1), tr2(size + 1) {}
    void clear()
    {
        tr1.clear();
        tr2.clear();
    }
    i64 ask(int l, int r)//区间查询
    {
        return __sum(r) - __sum(l - 1);
    }
    i64 ask(int x)//单点查询
    {
        return ask(x, x);
    }
    void add(int x, int y, i64 v)//区间修改，注意差分
    {
        __add(tr1, x, v);
        __add(tr1, y, -v);
        __add(tr2, x, v * x);
        __add(tr2, y, -v * y);
    }
    void add(int x, i64 v)//单点修改
    {
        add(x, x+1, v);
    }
};

练习题目

P3374 【模板】树状数组 1 模板题
P3368 【模板】树状数组 2 区间修改，单点查询，维护差分模板题
P5057 [CQOI2006] 简单题区间修改，单点查询，维护差分模板题
P2068 统计和模板题，记得long long
P4939 Agent2区间修改，单点查询，维护差分模板题
P2357 守墓人 全操作
P1972 [SDOI2009] HH的项链区间种类个数

算法
#数据结构 #树状数组
树状数组
http://pikachuxpf.github.io/posts/59a0de58/
作者
Pikachu_fpx
发布于
2024年3月14日
许可协议