树状数组:
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