[자료구조] 백준 1275번: 커피숍2 (C++)

https://www.acmicpc.net/problem/1275

1275번: 커피숍2

구간합 세그먼트 트리 문제였다. 이번 문제를 토대로 조금씩 세그먼트 트리에 대한 감이 잡히고 있다.

쿼리 선, 업데이트 후 방식으로 진행해주면 된다. x > y 인경우 swap 해주는 거 잊지 않기.

#include <iostream>
#define MAX (100000 + 1)
#define ll long long
using namespace std;

ll arr[MAX];
ll sgTree[MAX * 4];
int n, q;

ll sgInit(int start, int end, int node) {
	if (start == end) {
		return sgTree[node] = arr[start];
	}
	int mid = (start + end) / 2;
	return sgTree[node] = sgInit(start, mid, node * 2) + sgInit(mid + 1, end, node * 2 + 1);
}

void update(int start, int end, int node, int index, ll value) {
	if (index < start || index > end) return;
	if (start <= index && index <= end) {
		sgTree[node] += value;
	}
	if (start == end) return;
	int mid = (start + end) / 2;
	update(start, mid, node * 2, index, value);
	update(mid + 1, end, node * 2 + 1, index, value);
}

ll query(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return 0;
	if (left <= start && end <= right) return sgTree[node];
	int mid = (start + end) / 2;
	return query(start, mid, node * 2, left, right) + query(mid + 1, end, node * 2 + 1, left, right);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

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