구간합 기술, 그림으로 쉽게 이해하기

1. 구간합 기술이란?

1차원 배열에서 특정 구간 내의 원소들의 합을 구하는 알고리즘이다.

2. 왜 써야 하는가?

위의 예시에서 A에서 B까지의 구간 합을 구한다면, 어떻게 구할 것인가? 혹자는 2번 index부터 7번 index까지 for 반복문을 활용해 차례대로 더할 것이다. 혹자는 0에서 A번까지의 누적합을 구하고, 0~B번까지의 누적합을 구해, 둘을 빼서 구할 것이다. 만약 단일 계산이라면, 이런 식의 풀이는 n번의 반복일 뿐이니 괜찮을 수 있다. 하지만, 문제에서 여러 개의 구간합을 반환하길 바란다면? 매번 이러한 반복문을 반복하는 것은 비효율적이다. 이는 시간 초과로 이어질 수 있다.

시간 복잡도로 계산해 보겠다. 최악을 상정해야하니, N개의 원소를 가진 배열에서 0~ N~1까지의 계산을 K번 반복한다고 하자. 이때의 시간 복잡도는 O(N*K)이다.

3. 어떻게 구현 하는가?

구간합 알고리즘은 이러한 시간 복잡도를 획기적으로 줄인다. 먼저 구간합 알고리즘을 이해하기 위해서는 누적합 배열에 대한 이해를 해야한다. 누적합 배열은 말그대로, 문제에서 주어진 배열의 원소값을 index를 거듭할수록 누적하여 저장하는 배열이다. 위의 예시로 들었던 배열을 누적합 배열로 다시 나타내면 다음과 같다.

이제 뭘하면 되는가? 그렇다! 그냥 필요한 위치의 누적합끼리 빼면된다.

여기서는 18 - 2 = 16으로 나올 수 있다. 누적합끼리의 차는 무엇을 의미하는가?
sum[7] = 1에서7번 index의 값들의 합이고, sum[1] = 1 index의 합이다. 이 둘의 차는 2에서 7번 index의 합이다.

두 수간의 차를 구하는 시간복잡도는 O(1)이다. 따라서 구간합을 쓰지 않은 방식이 매번 구간합을 구하는 것과 다르게, 해당 알고리즘을 활용하면 누적합을 구하는 N번의 반복을 제외하면 사실상 시간 복잡도를 늘리는 행동이 없다. 구해야하는 구간합의 개수를 K라고 하면 시간복잡도는 O(N+K)가 될 것이다.