[BOJ 1275 // C++] 커피숍2

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1275번 문제인 커피숍2이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1275

1275번: 커피숍2

이 문제에서는 배열이 주어지고, 배열의 구간합을 구한 뒤 수 하나를 다른 수로 바꾸는 쿼리가 반복하여 주어진다.

숫자가 계속 바뀔 수 있으므로, 세그먼트트리를 이용하여 이 문제를 푸는 것이 좋다.

 

숫자를 다른 수로 변경할 때, 원래 배열에 있던 수와 새로 바꾸려는 수의 차이만큼 업데이트를 해주면 된다는 점을 잊지 말자. 또한, 이 과정에서 원래 배열의 값도 갱신해주는 것을 잊지 말자.

 

아래는 제출한 소스코드이다.

#include <iostream>
typedef long long ll;

using namespace std;

ll arr[100001];
ll seg[262145];

ll init(int L, int R, int sI) {
	if (L == R) return seg[sI] = arr[L];
	return seg[sI] = init(L, (L + R) / 2, sI * 2) + init((L + R) / 2 + 1, R, sI * 2 + 1);
}

void update(int L, int R, int qI, ll qVal) {
	int sI = 1;
	while (L != R) {
		seg[sI] += qVal;
		int mid = (L + R) / 2;
		if (qI <= mid) {
			R = mid;
			sI = sI * 2;
		}
		else {
			L = mid + 1;
			sI = sI * 2 + 1;
		}
	}
	seg[sI] += qVal;
}

ll query(int L, int R, int qL, int qR, int sI) {
	if (qR < L || R < qL) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return query(L, (L + R) / 2, qL, qR, sI * 2) + query((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

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

	int N, Q; cin >> N >> Q;
	
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

	init(1, N, 1);

	for (int q = 0; q < Q; q++) {
		int x, y, a; ll b; cin >> x >> y >> a >> b;
		if (x > y) swap(x, y);
		cout << query(1, N, x, y, 1) << '\n';
		update(1, N, a, b - arr[a]);
		arr[a] = b;
	}
}