백준 1275번 커피숍2 문제풀이(C++)

백준 1275번 커피숍2

아이디어

x y a b의 형식으로 x~y까지의 합을 구하여라, a번째 수를 b로 바꾸어라 라는 뜻의 데이터가 주어진다.

x ~ y까지의 합 => 세그먼트트리 , 펜윅트리, 누적합

a번째 수를 b로 바꾸어라 => 세그먼트트리 , 펜윅트리, 누적합

(1 ≤ N, Q ≤ 100,000) => 100,000까지의 비교적 적은 범위 => lazy 제외, 누적합(시간복잡도) 제외

∴ 세그먼트 트리, 펜윅트리 둘 중 하나 선택 => 구현하기 쉬운 펜윅트리 사용

---

※ x > y 인 경우 조심

if (x > y)
	swap(x, y);

로 x > y인 문제 해결

문제풀이

#include<bits/stdc++.h>
using namespace std;
#define MAX 100'000 + 10
typedef long long ll;
ll num[MAX];
int n, q;
ll sum(int idx) {
	ll _sum = 0L;
	while (idx) {
		_sum += num[idx];
		idx -= (idx & -idx);
	}
	return _sum;
}
void update(int idx, ll diff) {
	while (idx <= n + 1) {
		num[idx] += diff;
		idx += (idx & -idx);
	}
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int num; cin >> num;
		update(i, num);
	}
	while (q--) {
		int x, y, a, b; cin >> x >> y >> a >> b;
		if (x > y)
			swap(x, y);
		cout << sum(y) - sum(x - 1) << '\n';
		ll node = sum(a) - sum(a - 1);
		update(a, b - node);
	}
	return 0;
}