[C++]구간 합 구하기(Segment) - 백준2042

문제

• 구간 합 구하기(백준2042)

풀이

문제 해석을 하자면,

• 문제를 읽어보면 알겠지만 전형적인 Segment Tree 문제이다.
• Segment Tree는 구간합을 구하는데 특화된 트리인데 특히 중간에 수의 변경이 빈번히 일어나는 경우에 더욱 성능이 좋은 자료구조이다.
• 따라서 이 문제는 Segment Tree를 구현하는 문제로 볼 수 있다.

풀이

• 이전에 Segment Tree를 구현한 코드가 있어서 해당 게시물 참고바람
• 추가로 생각할점은 b번째 수를 c로 바꾸는건 c-inArr[b-1] 로 바꿔야 한다는 의미란 것!!
• 또한, 추가로 배열 크기를 굉장히 크게 잡아야한다.
  • 2백만이면 충분할줄 알고 했다가 안풀려서 5백만으로 올리니까 정답처리 되었다.

코드

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

long long inArr[2000010];
long long outArr[5000010];

long long segmentBuild(int start, int end, int node) {
	if (start == end) {
		outArr[node] = inArr[start];
		return outArr[node]; // 종료시점
	}

	int mid = (start + end) / 2; // mid 구해서 왼, 오 구간 나눔
	outArr[node] = segmentBuild(start, mid, node * 2) + segmentBuild(mid + 1, end, node * 2 + 1);
	return outArr[node]; // 끝
}


// 구하는 합 구간 left, right
// node가 담당하는 구간 start, end
long long segmentSum(int start, int end, int node, long long left, long long right) {
	// 1. 겹치지 않는 경우 (왼쪽이거나 오른쪽 구간인경우)
	if ((left < start && right < start) || (left > end && right > end)) return 0;
	
	// 2. left, right가 start, end를 완전히 포함하는 경우
	if (left <= start && right >= end) return outArr[node];

	// 3. 나머지 경우 (자식 트리 탐색)
	int mid = (start + end) / 2;
	return segmentSum(start, mid, node * 2, left, right) + segmentSum(mid + 1, end, node * 2 + 1, left, right);
}

// node가 담당하는 구간 start, end
// 수정할 노드 index, 수정할 값 dif
void segmentUpdate(int start, int end, int node, long long index, long long dif) {
	// 1. 겹치지 않는 경우 (왼쪽이거나 오른쪽 구간인경우)
	if ((start < index && end < index) || (start > index && end > index)) return;
	// 2. left, right가 start, end를 완전히 포함하는 경우
	if (start <= index && index <= end) outArr[node] += dif;
	
	// 무조건 종료시점(무한루프 안걸리게)
	if (start == end) return;
	// 3. 나머지 경우 (자식 트리 탐색)
	int mid = (start + end) / 2;
	segmentUpdate(start, mid, node * 2, index, dif);
	segmentUpdate(mid + 1, end, node * 2 + 1, index, dif);
}

int N, M, K;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> K;

	for (int i = 0; i < N; i++) {
		cin >> inArr[i];
	}
	segmentBuild(0, N-1, 1); // outArr 수정(index 1부터 저장)

	long long a = 0;
	long long b = 0;
	long long c = 0;
	for (int i = 0; i < M + K; i++) {
		cin >> a >> b >> c;
		if (a == 1) {
			// b번째 수를 c로 바꾸는건 `c-inArr[b-1]` 로 바꿔야 한다는 의미이다.
			segmentUpdate(0, N-1, 1, b-1, c-inArr[b-1]);
			inArr[b - 1] = c; // b->c로 변환 (`c-inArr[b-1]` 에 사용되니까 바꿔줘야함)
		}
		else if (a == 2) {
			cout << segmentSum(0, N-1, 1, b-1, c-1) << '\n';
		}
	}

	return 0;
}

느낀점

생략