我的博客

codevs 1081 线段树练习 2

目录
  1. 题解

题目描述 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

题解

区间更新,单点查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
using namespace std;

int t[131072<<1];
int lt, rt, cnt;

void update(int f, int l, int r) {
if (l == r) {
if (l >= lt && l <= rt) {
t[f] += cnt;
}
}
else {
int mid = l + r >> 1, ls = f << 1, rs;
rs = ls | 1;
if (l >= lt && r <= lt){
t[f] += cnt;
}
else {
if (l > rt || r < lt) return;
if (lt <= mid)
update(ls, l, mid);
if (rt > mid)
update(rs, mid+1, r);
}
}
}

int query(int f, int l, int r) {
if (l==r) return t[f];
int ans = t[f];
int mid = l + r >> 1, ls = f << 1, rs;
rs = ls | 1;
if (lt > mid) {
return t[f] + query(rs, mid+1, r);
}
else {
return t[f] + query(ls, l, mid);
}
}

int main() {
ios::sync_with_stdio(false);
int n, m;
cin >> n;
int size = 1;
while (size < n) size <<= 1;
for (int i = 0; i < n; i++) {
cin >> t[i+size];
}
cin >> m;
while (m--) {
int x;
cin >> x;
if (x == 1) {
cin >> lt >> rt >> cnt;
update(1, 1, size);
}
else {
cin >> lt;
cout << query(1, 1, size) << endl;
}
}
}

评论无需登录,可以匿名,欢迎评论!