mydcwfy's Blog

树状数组

Posted on
Symbols count in article: 5.8k Reading time ≈ 13 mins.

简单的前置知识。

树状数组

1.基本功能

树状数组可以在 $O(\log n)$ 的时间里，完成1.求前缀和或者2.修改某一个数。

最坏情况下，也只是 $O(m \log n)$ 的复杂度。

2.基本原理

基于二进制拆分思想。

$\forall x\in N^+, x=2^ {i_k}+2^{i_{k-1}}+…+2^{i_2}+2{i_1}$，

其中 $i_k\geq i_{k-1} \geq…\geq i_2\geq i_1$。

于是，我们将整个区间分为 $\log n$ 个区间。

分别为 $[x-2^{i_1}+1,x]$,$[x-2^{i_2}-2^{i_1}+1,x-2^{i_1}]$ … $[1,2^{i_{k}}]$。

每次，都可以取出 $2^i$，它是 x 的二进制表示的最后一位 1。

定义 $\operatorname{lowbit}(r)$ 表示 r 的最后一位 1 所表示的数。

那么，$\forall x$，第一个区间都可以表示为 $[x-\operatorname{lowbit}(x)+1,x]$

又发现，每一个 x，只有一个区间，而这个区间又很容易得到。

那么，让树状数组 $c[x]$ 表示区间$[x-\operatorname{lowbit}(x)+1,x]$

又二进制拆分最多只有 $\log n$ 位，所以每一个 x 的前缀和都可以拆分为 $\log n$ 个区间。

举个例子，13 的区间计算如下：

  1. $13=(1101)_2,\operatorname{lowbit}(13)=1:[13,13]$

  2. $13-\operatorname{lowbit}(13)=12$

  3. $12=(1100)_2,\operatorname{lowbit}(12)=4:[9,12]$

  4. $12-\operatorname{lowbit}(12)=8$

  5. $8=(1000)_2,\operatorname{lowbit}(8)=8:[1,8]$

  6. $8-\operatorname{lowbit}(8)=0$

结束。

讨论如何单点修改。

比如，我们需要在 13 加一个数。

可以发现，14 16 都要加上这个数。

相当于， $c[x]$ 代表的区间包含该数，那么该点需要修改。

将树状数组改为树的形式，也就是它的祖先都要修改。

当 13 加上 $\operatorname{lowbit}(13)$，则从低到高所有连续的 1 都会向前进位，直到碰到一个0。

这样得到的数，所包含的区间一定包含该数。

最后，我们还没讨论 $\operatorname{lowbit}(x)$。

如何计算 $\operatorname{lowbit}(x)$。

结论：$\operatorname{lowbit}(x)=x$ & $(-x)$

$x=(…100…0)_2$（前面随意）。

又 $-x=\sim x+1$，所以所有的 0 都变成 1，接着加 1，所有最后的 1 都进位，直到原来的 1 不会进位，所以 & 后，不会舍去，而其他位都被去掉。

3.扩展

1）差分

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

直接维护当前的差分数组即可（差分就是 $b[i]=a[i]-a[i-1]$ ）

2）差分加区间和

同样维护一个差分数组,也就是维护前缀和。

公式如下：

进一步推导可以得到：

分离 x 与 i：

维护 b[x] 的前缀和和 $x * b[x]$ 的前缀和即可。

4.例题

T1：楼兰图腾

题目传送门 AcWing

维护当前左端的数，即可。

先从左向右记录比当前数大的个数和小的个数。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) x&(-x)
#define ll long long
using namespace std;

const int N=2e5+10;
ll c[N],g[N],l[N];
int n,a[N];

void add(int x,int r)
{
    for (int i=x;i<=n;i+=lowbit(i))
        c[i]+=(ll)r;
}

ll sum(int x)
{
    ll res=0;
    for (int i=x;i;i-=lowbit(i))
        res+=c[i];
    return res;
}

int main()
{
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",a+i);
    for (int i=1;i<=n;++i)
    {
        g[i]=sum(n)-sum(a[i]);
        l[i]=sum(a[i]-1);
        add(a[i],1);
    }
    memset(c,0,sizeof c);
    ll res1=0,res2=0;
    for (int i=n;i;--i)
    {
        res1+=g[i]*(sum(n)-sum(a[i]));
        res2+=l[i]*(sum(a[i]-1));
        add(a[i],1);
    }
    printf("%lld %lld",res1,res2);
    return 0;
}

T2：一个简单的整数问题

题目传送门 AcWing

刚才扩展 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
53
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define lowbit(x) x&-x
#define ll long long
using namespace std;

