树状数组延伸

自用笔记算法

单点修改+区间查询

这是树状数组最基本的应用
转跳链接

poj 3321

题目要求

树上的单点修改和区间点权和
这里的区间求和是指子树(包括根)的所有结点权值和
单点修改为：1变0 0变1

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int tree[maxn];
int n,step;
vector<vector<int> >e(maxn);  
int in[maxn],out[maxn];
int vis[maxn];
void change(int x,int val){
    while(x<=n) {
        tree[x]+=val;
        x+=x&(-x);
    }
}
int sum(int x){
    int res=0;
    while (x){
        res+=tree[x];
        x-=x&(-x);
    }
    return res;
}
void dfs(int x,int fa){
	in[x]=step;
	int len=e[x].size();
	for(int i=0;i<len;i++){
		int next=e[x][i];
		if(next==fa) continue;
		step++;
		dfs(next,x);
	}
	out[x]=step;
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&n);
	for(int i=0;i<=n;i++) e[i].clear();
	mm(tree,0),mm(in,0),mm(out,0),mm(vis,0);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	step=1;
	dfs(1,0);
	for(int i=1;i<=n;i++){
		change(i,1);
		vis[i]=1;
	}
	int q; scanf("%d",&q);
	while(q--){
		char c; cin>>c;
		if(c=='C'){
			int x; scanf("%d",&x);
			if(vis[in[x]]) change(in[x],-1);
			else change(in[x],1);
			vis[in[x]]=!vis[in[x]];
		}
		else{
			int x; scanf("%d",&x);
			int ans=sum(out[x])-sum(in[x]-1);
			printf("%d\n",ans);
		}
	}
	return 0;
}

思路

由于是树上的树状数组问题 所以使用dfs序把树形结构转换为线性结构
维护两个时间戳in和out
注意开始时初始化均为1 利用vis数组可以快速判断执行+1操作还是-1操作

区间修改+单点查询

维护一个差分数组c[i]=a[i]-a[i-1]
如果想要修改a[i]到aj，只需令c[i]+=v,c[j+1]-=v
单点询问只需sum(c[i])即可

fzu 2277

转跳链接
由于此题没有初始数组(均为0) 所以只需要维护一个差分数组即可
tree1和tree2实际就是差分数组
若有初始数据可以利用change加到树中 也可以creat加入 也可以求前缀和+sum的结果避免插入操作
注意这里的out+1是建立在dfs里out为step-1的基础上

区间修改+区间查询

codeVS 1082

题目要求

区间修改+区间查询裸题

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 200050
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n;
LL a[maxn];
LL tree1[maxn],tree2[maxn];
void add(LL *tree,int x,LL val){
    while(x<=n) {
        tree[x]+=val;
        x+=x&(-x);
    }
}
LL sum(LL *tree,int x){
    LL res=0;
    while(x){
        res+=tree[x];
        x-=x&(-x);
    }
    return res;
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&n);
	mm(tree1,0),mm(tree2,0);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		add(tree1,i,a[i]-a[i-1]);
		add(tree2,i,(i-1)*(a[i]-a[i-1]));
	}
	int q; scanf("%d",&q);
	while(q--){
		int x; scanf("%d",&x);
		if(x==1){
			int l,r;
			LL k;
			scanf("%d%d%lld",&l,&r,&k);
			add(tree1,l,k); add(tree1,r+1,-k);
			add(tree2,l,k*(l-1)); add(tree2,r+1,-k*r);
		}
		else{
			int l,r;
			scanf("%d%d",&l,&r);
			LL temp1=(l-1)*sum(tree1,l-1)-sum(tree2,l-1);
			LL temp2=r*sum(tree1,r)-sum(tree2,r);
			printf("%lld\n",temp2-temp1);
		}
	}
	return 0;
}

思路

注意维护好tree2数组 开LL

二维树状数组

涉及到区间修改单点查询+单点修改区间查询

POJ 2155(区间修改单点查询)

题目要求

区间修改 矩形内0变1 1变0
问单点的值为多少

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int tree[maxn][maxn];
int n;
int sum(int i,int j){  
    int s=0;  
    while(i>0){  
        int jj=j;  
        while(jj>0){  
            s+=tree[i][jj];  
            jj-=jj&-jj;  
        }  
        i-=i&-i;  
    }  
    return s;  
}  
void add(int i,int j,int x){  
    while(i<=n){  
        int jj=j;  
        while(jj<=n) {  
            tree[i][jj]+=x;  
            jj+=jj&-jj;  
        }  
        i+=i&-i;  
    }  
}    
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		int q;
		scanf("%d%d ",&n,&q);
		mm(tree,0);
		while(q--){
			char c; cin>>c;
			if(c=='C'){
				int x1,y1,x2,y2;
				scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
				add(x1,y1,1);
				add(x1,y2+1,-1);
				add(x2+1,y1,-1);
				add(x2+1,y2+1,1);
			}
			else{
				int x,y;
				scanf("%d%d",&x,&y);
				printf("%d\n",sum(x,y)%2);
			}
		}
		if(t) printf("\n");
	}
	return 0;
}

思路

区间修改和一维树状数组一样 利用差分数组 注意修改的方式即可
本题记录的是修改的次数 偶数次修改不变 奇数次修改变位 所以最后答案%2即可

POJ 1195(单点修改区间查询)

