[알고리즘][C++] 세그먼트 트리

백준 2042: 구간 합 구하기

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

2042번: 구간 합 구하기

 

접근 방향 및 디버깅

"범위" 별 재귀 핸들링에 집중

[1] 찾는 범위를 미포함하는 호출일 때

[2] 찾는 범위를 전부 포함하는 호출일 때

[3] 찾는 범위를 일부 포함하는 호출일 때

 

정수형 데이터 타입 고민

- 문제 조건 중 "입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다." 을 보고 모든 정수형 자료형을 long long 으로 선언하여 사용

- 메모리를 더 효율적으로 사용하기 위해 int 로 유지할 수 있는 변수들은 다시 int 로 바꿨으나 결과적으로 메모리가 줄지는 않음. (아마 채점 환경에서 int 가 8 byte 여서 그런가봄) 

 

코드

/* 87960KB,	220ms */
#include <iostream>
#include <stdio.h>
#define MAX 1000001
#define MAXSEG 10000001
using namespace std;

long long numArr[MAX];
long long segArr[MAXSEG];

long long segTree(int node, int start, int end) {
	if (start == end) {
		return segArr[node] = numArr[start];
	}

	int mid = (start + end) / 2;
	long long l = segTree(node * 2, start, mid);
	long long r = segTree(node * 2 + 1, mid + 1, end);
	return segArr[node] = l + r;
}

long long findSum(int node, int start, int end, int findStart, int findEnd) {
	if (findStart > end || findEnd < start) return 0;
	if (findStart <= start && findEnd >= end) return segArr[node];

	int mid = (start + end) / 2;
	long long l = findSum(node * 2, start, mid, findStart, findEnd);
	long long r = findSum(node * 2 + 1, mid + 1, end, findStart, findEnd);
	return l + r;
}

void updateNode(int node, int start, int end, int idx, long long diff) {
	if (idx > end || idx < start) return;
	segArr[node] += diff;

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

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

	freopen("input.txt", "r", stdin);
	int N, M, K;
	cin >> N >> M >> K;

	for (int i = 0; i < N; i++) {
		cin >> numArr[i];
	}
	segTree(1, 0, N - 1);

	while (M || K) {
		long long a, b, c;
		cin >> a >> b >> c;

		if (a == 1) {
			updateNode(1, 0, N - 1, b - 1, c - numArr[b - 1]);
			numArr[b - 1] = c;
			M--;
		}
		else {
			long long res = findSum(1, 0, N - 1, b - 1, c - 1);
			cout << res << "\n";
			K--;
		}
	}

	return 0;
}

 

배운 점

- return segArr[node] = numArr[start]; 가 가능하다는 것

- segTree 의 크기는 배열 크기 N 보다 커야 한다는 것

ㄴ segTree 높이: ceil(log2(N))

ㄴ segTree 크기: 2 ^ (높이 + 1)