백준 2268번 c++ "수들의 합 7" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 세그먼트 트리 알고리즘을 이용하면 쉽게 풀 수 있다. 

특이한 점은 처음 값들이 주어지지 않고 입력값을 통해 순차적으로 트리를 갱신해줘야 된다는 점이다.

아래는 코드 해설이다.

[코드 해설]

 

• 세그먼트 트리 초기화
  Init_Segment_Tree 함수는 입력 데이터 크기 N에 기반하여 세그먼트 트리의 높이와 크기를 계산하고 트리를 초기화한다.
  • 트리의 높이는 ⌈log⁡2(N)⌉\lceil \log_2(N) \rceil⌈log2​(N)⌉로 계산된다.
  • 트리의 전체 크기는 2(트리 높이+1)2^{(\text{트리 높이} + 1)}2(트리 높이+1)로 설정된다.
  • 트리는 vector 자료구조로 구현되며, 초기 값으로 0으로 채워진다.
• 쿼리를 통한 구간 합 계산
  Query 함수는 특정 구간의 합을 계산한다.
  • 시작점 start와 끝점 end를 세그먼트 트리의 리프 노드 인덱스에 맞게 변환한다.
  • 두 인덱스가 교차할 때까지 반복하며, 현재 범위에서 합을 구한다.
    • start가 홀수라면, 해당 노드를 더하고 인덱스를 증가시킨다.
    • end가 짝수라면, 해당 노드를 더하고 인덱스를 감소시킨다.
  • start와 end를 부모 노드로 이동시키며, 합산 과정을 반복한다.
  • 최종적으로 구간의 합을 반환한다.
• 트리 값 업데이트
  Update_Tree 함수는 특정 인덱스의 값을 갱신하고, 그에 따라 세그먼트 트리를 수정한다.
  • 입력으로 주어진 인덱스를 리프 노드의 인덱스에 맞게 변환한다.
  • 기존 값과 새로운 값의 차이를 계산하고, 해당 차이를 모든 관련 부모 노드에 반영한다.
  • 인덱스를 부모로 이동시키며 갱신을 반복한다.
• 게임 진행
  Game_Start 함수는 세그먼트 트리 초기화 이후 입력 데이터를 처리하며 명령을 수행한다.
  • 사용자 입력으로 flag, x, y 값을 받는다.
    • flag가 0인 경우, Query를 통해 구간 [x, y]의 합을 계산하고 출력한다.
    • flag가 1인 경우, Update_Tree를 통해 인덱스 x의 값을 y로 갱신한다.
• 입력 및 실행
  • Input 함수는 전체 데이터의 크기 N과 명령의 개수 M을 입력받는다.
  • Game_Start 함수는 초기화와 명령 처리를 순차적으로 실행한다

 

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int N, M;
vector<long> arr;
vector<long> tree;
int treeHeight, treeSize, leftStartIdx;

void Input() {
	cin >> N >> M;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

}

void Init_Segment_Tree() {
	treeHeight = (int)ceil(log2(N));
	treeSize = (1 << (treeHeight + 1));
	leftStartIdx = treeSize / 2;

	tree.resize(treeSize);

	for (int i = 0; i < N; i++) {
		tree[i + leftStartIdx] = arr[i];
	}

	for (int i = leftStartIdx - 1; i > 0; i--) {
		tree[i] = tree[i * 2] + tree[i * 2 + 1];
	}
}
long Query(int start, int end) {
	
	start += leftStartIdx;
	end += leftStartIdx;

	long sum = 0;

	while (start <= end) {
		if (start % 2 == 1) {
			sum += tree[start];
			start++;
		}
		if (end % 2 == 0) {
			sum += tree[end];
			end--;
		}

		start /= 2;
		end /= 2;
	}

	return sum;
}
void Update_Tree(int idx, int value) {
	idx += leftStartIdx;
	long nowValue = tree[idx];
	long diff = value - nowValue;

	while (idx != 0) {
		tree[idx] += diff;
		idx /= 2;
	}
}

void Game_Start() {
	Init_Segment_Tree();

	for (int i = 0; i < M; i++) {
		int x1, y1, a, b;
		cin >> x1 >> y1 >> a >> b;

		int  x = min(x1, y1);
		int y = max(x1, y1);

		cout << Query(x - 1, y - 1) << '\n';
		Update_Tree(a - 1, b);
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	Input();
	Game_Start();
}