구간 합

구간 합 구하기

0. 구간 합?

구간 합은 위와 같이 전체 범위에서 각 부분 범위를 빼서 구할 수 있다. 그러나 중복되는 영역이 존재하기 때문에 이 영역은 나중에 더해주어야 한다.

이를 도식화하면,

과 같이 나타낼 수 있다.

간단하게 시간복잡도를 구해보면 대략 $O(n^2)$인 것을 알 수 있다. 그러나 이런 방법으로 구간 합을 구하는 것은 매우 비효율적이다.

만약 구간이 여러 개가 주어지는 상황일 때, 시간 복잡도는 $O(n^3)$이 되게 된다.

그렇다면, 어떻게 최적화할 수 있을까?

1. 누적 합 계산

각 위치에 따른 누적합 표를 미리 구해놓을 수 있다면, 이 표에 $O(1)$의 복잡도로 접근하여 시간복잡도를 확연하게 줄일 수 있을 것 같다.

그렇다면, 특정 위치의 누적 합을 구하는 방법은 어떻게 일반화할 수 있을까?

위와 같이, 특정 위치의 누적 합을 구하는 과정은 다음과 같다.

우선, 특정 위치의 왼쪽과 위쪽의 누적 합을 더한다. 이렇게 되면 중복되는 영역이 발생하게 되므로, 이 중복 누적 합을 빼줘야 한다.

마지막으로, 특정 위치 값을 더해주면 특정 위치의 누적 합을 구할 수 있다.

검산도 성공적으로 이루어진 것을 볼 수 있다.

간단한 파이썬 코드로 나타내면 다음과 같다.

for i in range(1, n + 1):  
    row = list(map(int, input().split()))  
    for j in range(1, n + 1):  
        s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + row[j-1]

2. 구간 합 계산

이렇게 누적 합에 대한 표를 구했다면, 구간 합을 $O(1)$의 복잡도로 구할 수 있다.

만약 질의가 $(x_1,y_1,x_2,y_2)=(2,2,4,3)$와 같이 주어진다면, 아래와 같이 처음에 봤던 구간 합을 구하는 방식을 누적 합 표에 적용하여 쉽게 구할 수 있다.

최종적으로 아래와 같은 식으로 나타낼 수 있게 되었다.

각 원소에 접근하는 시간 복잡도는 $O(1)$ 이므로, 최종의 시간복잡도 $T(n,m)$는

$$T(n,m)=O(n^2)+O(m)=O(n^2+m)$$

과 같이 나타낼 수 있다.