区间修改单点查询

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 const int N=1e5+5;
 6 int n,m;
 7 int sum[N<<2],laze[N<<2]; //延迟标记
 8 
 9 void Update(int rt){
10     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
11 }
12 
13 void Updown(int rt,int l,int r){
14     if(laze[rt]){
15         laze[rt<<1]+=laze[rt];
16         laze[rt<<1|1]+=laze[rt];
17         int mid=(l+r)>>1;
18         sum[rt<<1]+=laze[rt]*(mid-l+1);
19         sum[rt<<1|1]+=laze[rt]*(r-(mid+1)+1);
20         laze[rt]=0;
21     }
22 }
23 
24 void Build(int l,int r,int rt){
25     if(l==r) {scanf("%d",&sum[rt]);return;}
26     int mid=(l+r)>>1;
27     Build(l,mid,rt<<1);
28     Build(mid+1,r,rt<<1|1);
29     Update(rt);  //不要忘记往上更新
30 }
31 
32 void Add(int l,int r,int rt,int L,int R,int V){
33     if(L<=l&&R>=r){
34         sum[rt]+=(r-l+1)*V;
35         laze[rt]+=V;  //延迟标记
36         return;
37     }
38     Updown(rt,l,r);  //延迟标记往下更新
39     int mid=(l+r)>>1;
40     if(L<=mid) Add(l,mid,rt<<1,L,R,V);
41     if(R>mid) Add(mid+1,r,rt<<1|1,L,R,V);
42     Update(rt);
43 }
44 
45 int ans;
46 void query(int l,int r,int rt,int p){
47     if(l==r) {ans=sum[rt];return;}
48     Updown(rt,l,r);   //用到要更新 延迟标记
49     int mid=(l+r)>>1;
50     if(mid>=p) query(l,mid,rt<<1,p);
51     else query(mid+1,r,rt<<1|1,p);
52 }
53 
54 int main()
55 {
56     scanf("%d",&n);
57     Build(1,n,1);
58     scanf("%d",&m);
59     while(m--){
60         int flag,a,b,X,p;
61         scanf("%d",&flag);
62         if(flag==1){
63             scanf("%d%d%d",&a,&b,&X); //【a-b】加上X;
64             Add(1,n,1,a,b,X);
65         }
66         else if(flag==2) ans=0,scanf("%d",&p),query(1,n,1,p),printf("%d
",ans);
67     }
68     return 0;
69 }
View Code
区间修改 单点查询

区间修改单点查询