题目要求

0表示初始化 3表示退出 1表示单点修改 2表示区间查询

参考AC代码

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<bits/stdc++.h>
#define maxn 1050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int tree[maxn][maxn];
int n;
int sum(int i,int j){  
    int s=0;  
    while(i>0){  
        int jj=j;  
        while(jj>0){  
            s+=tree[i][jj];  
            jj-=jj&-jj;  
        }  
        i-=i&-i;  
    }  
    return s;  
}  
void add(int i,int j,int x){  
    while(i<=n){  
        int jj=j;  
        while(jj<=n) {  
            tree[i][jj]+=x;  
            jj+=jj&-jj;  
        }  
        i+=i&-i;  
    }  
}
int main(){
//	freopen("input.txt","r",stdin);
	int x;
	while(1){
		scanf("%d",&x);
		if(x==3) break;
		if(x==0){
			mm(tree,0);
			scanf("%d",&n);
		}
		if(x==1){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			a++,b++;
			add(a,b,c);
		}
		if(x==2){
			int x1,x2,y1,y2;
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			x1++,x2++,y1++,y2++;
			printf("%d\n",sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1));
		}
	} 
	return 0;
}

思路

裸题
注意树状数组的下标要从1开始 本题是从0开始所以所有的坐标都要+1
以及利用容斥对矩形查询的方式

HDU 1892(单点修改区间查询)

题目要求

S表示区间查询
A表示单点增加
D表示单点减少
M表示把点A的值移到点B上

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1010
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int num[maxn][maxn];
int tree[maxn][maxn];
int lowbit(int x){
    return x&(-x);
}
void init(){
    mm(tree,0);
    for(int i=1;i<maxn;i++){
        for(int j=1;j<maxn;j++){
        	num[i][j]=1;
        	tree[i][j]=lowbit(i)*lowbit(j);
		}
    }
}
int sum(int i,int j){  
    int s=0;  
    while(i>0){  
        int jj=j;  
        while(jj>0){  
            s+=tree[i][jj];  
            jj-=jj&-jj;  
        }  
        i-=i&-i;  
    }  
    return s;  
}  
void add(int i,int j,int x){  
    while(i<maxn){  
        int jj=j;  
        while(jj<maxn){  
            tree[i][jj]+=x;  
            jj+=jj&-jj;  
        }  
        i+=i&-i;  
    }  
}
int flag=1;
int main(){
//    freopen("input.txt","r",stdin);
    int t; scanf("%d",&t);
    while(t--){
        cout<<"Case "<<flag++<<":"<<endl;
        init();
        int q; scanf("%d",&q);
        while(q--){
            char c; cin>>c;
	         if(c=='S'){
                int x1,y1,x2,y2;
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                x1++,y1++,x2++,y2++;
                int x3=min(x1,x2),y3=min(y1,y2);
                int x4=max(x1,x2),y4=max(y1,y2);
                int ans=sum(x4,y4)-sum(x4,y3-1)-sum(x3-1,y4)+sum(x3-1,y3-1);
                printf("%d\n",ans);
            }
	        else if(c=='A'){
                int x,y,k;
                scanf("%d%d%d",&x,&y,&k);
                x++,y++;
                add(x,y,k);
                num[x][y]+=k;
            }
	        else if(c=='D'){
                int x,y,k;
                scanf("%d%d%d",&x,&y,&k);
                x++,y++;
                k=min(num[x][y],k);
                num[x][y]-=k;
                add(x,y,-k);
            }
	        else{
                int x1,y1,x2,y2,k;
                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
                x1++,y1++,x2++,y2++;
                k=min(num[x1][y1],k);
                num[x1][y1]-=k;
                num[x2][y2]+=k;
                add(x1,y1,-k);
                add(x2,y2,k);
            }
        }
    }
    return 0;
}

思路

同样这题的下标从0开始 所以+1
本题需要注意2个点的坐标无固定的大小关系 所以S操作要判断出谁是左上谁是右下
同样需要注意本题需要一个num数组用来存放每个点的值 为了在减少到0以下时值为0
最后注意memset不能赋1 以及初始化tree为1的快速方法

本文标题:树状数组延伸

文章作者:Hippopmonkey

发布时间:2017-08-17, 12:08:13

最后更新:2017-08-17, 23:13:05

原始链接:http://xuboming8.github.io/2017/08/17/树状数组延伸/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 单点修改+区间查询
    1. 1.1. poj 3321
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
  2. 2. 区间修改+单点查询
    1. 2.1. fzu 2277
  3. 3. 区间修改+区间查询
    1. 3.1. codeVS 1082
      1. 3.1.1. 题目要求
      2. 3.1.2. 参考AC代码
      3. 3.1.3. 思路
  4. 4. 二维树状数组
    1. 4.1. POJ 2155(区间修改单点查询)
      1. 4.1.1. 题目要求
      2. 4.1.2. 参考AC代码
      3. 4.1.3. 思路
    2. 4.2. POJ 1195(单点修改区间查询)
      1. 4.2.1. 题目要求
      2. 4.2.2. 参考AC代码
      3. 4.2.3. 思路
    3. 4.3. HDU 1892(单点修改区间查询)
      1. 4.3.1. 题目要求
      2. 4.3.2. 参考AC代码
      3. 4.3.3. 思路
|