백준 2042번: 구간 합 구하기

jsi06138·2020년 8월 27일
0

문제
어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.


입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.

출력
첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.


이 문제에서 요구하는 것은 구간의 합을 구하고 수를 변경하는 연산이다.
구간의 합들을 앞에서부터 차례대로 저장해놓고, 수를 변경할 땐 그 수를 포함한 구간의 합들을 변경하는 방법을 생각할 수 있다. 이것을 이진트리로 구현해 세그먼트 트리
(https://www.acmicpc.net/blog/view/9)로 만들 수 있다.

이진트리의 크기는 원소의 개수를 사용해 최대 이진트리의 크기를 알아낼 수 있었다.

leaf의 개수가 n개 일 때

  • 포화이진트리(Full Binary Tree)
    총 노드의 개수: 2n - 1
    높이: log n
  • Not Full Binary Tree
    총 노드의 개수: 2^(h+1) - 1
    높이: O(logn)

알고리즘 요약

세그먼트 트리를 만들어내기 위해 tree의 루트부터 시작해서 init를 재귀로 호출하고 start==end가 되면, 즉 leaf node에 이르면 원소를 넣는다. 이후로는 구간들의 합들이 합쳐지면서 (다시 루트노드로 향함) 마지막으로 얻게되는 값은 전 구간의 합이 된다.

구간의 합을 구하는 함수에서는 left, right값을 필요로한다.
먼저 left, right의 범위가 타당한지 검사를 하고 그렇지않으면 값을 구할 수 없기에 0을 return한다.
다음으로 left, right구간에 딱 들어오게 되면 바로 값을 얻어내면되므로 그 시점의 값을 return한다.
만약.. left, right가 현재 구간(start, end)보다 안에 있을 경우에는 들어 맞을 때까지 구간을 쪼개서 sum함수를 호출한다.

마지막으로 값 변경 함수는 몇 번째 원소를 바꿀 것인지 그리고 기존 원소와 새로운 원소의 차이값을 필요로 한다.
이 함수도 위의 연산들과 마찬가지로 재귀호출을 하고 루트로부터 리프에 이를 때까지 차이값을 더하는 방식으로 값의 변경을 나타낼 수 있다.

#include <stdio.h>
#include <cmath>
#include <vector>

using namespace std;

long long init(vector<long long>&, vector<long long>&, int, int, int);
long long sum(vector<long long>&, int, int, int, int, int);
void update(vector<long long>&, int, int, int, int, long long);

int main() {

	int m, n, k;

	scanf("%d %d %d", &n, &m, &k);

	double h =ceil(log2(n));
	double size = pow(2,h+1); 

	vector<long long> a(n);
	vector<long long> tree(size);

	for (int i = 0; i < n; i++) {
		scanf("%lld", &a[i]);
	}

	init(a, tree, 1, 0, n - 1);

	m += k;

	for (int i = 0; i < m; i++) {
		
		int t1;
		scanf("%d",&t1);

		if (t1 == 1) {
			int t2; long long t3;
			scanf("%d %lld", &t2, &t3);

			t2 -= 1;
			long long diff = t3 - a[t2];
			a[t2] = t3;
			update(tree, 1, 0, n - 1, t2, diff);
		}
		else {
			int t2, t3;
			scanf("%d %d", &t2, &t3);
			printf("%lld\n", sum(tree, 1, 0, n - 1, t2 - 1, t3 - 1));
		}

	}

	return 0;
}


long long init(vector<long long>& a, vector<long long>& tree, int node, int start, int end) {
	if (start == end) {
		return tree[node] = a[start];
	}
	else {
		return tree[node] = init(a, tree, node * 2, start, (start + end) / 2) + init(a, tree, node * 2 + 1, (start + end) / 2 + 1, end);
	}
}

long long sum(vector<long long>& tree, int node, int start, int end, int left, int right) {

	if (right < start || end < left) {
		return 0;
	}
	
	if (left <= start && end <= right) {
		return tree[node];
	}

	return sum(tree, node * 2, start, (start + end) / 2, left, right) + sum(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right);
}

void update(vector<long long>& tree, int node, int start, int end, int index, long long diff) {

	if (index < start || end < index) {
		return;
	}

	tree[node] += diff;

	if (start != end) {
		update(tree, node * 2, start, (start + end) / 2, index, diff);
		update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, diff);
	}
		
}

0개의 댓글