首页 > 编程语言 > 详细

树状数组初步用法

时间:2021-06-29 23:02:07      阅读:34      评论:0      收藏:0      [点我收藏+]

树状数组:

1:单点增加,区间询问(前缀和)

 1 #include<iostream>
 2 using namespace std;
 3 #define ll long long
 4 int a[1000000];//原数组 
 5 int tre[1000000];//树状数组 
 6 int n;
 7 int sum(int i)//[1,i]sum
 8 {
 9     int s=0;
10     while(i>0){
11         s+=tre[i];
12         i-=i&-i;
13     }
14     return s;
15 }
16 int update(int i,int value)//a[i]+=value
17 {
18     while(i<=n){
19         tre[i]+=value;
20         i+=i&-i;
21     }
22 }
23 int main()
24 {
25     int t,q;
26     cin>>n>>t>>q;//n个数,t次修改,q次询问 
27     for(int i=1;i<=n;i++){
28         cin>>a[i];
29         update(i,a[i]);
30     }
31     int l,r,c; 
32     while(t--){
33         cin>>l>>c;
34         update(l,c);
35     } 
36     while(q--){
37         cin>>l>>r;
38         cout<<sum(r)-sum(l-1)<<endl;
39     }
40     return 0;
41 }

 

技术分享图片

 

 

 

2.区间修改,单点查询(差分)

 1 #include<iostream>
 2 using namespace std;
 3 #define ll long long
 4 int a[1000000];//原数组 
 5 int d[1000000];//差分数组 
 6 int tre[1000000];//树状数组 
 7 int n;
 8 int sum(int i)//[1,i]sum
 9 {
10     int s=0;
11     while(i>0){
12         s+=tre[i];
13         i-=i&-i;
14     }
15     return s;
16 }
17 int update(int i,int value)//a[i]+=value
18 {
19     while(i<=n){
20         tre[i]+=value;
21         i+=i&-i;
22     }
23 }
24 int main()
25 {
26     int t,q,m; 
27     cin>>n>>t>>q;//n个数,t次修改,q次询问 
28     for(int i=1;i<=n;i++){
29         cin>>a[i];
30         d[i]=a[i]-a[i-1]; 
31         update(i,d[i]);
32     }
33     int l,r,c;
34     while(t--){
35         cin>>l>>r>>c;
36         d[l]+=c;//差分数组更新 
37         d[r+1]-=c;
38         update(l,c);//树状数组更新 
39         update(r+1,-c);
40     }
41     while(q--){
42         cin>>l;//查询l点具体数值 
43         cout<<sum(l)<<endl;
44     }
45     return 0;
46 }

测试数据:

技术分享图片

3:区间修改,区间查询(记不住系列)

借用杭电视频截图= =

技术分享图片

 

 技术分享图片

 

 技术分享图片

 

树状数组初步用法

原文:https://www.cnblogs.com/20km-shimakaze/p/14951873.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!