백준 25778 c++ "House Prices Going Up" -PlusUltraCode-

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

 

 

[필자 사고]

이 문제는 세그먼트 트리 합 관련 기본 문제이다.

조심해야 될 점은 없었던거 같고

항상 세그먼트 질의문에 a,b중 작은값 큰값 조심하자.

[코드 해설]

1. 입력 함수 (Input)
   • 사용자로부터 입력을 받는 역할을 수행한다.
   • 먼저 N (배열의 크기)을 입력받고, 그에 맞게 세그먼트 트리(tree)와 입력 배열(arr)을 크기에 맞게 초기화한다.
   • 이후 배열의 요소들을 차례로 입력받아 arr에 저장한다.
2. 세그먼트 트리 초기화 함수 (Init_Tree)
   • 세그먼트 트리를 구성하는 함수이다.
   • 재귀적으로 호출되며, 리프 노드에는 입력 배열의 값을 저장하고, 부모 노드에는 자식 노드들의 합을 저장한다.
   • node, start, end를 매개변수로 받아 현재 세그먼트 트리의 노드와 해당 구간을 처리한다.
3. 값 갱신 함수 (Update)
   • 특정 인덱스(idx)의 값을 업데이트하는 함수이다.
   • 업데이트된 값을 기반으로 해당 인덱스를 포함하는 모든 부모 노드들의 값을 재계산한다.
   • start와 end로 현재 노드가 관리하는 구간을 나타내며, diff는 변경된 값을 나타낸다.
4. 구간 합 조회 함수 (Query)
   • 특정 구간 (left, right)의 합을 구하는 함수이다.
   • 현재 노드가 관리하는 구간 (start, end)이 요청한 구간에 포함되면 해당 노드의 값을 반환한다.
   • 요청한 구간과 겹치지 않는 경우 0을 반환하고, 겹치는 경우 왼쪽과 오른쪽 자식을 재귀적으로 호출하여 결과를 합산한다.
5. 게임 시작 함수 (Game_Start)
   • 세그먼트 트리를 초기화한 후, 사용자로부터 명령을 반복적으로 입력받아 처리한다.
   • 명령은 두 가지로 구성된다:
     • 'R': 구간 합 조회 명령으로, Query를

호출하여 특정 구간의 합을 출력한다.
- 'U': 값 갱신 명령으로, Update를 호출하여 배열의 특정 인덱스 값을 갱신하고, 세그먼트 트리도 업데이트한다.

1. 메인 함수 (main)
   • 입출력 속도를 향상시키기 위해 ios::sync_with_stdio와 cin.tie, cout.tie를 설정한다.
   • 입력을 받고, 게임 시작 함수(Game_Start)를 호출하여 프로그램의 실행을 시작한다.

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<long> tree;
vector<long> arr;
int M;

void Input() {
	cin >> N;
	tree.resize(4 * N + 1);
	arr.resize(N + 1);

	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
}

void Init_Tree(int node, int start, int end) {
	if (start == end) {
		tree[node] = arr[start];
		return;
	}
	int mid = (start + end) / 2;

	Init_Tree(node * 2, start, mid);
	Init_Tree(node * 2 + 1, mid + 1, end);

	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void Update(int node, int start, int end, int idx, long diff) {
	if (idx < start || end < idx)return;

	if (start == end) {
		tree[node] += diff;
		return;
	}

	int mid = (start + end) / 2;
	if (idx <= mid) {
		Update(node * 2, start, mid, idx, diff);
	}
	else {
		Update(node * 2 + 1, mid + 1, end, idx, diff);
	}

	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

long Query(int node, int start, int end, int left, int right) {
	if (left <= start && end <= right) {
		return tree[node];
	}

	if (end < left || right < start)return 0;

	int mid = (start + end) / 2;
	return Query(node * 2, start, mid, left, right) +
		Query(node * 2 + 1, mid + 1, end, left, right);
}

void Game_Start() {
	Init_Tree(1, 1, N);

	cin >> M;
	for (int i = 0; i < M; i++) {
		char ch; int a, b;
		cin >> ch;
		cin >> a >> b;
		if (ch == 'R') {
			cout << Query(1, 1, N, a, b) << '\n';
		}
		else {
			Update(1, 1, N, a, b);
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Input();
	Game_Start();
}