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

题解

区间更新，单点查询

#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;
		}
	}
}