구간 합 문제

알고리즘 문제를 풀다 보면 특정 구간에 대해서 합, 최대 최소 등을 구하는 문제가 자주 등장한다.

예제 : 구간 합 구하기 4

위 문제는 포인터 두 개를 사용하여 적절한 구간을 매번 선택하면서 끝까지 탐색 시키는 방식으로 간단하게 풀 수 있다.

#include <iostream>

using namespace std;

int arr[100001];

int		main(void)
{
	int		n, m;
	int		i;
	int		a, b;

	i = 0;
	scanf("%d %d", &n, &m);
	while (i++ < n)
	{
		scanf("%d", &arr[i]);
		arr[i] = arr[i] + arr[i - 1];
	}
	while (m--)
	{
		scanf("%d %d", &a, &b);
		printf("%d\\\\n", arr[b] - arr[a - 1]);
	}
	return (0);
}

우선 Array에 문제에서 사용할 값들을 입력 받는다. 입력 받음과 동시에 직전 index에 저장되어 있던 값을 더해 현재 입력 받은 수를 갱신한다. 이렇게 데이터를 입력 받으면 각 index의 수들은 0번 index부터 자기 자신 까지의 누적 합을 담게 된다.

위 형태와 같이 누적 합 배열을 만들었다면, N부터 M까지의 구간 합은

**Array[M] - Array[N - 1]**

로 쉽게 계산된다는 것을 알 수 있다.

데이터가 계속 갱신되는 구간 합 문제

이제 문제를 확장해서 값이 계속 갱신 되는 경우의 구간 합을 구하는 방법에 대해 생각해보자.

만약 4번 index의 숫자를 10으로 갱신한다고 가정하면

4번 index부터 데이터의 size까지 누적 합을 전부 다시 계산해주어야 한다. 위의 그림에서는 데이터가 10개 뿐이지만, 만약 데이터의 개수가 10만 개, 100만 개로 늘어난다면 선형 시간 안에 누적 합을 계산하지 못하게 될 것이다.

이를 해결하기 위한 알고리즘으로는 Segment Tree, Fenwick Tree, Index Tree 등이 있는데 이번 글에서 다루고자 하는 것은 Bottom Up 방식으로 데이터를 갱신하는 Index Tree이다.

Index Tree

예제 : 구간 합 구하기

Index Tree 만들기

Index Tree의 초기 모습은 아래와 같다.