Wuyanru's blog
0%

树状数组

发表于 分类于 ，

树状数组是一种数据结构，常用于区间修改、区间查询等问题，功能没有线段树多，但胜在常数比线段树小了许多，且代码较短，更容易实现。

树状数组本质上就是一个数组，他们之间的关系就像一棵树一样，层层管理。

不妨设原数组为 ，树状数组为 ，则 。

那么 又是什么呢？

其实就是一个二进制数最后的 所代表的值。

并且因为补码的原因，还有 。

对于每一个 ，管理 的节点可能有很多个，但是直接进行管理的最多只有一个，其他的都是间接进行管理。

举个例子：

被 直接管理；

被 直接管理；

被 直接管理；

被 直接管理；

被 直接管理；

被 直接管理；

被 直接管理；

不被任何节点管理。

不难瞪出直接管理 的节点编号为 。

建树思路 ：

对于每一个 ，称直接管理 的节点为 。

管理 ， 又管理 ， 显然管理 。

父亲编号证明

我们刚刚只是用眼睛发现了 的父亲是 ，现在我们来证明。

为了方便，我们先设 。

我们先来证明 管理 。

这个很显然，因为 ，

那么就一定会有 。

管理的节点为 。

又有 ，即 。

所以 一定管理 。

我们再来证明 是所有管理 的节点中最小的。

假设 ，则一定 。

假设还有一个数字 满足 ，我们设 ，显然还有 。

因为我们知道 ，也就是说 和 在大于 的位上都是相同的。

由于 ，所以他们三个数字在大于 的位上也是相同的。

也就是说他们三个数应该长这个样子：

注意到 ，所以这个时候 的第 位上肯定是 。 然后你就会发现 ，但是根据我们之前的假设 。

所以 肯定为管理 的最小的节点。

树状数组建树

根据刚刚的结论，我们也可以算出，管理 的节点总共只有 的。

所以，我们就可以暴力找出所有管理 的节点，然后修改这个点的权值，时间复杂度 。

代码：

1
2
3
4
5
6
7
8
9
for(int i=1;i<=n;i++)
{
    int num=i;
    while(num<=n)
    {
        t[num]+=a[i];
        num+=lowbit(num);
    }
}

建树思路 ：

对于每一个 ，管理 的节点必定管理所有 所管理的节点。

所以直接找到直接管理 的节点，对其进行修改即可，时间复杂度 。

代码：

1
2
3
4
5
6
7
for(int i=1;i<=n;i++)
{
    t[i]+=a[i];
    int num=i+lowbit(i);
    if(num<=n)
        t[num]+=t[i];
}

优化：如果你想要节省内存，那么数组 与 可以为同一个数组，读入时读入 即可。

代码： 

1
2
3
4
5
6
for(int i=1;i<=n;i++)
{
    int num=i+lowbit(i);
    if(num<=n)
        t[num]+=t[i];
}

树状数组的修改

根据建树所提到的，只需修改管理该节点的所有节点即可。

1
2
3
4
5
6
7
8
void add(int x,int y)//将第x个数的值增加y
{
    while(x<=n)
    {
        t[x]+=y;
        x+=lowbit(x);
    }
}

树状数组的查询

树状数组这种数据结构可以做到 查询前缀和，一个点管理的所有点为它自己（包括）之前的 个节点，只需要利用这种关系查询即可。

1
2
3
4
5
6
7
8
9
10
void get(int x)//查询前x个数的值
{
    int ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}

树状数组维护信息

单点修改与区间查询

例题

操作 与上述所讲完全一样，树状数组即可。

操作 中的 并不保证是 ，我们可以利用：

解得答案。

代码： 

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
#include<cstdio>
using namespace std;
int lowbit(int i)
{
    return i&-i;
}
int t[500001];
int n,m;
void build()
{
    for(int i=1;i<=n;i++)
    {
        int num=i+lowbit(i);
        if(num<=n)
            t[num]+=t[i];
    }
}
void change(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
        t[i]+=y;
}
int get(int x)
{
    int num=0;
    for(int i=x;i;i-=lowbit(i))
        num+=t[i];
    return num;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",t+i);
    build();
    for(int i=1;i<=m;i++)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int x,k;
            scanf("%d%d",&x,&k);
            change(x,k);
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",get(y)-get(x-1));
        }
    }
    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
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
#include<cstdio>
using namespace std;
int lowbit(int i)
{
    return i&-i;
}
int t[500001];
int n,m;
void build()
{
    for(int i=1;i<=n;i++)
    {
        int num=i+lowbit(i);
        if(num<=n)
            t[num]+=t[i];
    }
}
void change(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
        t[i]+=y;
}
int get(int x)
{
    int num=0;
    for(int i=x;i;i-=lowbit(i))
        num+=t[i];
    return num;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",t+i);
    for(int i=n;i;i--)
        t[i]-=t[i-1];
    build();
    for(int i=1;i<=m;i++)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int x,y,k;
            scanf("%d%d%d",&x,&y,&k);
            change(x,k);
            change(y+1,-k);
        }
        else
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",get(x));
        }
    }
    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
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<cstdio>
using namespace std;
long long a[100010];
long long b[100010];
long long c[100010];
long long n,m;
inline long long read()
{
    long long s=0,w=1;
    char ch;
    while((ch=getchar())>'9'||ch<'0')
        if(ch=='-')
            w=-1;
    while(ch>='0'&&ch<='9')
    {
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}
inline long long lowbit(long long i)
{
    return i&(-i);
}
inline void build()
{
    for(long long i=1;i<=n;i++)
    {
        long long num=i;
        while(num<=n)
        {
            b[num]+=a[i];
            c[num]+=a[i]*i;
            num+=lowbit(num);
        }
    }
}
inline void change(long long x,long long k)
{
    long long num=x;
    while(num<=n)
    {
        b[num]+=k;
        c[num]+=x*k;
        num+=lowbit(num);
    }
}
inline long long get(long long x)
{
    long long ans=0,num=x;
    while(num)
    {
        ans+=b[num];
        num-=lowbit(num);
    }
    ans*=(x+1);
    num=x;
    while(num)
    {
        ans-=c[num];
        num-=lowbit(num);
    }
    return ans;
}
int main()
{
    n=read(),m=read();
    for(long long i=1;i<=n;i++)
        a[i]=read();
    for(long long i=n;i;i--)
        a[i]-=a[i-1];
    build();
    for(long long i=1;i<=m;i++)
    {
        long long op;
        op=read();
        if(op==1)
        {
            long long l,r,k;
            l=read(),r=read(),k=read();
            change(l,k);
            change(r+1,-k);
        }
        else
        {
            long long l,r;
            l=read(),r=read();
            printf("%lld\n",get(r)-get(l-1));
        }
    }
    return 0;
}