[백준][C++] 1275: 커피숍2

문제 링크: https://www.acmicpc.net/problem/1275

 

세그먼트 트리 문제입니다. 구간합 구하는 세그먼트 트리 쓰면 됩니다.

세그먼트 트리는 안보고 짜는거 포기했습니다. 제 기억력은 여기까지인가봅니다.

 

참고로 합이 int 범위 넘어갈 수 있으니 long long 으로 만들어야합니다.

그리고 x y 범위에 함정이 있으니 그거만 좀 체크해주면 됩니다. 힌트에 친절하게 써있습니다.

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;



// RSQ
vector<ll> tree;

// node -> 1
// [node_l, node_r] -> [0, n-1]

ll init(vector<ll>& arr, int node_l, int node_r, int node) {
	if (node_l == node_r) return tree[node] = arr[node_l];

	int mid = (node_l + node_r) / 2;
	return tree[node] = init(arr, node_l, mid, node * 2) + init(arr, mid + 1, node_r, node * 2 + 1);
}

ll query(const int& l, const int& r, int node_l, int node_r, int node) {
	if (r < node_l || node_r < l) return 0;	// 구간과 겹치지 않는 경우
	if (l <= node_l && node_r <= r) return tree[node];	// node 표현범위가 arr[l, r]에 포함되는 경우

	int mid = (node_l + node_r) / 2;
	return query(l, r, node_l, mid, node * 2) + query(l, r, mid + 1, node_r, node * 2 + 1);
}

ll update(const int& idx, const ll& newValue, int node_l, int node_r, int node) {
	if (idx < node_l || node_r < idx) return tree[node];	// 구간과 겹치지 않는 경우
	if (node_l == node_r) return tree[node] = newValue;		// leaf

	int mid = (node_l + node_r) / 2;
	return tree[node] = update(idx, newValue, node_l, mid, node * 2) + update(idx, newValue, mid + 1, node_r, node * 2 + 1);
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n, q;
	cin >> n >> q;

	vector<ll> arr(n);
	for (auto& c : arr)
		cin >> c;

	tree.resize(4 * n);
	init(arr, 0, n - 1, 1);

	while (q--) {
		int x, y, a, b;
		cin >> x >> y >> a >> b;

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

		cout << query(x, y, 0, n - 1, 1) << '\n';
		update(a, b, 0, n - 1, 1);
	}

	return 0;
}