문제

문제 링크 : https://www.acmicpc.net/problem/16975

풀이

레이지 세그먼트 트리를 구현하고 문제에서 시키는 대로 입력을 받아 출력하면 되는 문제이다. 풀이 코드는 다음과 같다.

#include <bits/stdc++.h>

using namespace std;
const int MAX = 100000;

long long tree[MAX * 4 + 100];
long long lazy[MAX * 4 + 100];
long long a[MAX + 10];

int n, m;

void propagation(int node, int s, int e) {
	if (lazy[node] == 0) return;
	tree[node] += lazy[node] * (e - s + 1);
	if (s != e) {
		lazy[node * 2] += lazy[node];
		lazy[node * 2 + 1] += lazy[node];
	}
	lazy[node] = 0;
}

void init(int node, int s, int e) {
	if (s == e) {
		tree[node] = a[s];
		return;
	}
	int mid = (s + e) / 2;
	init(node * 2, s, mid);
	init(node * 2 + 1, mid + 1, e);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

long long query(int node, int s, int e, int l, int r) {
	propagation(node, s, e);
	if (r < s || e < l) return 0;
	if (l <= s && e <= r) return tree[node];
	int mid = (s + e) / 2;
	long long left = query(node * 2, s, mid, l, r);
	long long right = query(node * 2 + 1, mid + 1, e, l, r);
	return left + right;
}

void update(int node, int s, int e, int l, int r, long long x) {
	propagation(node, s, e);
	if (r < s || e < l) return;
	if (l <= s && e <= r) {
		lazy[node] += x;
		propagation(node, s, e);
		return;
	}
	int mid = (s + e) / 2;
	update(node * 2, s, mid, l, r, x);
	update(node * 2 + 1, mid + 1, e, l, r, x);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	init(1, 1, n);

	cin >> m;

	for (int i = 0; i < m; i++) {
		int cmd;
		cin >> cmd;
		if (cmd == 1) {
			int p, q;
			long long r;
			cin >> p >> q >> r;
			update(1, 1, n, p, q, r);
		}
		else {
			int x;
			cin >> x;
			cout << query(1, 1, n, x, x) << '\n';
		}
	}

	return 0;
}