18. 구간 쿼리, 구간 합 (Range queries, Prefix sum, c++)

구간 쿼리 (Range queries)?

구간에 대한 쿼리에서는 배열의 부분 배열들을 기반으로 어떠한 값들을 계산합니다.

 

예를 들면 [a, b] 구간의 합계를 구한다던지, [a, b] 구간에서의 최솟값을 구하는 경우들이 있고, 이러한 종류의 연산들을 효과적으로 처리할 수 있는 자료구조들이 있습니다.

---

Prefix Sum

구간에 대한 합계를 구하는 연산은 미리 계산된 prefix sum array를 통해 쉽계 계산할 수 있습니다.

 

prefix sum array의 각각의 요소들은 원본 배열에서의 해당 위치까지의 합계입니다.

 

따라서, prefix sum array를 만드는 과정은 단순히 이전까지의 값에 현재 값을 더하는 것으로  O(N)에 수행됩니다.

 

예를 들어 { 1, 3, 4, 8, 6, 1, 4, 2 } 라는 원본 배열이 있다면

 

prefix sum array 는 { 1, 4, 8, 16, 22, 23, 27, 29 } 와 같이 계산할 수 있습니다.

 

이 때, 0번째부터 k번째 까지의 구간합인 sum(0, k) 는 prefix sum array를 조회함으로써 O(1) 시간복잡도로 계산할 수 있게됩니다.

 

그러므로 a번째부터 b번째 까지의 구간합인 sum(a, b)는 sum(0,b)-sum(0,a-1) 로 구할 수 있으며 마찬가지로 O(1) 시간복잡도로 계산이 됩니다.

 

위 배열을 예로 들면 3~6 번쨰 구간 {4, 8, 6, 1}의 합은 psum[6]-psum[2] = 23-4=19 로 계산할 수 있습니다.

---

2D Prefix Sum

같은 방식으로 2차원 배열에 대한 prefix sum array를 계산하는 것으로 2차원 배열에서의 사각형 범위의 합을 O(1)의 시간복잡도로 계산할 수 있습니다.

 

아래와 같은 2차원 배열이 각각의 숫자를 가지고 있고 초록색 사각형 범위에 대한 구간 합을 구하려고 합니다.

 

psum[X]는 왼쪽 최상단에서 부터 X 까지의 사각형 구간의 합이라고 정의합니다.

 

계산된 값을 이용하여 초록색 사각형 범위의 합계는 A까지의 총 합계에서 B와 C 까지의 사각형 합계를 빼고 중복된 구간인 D까지의 합계를 더하는 것으로 계산할 수 있습니다.

 

따라서 psum[A]-psum[B]-psum[C]+psum[D] 로 O(1)에 계산할 수 있습니다.