[백준] 1275번 커피숍2 C++ 코드

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;

ll n, q, num[100003], x, y, a, b;
vector<ll> tree;

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

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

void update(int s, int e, int node, int idx, ll val) {
	if (idx > e || idx < s) return;
	if (s == e) {
		num[s] = val;
		tree[node] = val;
	}
	else {
		int mid = (s + e) / 2;
		update(s, mid, node * 2, idx, val);
		update(mid + 1, e, node * 2 + 1, idx, val);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

void FASTIO() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main() {
	FASTIO();
	cin >> n >> q;
	tree.resize(4 * n);
	for (int i = 0; i < n; i++) cin >> num[i];
	init(0, n - 1, 1);
	// x~y의 수를 구하고, a번째 수를 b로 바꿔라
	for (int i = 0; i < q; i++) {
		cin >> x >> y >> a >> b;
        // x <= y 임이 보장되지 않았음에 주의
		if (x > y) {
			int tmp = x;
			x = y;
			y = tmp;
		}
		cout << query(0, n - 1, x - 1, y - 1, 1) << '\n';
		update(0, n - 1, 1, a - 1, b);
	}
	return 0;
}

풀이

세그먼트 트리 기본 문제로 볼 수 있다. 펜윅 트리로도 해결할 수 있을 거 같아서 있다가 해결해보려고 한다. 주의할 점은 x <= y가 보장된 게 아니라는 점이다. 다른 문제 풀 때도 이를 잘 고려해서 실수하지 않도록 해야겠다.