const int N=1e5+10;
ll c[N];
int n;

void add(int x,int r)
{
    for (int i=x;i<=n;i+=lowbit(i))
        c[i]+=(ll)r;
    return;
}
ll sum(int x)
{
    ll res=0;
    for (int i=x;i;i-=lowbit(i))
        res+=c[i];
    return res;
}

int main()
{
    int m,x,y,t,l=0;
    char op[5];
    cin>>n>>m;
    for (int i=1;i<=n;++i)
    {
        scanf("%d",&x);
        add(i,x-l);
        l=x;
    }

    while (m--)
    {
        scanf("%s%d",op,&x);
        if (op[0]=='Q')
        {
            cout<<sum(x)<<endl;
        }
        else
        {
            scanf("%d%d",&y,&t);
            add(y+1,-t);add(x,t);
        }
    }
    return 0;
}

T3：一个简单的整数问题2

题目传送门 AcWing

扩展 2 的模板题。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) x&(-x)
#define ll long long
using namespace std;

const int N=1e5+10;
ll c[2][N],a[N],n,sum[N];

void add(int k,int x,ll d)
{
	for (;x<=n;x+=lowbit(x)) c[k][x]+=d;
}

ll query(int k,int x)
{
	ll ans=0;
	for (;x;x-=lowbit(x)) ans+=(ll)c[k][x];
	return ans; 
}

int main()
{
	int m,b;ll d;
	cin>>n>>m;
	for (int i=1;i<=n;++i) scanf("%lld",a+i),sum[i]=sum[i-1]+a[i];
	char op[3];int a;
	while (m--)
	{
		scanf("%s%d%d",op,&a,&b);
		if (op[0]=='C')
		{
			scanf("%lld",&d);
			add(0,a,d);add(0,b+1,-d);
			add(1,a,a*d);add(1,b+1,-(b+1)*d);
		}
		else
		{
			ll ans=sum[b]-sum[a-1];
			ans+=(b+1)*query(0,b)-query(1,b);
			ans-=(a)*query(0,a-1)-query(1,a-1);
			printf("%lld\n",ans);
		}
	}
	return 0;
}

T4：谜一样的牛

题目传送门 ACWing

在线维护从前往后第 $a[i]+1$ 个1，就是本题答案。

考虑如何维护。

首先维护成前缀和。

一种比较简单的方法就是二分答案。

时间复杂度为 $O(n \log^2 n)$。

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define lowbit(x) x&-x
using namespace std;

const int N=1e5+10;

int c[N],n,a[N],ans[N];

void add(int x,int r)
{
    for (int i=x;i<=n;i+=lowbit(i)) c[i]+=r;
}

int sum(int x)
{
    int ans=0;
    for (int i=x;i;i-=lowbit(i)) ans+=c[i];
    return ans;
}

int main()
{
    cin>>n;
    for (int i=2;i<=n;++i) scanf("%d",a+i);
    for (int i=1;i<=n;++i) add(i,1);
    for (int i=n;i;--i)
    {
        int l=1,r=n;
        while (l<r)
        {
            int mid=l+r>>1;
            if (sum(mid)>=a[i]+1) r=mid;
            else l=mid+1;
        }
        ans[i]=l;
        add(l,-1);
    }
    for (int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}

另一种是倍增算法。

我们发现，树状数组恰好为我们维护的 2 的整数幂。

考虑使用倍增，如果当前的和小于需要的结果，那么就加上。

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define lowbit(x) x&-x
using namespace std;

const int N=1e5+10,L=20;

int c[N],n,a[N],ans[N];

void add(int x,int r)
{
    for (int i=x;i<=n;i+=lowbit(i)) c[i]+=r;
}

int sum(int x)
{
    int ans=0;
    for (int i=x;i;i-=lowbit(i)) ans+=c[i];
    return ans;
}

int main()
{
    cin>>n;
    for (int i=2;i<=n;++i) scanf("%d",a+i);
    for (int i=1;i<=n;++i) add(i,1);
    for (int i=n;i;--i)
    {
        int now=0,nowsum=0;
        for (int j=L;j>=0;--j)
        {
            if (now+(1<<j)>n) continue;
            if (nowsum+c[now+(1<<j)]<a[i]+1) now+=(1<<j),nowsum+=c[now];
        }
        ans[i]=now+1;
        add(ans[i],-1);
    }
    for (int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}
算法 时间 空间
二分答案算法 267 ms 2514 KB
倍增算法 134 ms 2008 KB

实测 AcWing。