线段树练习2

给你N个数，有两种操作

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

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

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

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

3

1

2

3

2

1 2 3 2

2 3

5

数据范围

1<=n<=100000

1<=q<=100000

                             1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4#define ll long long
 5usingnamespace std;
 6constint N=200010;
 7 ll a[N*4],tag[N*4];
 8int n,b;
 9ll read(){
10     register ll f=1,x=0;
11     register char ch=getchar();
12while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘) f=-1;ch=getchar();}
13while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();
14return x*f;
15}
16void ins(int k,int l,int r,int x,int y){
17int mid=(l+r)>>1;
18if(l==r) {a[k]=y;return;}
19if(x>mid) ins(k<<1|1,mid+1,r,x,y);
20else ins(k<<1,l,mid,x,y);
21     a[k]=a[k<<1]+a[k<<1|1];
22}
23void pushdown(int x,int l,int r){
24int lc=x<<1,rc=x<<1|1,mid=(l+r)>>1;
25if(!tag[x]) return;
26     a[lc]+=tag[x]*(mid-l+1);
27     a[rc]+=tag[x]*(r-mid);
28     tag[lc]+=tag[x];tag[rc]+=tag[x];tag[x]=0;
29}
30void add(int k,int l,int r,int L,int R,int val){
31int mid=(l+r)>>1;
32if(l==L&&r==R){
33         tag[k]+=val;a[k]+=val*(R-L+1);return;
34    }
35    pushdown(k,l,r);
36if(R<=mid) add(k<<1,l,mid,L,R,val);
37elseif(L>mid) add(k<<1|1,mid+1,r,L,R,val);
38else add(k<<1,l,mid,L,mid,val),add(k<<1|1,mid+1,r,mid+1,R,val);
39     a[k]=a[k<<1]+a[k<<1|1];
40}
41 ll query(int k,int l,int r,int L,int R){
42int mid=(l+r)>>1;
43if(l==L&&r==R) return a[k];
44    pushdown(k,l,r);
45if(R<=mid) return query(k<<1,l,mid,L,R);
46elseif(L>mid) return query(k<<1|1,mid+1,r,L,R);
47elsereturn query(k<<1,l,mid,L,mid)+query(k<<1|1,mid+1,r,mid+1,R);    
48}
49int main(){
50     n=read();
51for(int i=1;i<=n;i++) b=read(),ins(1,1,n,i,b);
52int q=read();
53for(int i=1;i<=q;i++){
54int opt=read();
55if(opt==1){
56int l=read(),r=read(),val=read();
57             add(1,1,n,l,r,val);
58        }
59else{
60int l=read();
61             printf("%lld\n",query(1,1,n,l,l));
62        }
63    }
64return0;
65 }