누적 합 (Prefix Sum)
모든 요소가 양의 정수인 길이 $N$의 수열이 있다. $(1 ≤ N ≤ 10^5)$ 다음 문제를 풀어보자. C/C++ 기준 $1$초 안에 결과가 나와야 한다.
여러분은 이 문제를 어떻게 풀 것인가? 아마 대부분 반복문을 떠올릴 것이다.
그렇다면, 다음 문제는 어떻게 풀 것인가?
이 문제 역시 반복문을 우선적으로 떠올려볼 수 있다. 시간 복잡도는 수열의 길이 $N$, 쿼리의 개수 $Q$에 대해 $O(NQ)$가 되겠다.
최악의 경우 ?
위 문제에서 가장 많은 연산을 하는 경우는 어떤 경우일까? 간단하다. $[l, r]$을 가능한 최대로 길게 하는 것이다.
이 경우 구간의 길이 $10^5$, 쿼리의 최대 개수 $10^5$로 약 $10^{10}$의 연산량을 가지게 된다. 그리고 당연하게도, 이 연산량이 C/C++ 기준 $1$초 안에 완료될 리 만무하다.
결국 우리는, 새로운 방식을 고찰해야한다.
값을 재활용할 수 없을까?
다이나믹 프로그래밍을 접해본 사람이라면, 메모이제이션의 개념을 알고 있는 사람이라면 이 대목에서 대강 느낌이 올 것이다. 물론 이를 접해보지 않았어도 괜찮다.
위 문제에 대해 굉장히 중요한 사실이 하나 있는데, 이는 다음과 같다.
$a_1, a_2, a_4, ... , a_N$의 값은 불변하다.
$\sum\limits_{i=l}^r a_i$의 값은 지금 구해도, $10$년 뒤에 구해도, $100$년 뒤에 구해도 변하지 않는다.배열 하나를 정의해보자.
이는 한 번의 순회로 모두 채울 수 있다.
궁금증
위 배열의 의미를 이해했다면, 다음의 궁금증이 생길 것이다.
결과를 기록해두는 건 알겠는데, 이건 한쪽 끝이 고정되어 있지 않나요? 즉, $[1, 3]$, $[1, 5]$, $[1, N]$ 같은 경우만 답을 낼 수 있지 않나요?
역으로 여러분들에게 묻겠다. $[1, 3]$과 $[2, 3]$의 결과는 어떤 연관성이 있는가?
그렇다. $[1, 3]$에서 $[1, 1]$을 빼면 $[2, 3]$이 된다.
그럼 구간을 좀 넓혀서, $[1, 10]$과 $[6, 10]$은 어떤 연관성이 있는가?
그렇다. $[1, 10]$에서 $[1, 5]$를 빼면 $[6, 10]$이 된다.
마지막으로 질문을 조금 바꿔보자. $[4, 7]$의 결과는 무엇인가?
$[1, 7]$에서 $[1, 3]$을 뺀 값이다.
결론
우리가 기록해둔건, $[l, r]$에 대해 $[1, r]$인 경우 뿐이었다. 그런데 우리는, $[4, 7]$을 $[1, 7]$과 $[1, 3]$으로 분해해 생각할 수 있었다.
$l = 1$이 될 경우 $pre$ 배열에 기록된 값을 활용할 수 있게 되고, 이는 곧 각 쿼리를 $O(1)$에 계산할 수 있음을 의미한다.최종적으로 우리는 위 문제를 전처리 $O(N)$, 쿼리당 $O(1)$로 총 $O(N+Q)$에 해결할 수 있게 되었다.
자 다시 위로 돌아가보자. 이제 위 문제를 풀 수 있는가?