[ BOJ ] 16975 : 수열과 쿼리 21 ( PLATINUM 4 ) / C

문제

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다.
• 2 x: Ax 를 출력한다.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000,000)

셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

넷째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. 1번 쿼리의 경우 1 ≤ i ≤ j ≤ N, -1,000,000 ≤ k ≤ 1,000,000 이고, 2번 쿼리의 경우 1 ≤ x ≤ N이다. 2번 쿼리는 하나 이상 주어진다.

출력

2번 쿼리가 주어질 때마다 출력한다.

풀이 과정

구간 합이 아닌 특정 인덱스의 노드만 불러오는 느리게 갱신되는 세그먼트 트리를 이용하였다.

#include <stdio.h>

int arr[100001];
long long int tree[400004];
long long int lazy[400004];

long long int init(int start, int end, int idx) {
	if (start == end) {
		tree[idx] = arr[start];
		return tree[idx];
	}
	else {
		int mid = (start + end) / 2;
		tree[idx] = init(start, mid, idx * 2) + init(mid + 1, end, idx * 2 + 1);
		return tree[idx];
	}
}

void update_lazy(int start, int end, int idx) {
	if (lazy[idx] != 0) {
		tree[idx] += (end - start + 1) * lazy[idx];
		if (start != end) {
			lazy[idx * 2] += lazy[idx];
			lazy[idx * 2 + 1] += lazy[idx];
		}
		lazy[idx] = 0;
	}
}

void update_range(int start, int end, int idx, int left, int right, int value) {
	update_lazy(start, end, idx);
	if (end < left || right < start) return;
	if (left <= start && end <= right) {
		tree[idx] += (end - start + 1) * value;
		if (start != end) {
			lazy[idx * 2] += value;
			lazy[idx * 2 + 1] += value;
		}
		return;
	}

	int mid = (start + end) / 2;
	update_range(start, mid, idx * 2, left, right, value);
	update_range(mid + 1, end, idx * 2 + 1, left, right, value);
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

long long int query(int start, int end, int idx, int what) {
	update_lazy(start, end, idx);

	if (what < start || end < what) return 0;
	if (start == end) return tree[idx];

	int mid = (start + end) / 2;
	return query(start, mid, idx * 2, what) + query(mid + 1, end, idx * 2 + 1, what);
}

int main(void) {
	int n, q;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &arr[i]);

	init(0, n - 1, 1);

	scanf("%d", &q);
	for (int i = 0; i < q; i++) {
		int mode = 0;
		scanf("%d", &mode);
		if (mode == 1) {
			int n1, n2, n3;
			scanf("%d %d %d", &n1, &n2, &n3);
			update_range(0, n - 1, 1, n1 - 1, n2 - 1, n3);
		}
		else {
			int n1;
			scanf("%d", &n1);
			printf("%lld\n", query(0, n - 1, 1, n1 - 1));
		}
	}
	return 0;
}