1081 线段树练习 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

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发与安全

从零开始学C++之从C到C++(一):const与#define、结构体对齐、函数重载name mangling、new/delete 等

一、bool 类型 逻辑型也称布尔型,其取值为true(逻辑真)和false(逻辑假),存储字节数在不同编译系统中可能有所不同,VC++中为1个字节。 声明方式...

20400
来自专栏编程坑太多

Python 字典

13640
来自专栏阿杜的世界

Java泛型基础(一)目的泛型类总结

利用Java开发的时候,肯定会有一个类持有另一个或几个类的情况,在编写一些比较基础的组件,例如缓存操作组件,这类组件的逻辑差不多,但是希望能够处理不同的类型。

7210
来自专栏猿人谷

第一个只出现一次的字符

题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。 看到这道题时,最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某...

19870
来自专栏CVer

排序算法 | 冒泡排序(含C++/Python代码实现)

排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。排序算法有很多,本文将介绍最经典的排序算法:冒泡排序...

16620
来自专栏IT笔记

京东2017校园招聘笔试真题(希尔排序)

对关键字{10,20,8,25,35,6,18,30,5,15,28}序列进行希尔排序,取增量d =5时,排序结果为( ) A. {6,18,8,5,15,10...

32050
来自专栏炉边夜话

java 异常处理学习笔记

<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

12520
来自专栏数据结构与算法

洛谷P2759 奇怪的函数(log 二分)

7710
来自专栏容器云生态

awk-grep-sed简单使用总结(正则表达式的应用)

正则表达式: 匹配一组字符: #[ns]a.\.xls  //[]用于限定字符;“.”用于匹配任意字符; \.用于转义"." 匹配到s/na*.xls  [n...

30790
来自专栏lgp20151222

排序算法对比,步骤,改进,java代码实现

发现是时候总结一番算法,基本类型的增删改查的性能对比,集合的串并性能的特性,死记太傻了,所以还是写在代码里,NO BB,SHOW ME THE CODE!

10520

扫码关注云+社区

领取腾讯云代金券