[백준/BOJ] 백준 1275번 : 커피숍2

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

1275번: 커피숍2

bottom-up 세그먼트 트리를 구현하여 문제를 해결했다.

 

코드

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

long long n, q;
vector<long long> number;
vector<long long> sgmtt(200000); //bottom-up 세그먼트의 크기는 2*n으로 충분하다

//bottom-up 세그먼트로 구현

void MakeSgmtt()
{
	for (int i = 0; i < n; i++)
	{
		sgmtt[n + i] = number[i];
	}

	for (int i = n - 1; i >= 1; i--)
	{
		sgmtt[i] = sgmtt[i * 2] + sgmtt[i * 2 + 1];
	}
}

void UpdateSgmtt(int index, long long value)
{
	sgmtt[n + index] = value;
	for (int i = (n + index) / 2; i >= 1; i = i / 2)
	{
		sgmtt[i] = sgmtt[i * 2] + sgmtt[i * 2 + 1];
	}
}

long long QuerySgmtt(int left, int right)
{
	long long ret = 0;

	left = n + left;
	right = n + right;

	while (left < right)
	{
		//left가 오른쪽 자식일때 -> 왼쪽 자식은 범위에 포함되지 않는다 -> 부모 노드 정보가 필요하지 않음
		if (left % 2 == 1)
		{
			ret += sgmtt[left];
			left++;
		}

		//right가 왼쪽 자식일때 -> 오른쪽 자식은 범위에 포함되지 않는다 -> 부모 노드 정보가 필요하지 않음
		if (right % 2 == 0)
		{
			ret += sgmtt[right];
			right--;
		}

		//left, right모두 부모 노드로 올라가기
		left /= 2;
		right /= 2;
	}

	if (left == right)
		ret += sgmtt[left];

	return ret;
}

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

	cin >> n >> q;

	for (int i = 0; i < n; i++)
	{
		long long input;
		cin >> input;

		number.push_back(input);
	}

	MakeSgmtt();

	for (int i = 0; i < q; i++)
	{
		long long x, y, a, b;
		cin >> x >> y >> a >> b;

		//시작 인덱스를 0으로 했다
		x--;
		y--;
		a--;

		cout << QuerySgmtt(min(x, y), max(x, y)) << "\n";
		UpdateSgmtt(a, b);
	}

	return 0;
}