首页 > 编程语言 > 详细

树状数组2模板 Luogu 3368

时间:2017-08-21 19:30:19      阅读:237      评论:0      收藏:0      [点我收藏+]

树状数组区间修改&&**……*&%&……

好吧,我看了Running-coder的博客,久久才明白……

废话不多说:讲思路:无………………

 

代码:

 1  #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 int bit[1000000],n,m,d,p,xx,yy,kk;
 7 int lazy[1000000];
 8 int a[1000000];
 9 
10 void add(int i,int x){
11     while(i<=n){
12         bit[i]+=x;
13         i+=i & -i;
14     }
15 }
16 
17 void addn(int x,int y,int k){
18     while(y>=x){
19         lazy[y]+=k;
20         y -=y & -y;
21     }
22     x--;
23     while(x>y){
24         lazy[x]-=k;
25         x -=x& -x;
26     }
27 }
28 
29 int sum(int i){
30     int s=a[i];
31     while(i<=n){
32         s+=lazy[i];
33         i+=i & -i;
34     }
35     return s;
36 }
37 
38 int main(){
39     scanf("%d %d",&n,&m);
40     for(int j=1;j<=n;j++){
41         scanf("%d",&d);
42         add(j,d);
43         a[j]=d;
44     }
45     for(int j=1;j<=m;j++){
46         scanf("%d",&p);
47         switch (p){
48             case 1:{
49                 scanf("%d %d %d",&xx,&yy,&kk);
50                 addn(xx,yy,kk);
51                 break;
52             }
53             case 2:{
54                 scanf("%d",&xx);
55                 cout<<sum(xx)<<endl;
56                 break;
57             }
58         }
59     }
60     return 0;
61 }  

 

树状数组2模板 Luogu 3368

原文:http://www.cnblogs.com/Misaki-Mei/p/7401533.html

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