[백준] 1275번 : 커피숍2

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 수열의 특정 구간 합을 구하는 문제로, 세그먼트 트리 알고리즘을 사용하여 풀이했다.

1) 수열을 저장할 datas, 구간합 트리를 저장할 tree 배열을 선언한다. 이 때 구간합 트리의 크기는 수열 배열의 최대 크기의 4배 이상으로 설정한다.

2) 수의 개수 n과 턴의 개수 q를 입력 받아 저장하고, n개의 수를 입력받아 datas에 저장한다.

3) init() 함수를 통해 구간합 트리를 초기화 한다.

• 최상위 노드부터 시작해 데이터 범위를 반씩 분할하여 구간합을 저장하는 방식으로 트리를 채운다. 재귀를 통해 가장 작은 범위의 값을 구해, 그 값들로 더 큰 범위의 값을 구한다.
• 현재 순서 노드의 값 = 왼쪽 자식 노드의 값 + 오른쪽 자식 노드의 값
• 더 이상 분할할 수 없을 때(범위 내에 수가 하나 뿐일 때) 해당 수를 현재 순서 노드의 값으로 설정하고 반환한다.

4) q 만큼의 (합 구하기, 수 바꾸기)를 실행한다.

• sum() 함수를 통해 현재 순서에서 구해야하는 범위의 구간합을 구하고 이를 출력한다.
  • 범위 밖에 있는 경우 0을 반환한다.
  • 범위 안에 있는 경우 현재 순서 노드의 구간합을 반환한다.
  • 범위에 걸쳐 있는 경우 현재 범위의 절반으로 나누어 합을 구한다.
  • 이 때 반드시 x < y 인 것은 아니므로, x < y일 때와 x > y일 때 매개변수를 다르게 입력한다.
• update() 함수를 통해 특정 인덱스의 수를 다른 수로 변경한다.
  • 범위 밖에 있는 경우 무시한다.
  • 범위 안에 있으면 현재 순서 노드에 변경 값을 더해주고, 하위 노드로 내려가며 범위 내에 있는 다른 원소도 갱신한다.
  • update() 함수 실행 이후 datas의 특정 인덱스 값도 변경해주어야 한다.

🖥️ 풀이 코드

#include <iostream>
#include <algorithm>
using namespace std;

long long tree[400004];
long long datas[100001];
int n, q;

long long init(int start, int end, int node)
{
	if (start == end) return tree[node] = datas[start];
	int mid = (start + end) / 2;
	return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

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

void update(int start, int end, int node, int index, long long dif)
{
	if (index < start || index > end) return;
	tree[node] += dif;
	if (start == end) return;
	int mid = (start + end) / 2;
	update(start, mid, node * 2, index, dif);
	update(mid + 1, end, node * 2 + 1, index, dif);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> datas[i];

	init(1, n, 1);
	for (int i = 0; i < q; i++)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		if(a < b)
			cout << sum(1, n, 1, a, b) << '\n';
		else
			cout << sum(1, n, 1, b, a) << '\n';
		long long calcNum = d - datas[c];
		update(1, n, 1, c, calcNum);
		datas[c] = d;
	}
}