백준 1275번 커피숍2 C++

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

 

세그먼트 트리를 이용하여 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

ll MakeTree(int start, int end, int node, vector<ll>& v, vector<ll>& tree) {
	if (start == end) return tree[node] = v[start];
	ll mid = (start + end) / 2;
	return tree[node] = MakeTree(start, mid, node * 2, v, tree) +
		MakeTree(mid + 1, end, node * 2 + 1, v, tree);
}

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

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

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

	int n, q;
	cin >> n >> q;
	vector<ll> v(n);
	vector<ll> tree(n * 4);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	MakeTree(0, n - 1, 1, v, tree);
	
	for (int i = 0; i < q; i++) {
		int x, y, a, b;
		cin >> x >> y >> a >> b;
		int start = min(x - 1, y - 1);
		int end = max(x - 1, y - 1);
		a -= 1;
		ll change = b - v[a];
		v[a] = b;
		cout << GetSum(0, n - 1, 1, start, end, tree) << "\n";
		Update(0, n - 1, 1, a, change, tree);
	}
};