codevs1081 线段树练习 2<区间修改>

1081 线段树练习 2

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

给你N个数，有两种操作

1：给区间[a,b]的所有数都增加X

2：询问第i个数是什么？

输入描述 Input Description

第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1，后接3个正整数a,b,X，表示在区间[a,b]内每个数增加X,如果是2，后面跟1个整数i, 表示询问第i个位置的数是多少。

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

1 2 3 2

2 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

数据范围

1<=n<=100000

1<=q<=100000

NotOnlySuccess

有兴趣的可以去这个博客看一下线段树，讲的真是很好。

先看一个暴力吧并没有什么用，我只是比较惊讶于暴力的神奇；正解在下边。.

 1 #include<iostream>
 2 using namespace std;
 3 #include<cstdio>
 4 int n,m,a[100005],l,r,f;
 5 int main() {
 6     cin>>n;
 7     for(int i=1; i<=n; i++)
 8         cin>>a[i];
 9     cin>>m;
10     for(int i=1; i<=m; i++) {
11         int x;
12         cin>>x;
13         if(x==1) {
14             cin>>l>>r>>f;
15             for(int i=l; i<=r; i++)
16                 a[i]+=f;
17         }
18         if(x==2) {
19             cin>>f;
20             cout<<a[f]<<endl;
21         }
22     }
23     return 0;
24 }

这里才是正解：

 1 //s d s
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<cstdlib>
 5 using namespace std;
 6 const int N=10000006;
 7 int a[N],sum[N];int miku[N];
 8 int b,c,d,e;
 9 
10 void update(int rt)
11 {
12     sum[rt]=sum[rt*2]+sum[rt*2+1];
13 }
14 
15 void build(int l,int r,int rt)
16 {
17     if(l==r)
18     {
19         sum[rt]=a[l];
20         return ;
21     }
22     int m=(l+r)/2;
23     build(l,m,rt*2);
24     build(m+1,r,rt*2+1);
25     update(rt);
26 }
27 
28 void midify_interval(int l,int r,int rt,int nowl,int nowr,int neww)
29 {
30     if(nowl==l&&nowr==r)
31     {
32         miku[rt]+=neww;
33         sum[rt]+=neww*(r-l+1);
34         return ;
35     }
36     int m=(l+r)>>1;
37     if(nowr<=m) midify_interval(l,m,rt*2,nowl,nowr,neww);
38     else if(nowl>m) midify_interval(m+1,r,rt*2+1,nowl,nowr,neww);
39     else 
40     {
41         midify_interval(l,m,rt*2,nowl,m,neww);
42         midify_interval(m+1,r,rt*2+1,m+1,nowr,neww);
43     }
44     update(rt);
45 }
46 
47 int query(int l,int r,int rt,int nowrt)
48 {
49     if(l==r)
50     {
51         return sum[rt];
52     }
53     int m=(r+l)/2;
54     sum[rt+rt]+=miku[rt]*(m-l+1);
55     sum[rt+rt+1]+=miku[rt]*(r-m);
56     miku[rt+rt]+=miku[rt];
57     miku[rt+rt+1]+=miku[rt];
58     miku[rt]=0;
59     int ans=0;
60     if(nowrt<=m) ans=query(l,m,rt<<1,nowrt);
61     else if(nowrt>m)  ans=query(m+1,r,rt*2+1,nowrt);
62     return ans;
63 }
64 
65 
66 int main()
67 {
68     int n;
69     scanf("%d",&n);
70     for(int i=1;i<=n;i++)scanf("%d",a+i);
71     build(1,n,1);
72     int m;
73     scanf("%d",&m);
74     
75     for(int i=1;i<=m;i++)
76     {
77         scanf("%d",&b);
78         if(b==1)
79         {
80             scanf("%d%d%d",&c,&d,&e);
81             midify_interval(1,n,1,c,d,e);
82         }
83         if(b==2)
84         {
85             scanf("%d",&c);
86             printf("%d
",query(1,n,1,c));
87         }
88     }
89     return 0;
90 
91 }