首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >1081 线段树练习 2 单点查询及区间修改

1081 线段树练习 2 单点查询及区间修改

作者头像
attack
发布2018-04-13 15:04:20
6220
发布2018-04-13 15:04:20
举报

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

3

1

2

3

2

1 2 3 2

2 3

样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

数据范围

1<=n<=100000

1<=q<=100000

分类标签 Tags 点此展开
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int n,m;
 7 const int MAXN=100001;
 8 int ans=0;
 9 struct node
10 {
11     int l,r,w,f;
12 }tree[MAXN*4];
13 inline void updata(int k)
14 {
15     tree[k].w=tree[k*2].w+tree[k*2+1].w;
16 }
17 inline void build(int k,int ll,int rr)
18 {
19     tree[k].l=ll;tree[k].r=rr;
20     if(tree[k].l==tree[k].r)
21     {
22         scanf("%d",&tree[k].w);
23         return ;
24     }
25     int m=(ll+rr)/2;
26     build(k*2,ll,m);
27     build(k*2+1,m+1,rr);
28     updata(k);
29 }
30 
31 inline void down(int k)
32 {
33     tree[k*2].f+=tree[k].f;
34     tree[k*2+1].f+=tree[k].f;
35     tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);
36     tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);
37     tree[k].f=0;
38 }
39 inline void interval_change(int k,int ll,int rr,int v)
40 {
41     if(tree[k].l>=ll&&tree[k].r<=rr)
42     {
43         tree[k].w+=(tree[k].r-tree[k].l+1)*v;
44         tree[k].f+=v;
45         return ;
46     }
47     if(tree[k].f)    down(k);
48     int m=(tree[k].l+tree[k].r)/2;
49     if(ll<=m)    interval_change(k*2,ll,rr,v);
50     if(rr>m)    interval_change(k*2+1,ll,rr,v);
51     updata(k);
52 }
53 inline void point_ask(int k,int p)
54 {
55     if(tree[k].l==tree[k].r)
56     {
57         ans=tree[k].w;
58         return ;
59     }
60     if(tree[k].f)    down(k);
61     int m=(tree[k].l+tree[k].r)/2;
62     if(p<=m)    point_ask(k*2,p);
63     else point_ask(k*2+1,p);
64 }
65 int main()
66 {
67     scanf("%d",&n);
68     build(1,1,n);
69     scanf("%d",&m);
70     for(int i=1;i<=m;i++)
71     {
72         int how;
73         scanf("%d",&how);
74         if(how==1)//区间修改
75         {
76             int x,y,v;
77             scanf("%d%d%d",&x,&y,&v);
78             interval_change(1,x,y,v);
79         }
80         else//单点查询 
81         {
82             int p;
83             scanf("%d",&p);
84             ans=0;
85             point_ask(1,p);
86             printf("%d\n",ans);
87         } 
88     }
89     return 0;
90 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-05-08 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1081 线段树练习 2
    • 分类标签 Tags 点此展开
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档