[BOJ_16975_RN] 수열과 쿼리 21 Problem Solving

문제 출처 : https://www.acmicpc.net/problem/16975

문제 해결에 필요한 알고리즘 : Segment Tree Lazy Propagation

해설 / 시간복잡도

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

이 조건에서 1번 문제는 Segment Tree를 Lazy하게 업데이트 하면  으로 구간 덧셈을 업데이트 할 수 있다. 또 2번 조건도 Segment Tree 검색도 으로 검색이 가능하다. 그래서  으로 해결할 수 있다.

수열과 쿼리 21 코드 [ C ]

#include <stdio.h>
#define LEFT(I) (I << 1)
#define RIGHT(I) ((I << 1) + 1)
int ar[100001], seg[1 << 19], lazy[1 << 19];
void lazyUpdate(int I, int l, int r) {
	if (lazy[I]) {
		seg[I] += (r - l + 1) * lazy[I];
		if (r - l) {
			lazy[LEFT(I)] += lazy[I];
			lazy[RIGHT(I)] += lazy[I];
		}
		lazy[I] = 0;
	}
}
void update(int I, int l, int r, int x, int y, int k) {
	lazyUpdate(I, l, r);
	if (l > y || r < x) return;
	if (l >= x && r <= y) {
		lazy[I] += k;
		lazyUpdate(I, l, r);
		return;
	}
	int mid = l + r >> 1;
	update(LEFT(I), l, mid, x, y, k);
	update(RIGHT(I), mid + 1, r, x, y, k);
	seg[I] = seg[LEFT(I)] + seg[RIGHT(I)];
}
int find(int I, int l, int r, int x, int y) {
	lazyUpdate(I, l, r);
	if (l > y || r < x) return 0;
	if (l >= x && r <= y) {
		return seg[I];
	}
	int mid = l + r >> 1;
	return find(LEFT(I), l, mid, x, y) + find(RIGHT(I), mid + 1, r, x, y);
}
int main() {
	char in[1 << 18], out[1 << 18];
	setvbuf(stdin, in, _IOFBF, sizeof in);
	setvbuf(stdout, out, _IOFBF, sizeof out);
	
	int i, n, m;
	scanf("%d", &n);
	for (i = 0; i < n; ++i) {
		scanf("%d", ar + i + 1);
		update(1, 1, n, i + 1, i + 1, ar[i + 1]);
	}
	scanf("%d", &m);
	for (i = m; i--; ) {
		int t;
		scanf("%d", &t);
		if (t - 2) {
			int l, r, x;
			scanf("%d%d%d", &l, &r, &x);
			update(1, 1, n, l, r, x);
		} else {
			int x;
			scanf("%d", &x);
			printf("%d\n", find(1, 1, n, x, x));
		}
	}
	return 0;
}