백준 11143 c++ "Beads" -PlusUltraCode-

 

#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 <= start) {
		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();
}

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

 

[필자 사고]

기본적인 세그먼트 트리 기초 문제이다. 세그먼트 트리 설계 과정을 알고 있다면

실수 없이 쉽게 풀 수 있다.

다만 주어지는 쿼리 index 범위가 항상 작은거에서부터 입력된다는 고정생각을 벗어나야 된다.

[코드 해설]

주요 코드 설명

1. 입력 데이터 처리 및 초기화
   • T: 테스트 케이스 수.
   • 각 테스트 케이스에서:
     • B: 배열의 크기.
     • P: 업데이트 연산(‘P’로 표시)의 수.
     • Q: 쿼리 연산(‘Q’로 표시)의 수.
   • 세그먼트 트리 tree는 각 테스트 케이스마다 초기화됩니다.
2. 세그먼트 트리 기본 연산
   • 구간 합 쿼리 (Query 함수):
     • 주어진 구간 [left, right]에서 합을 계산합니다.
     • 현재 노드의 구간 [s, e]가 완전히 쿼리 구간에 포함되면 해당 노드의 값을 반환합니다.
     • 구간이 겹치지 않으면 0을 반환합니다.
     • 구간이 일부만 겹치는 경우, 왼쪽 자식 노드와 오른쪽 자식 노드를 재귀적으로 호출하여 결과를 합산합니다.
   • 값 업데이트 (Update 함수):
     • 배열의 특정 인덱스 idx에 diff만큼 값을 추가합니다.
     • 리프 노드까지 내려가 값을 갱신한 후, 재귀적으로 올라오면서 부모 노드의 값을 갱신합니다.
3. 테스트 케이스 처리 (Game_Start 함수)
   • 각 테스트 케이스마다:
     • 배열 크기 B에 따라 세그먼트 트리를 초기화합니다.
     • P + Q개의 연산을 처리합니다:
       • ‘P’ 연산 (Update):
         • a 인덱스에 b 값을 더합니다.
         • Update 함수 호출.
       • ‘Q’ 연산 (Query):
         • 구간 [a, b]의 합을 계산하여 출력합니다.
         • Query 함수 호출.
4. 입출력 최적화
   • ios::sync_with_stdio(false)와 cin.tie(0)를 사용하여 빠른 입출력을 처리합니다.

[소스 코드]