Prefix Sum Technique

사실 Technique라고 하기도 뭐하지만... 최근에 여러문제들을 풀면서 느낀 점이 있어서 간단하게 적어 놓으려고 한다.

Prefix Sum 이란?

Prefix = 접미사 sum = 합. 그니까 앞에서 부터의 합을 의미한다. 어떠한 값이 들어있는 기존의 배열 arr이 존재한다고 하면 $pre[x]=\sum_{i=1}^{x} arr[i]$ 로 표현되는 값들이 prefix sum들이라는 것이다. 

How?

prefix sum 배열을 채우는 것은 $O(N)$만에 정말 간단하게 할 수 있다. $pre[i]=pre[i-1]+arr[i]$ 로 할 수 있다. 어떤 식으로 활용해야 할지에 대해서 고민을 해봐야 한다.

prefix sum은 구간 합을 구할 때 주로 사용되어진다. i부터 j까지의 구간합은 $pre[j]-pre[i-1]$로 나타낼 수 있다. 이때 만약 값이 바뀌면 전체를 다시 채워야 하므로 바뀔 때 마다 $O(N)$이라서 효율성이 너무 떨어져서 대신 segment tree를 만이 사용한다. 따라서 계속해서 임의의 구간에 대한 합을 구하면서도 변경되는 값이 없을 때 사용을 하게 된다.

Technique in DP

굳이 Prefix Sum Technique이라고 한 이유는 최근에 다른 고급테크닉을 쓰는 DP문제들에서 prefix sum을 이용한 경우가 많았기 때문이다. 이 글을 쓴 이유도 그 때문이다. 
예를 들어서 CHT 문제가 있다고 해보자. j보다 작은 i에 대해서 i와 j에 관한 식의 최솟값을 찾는 것인데 이때 i~j의 구간합이 들어가 있으면 그 대신 pre[j]-pre[i-1]로 대신 할 수 있다는 것이다. 이렇게 식을 바꿨을 때 가장 좋은 점은 pre[i-1]이 고정된 채로 j가 바뀌어도 계속 쓸 수 있다는 것이다. 실제로 cht에 한 번 선분을 넣어놓고 그 선분을 계속해서 활용한다는 것을 알 수 있다. 

결국 prefix sum을 활용함으로써 얻을 수 있는 가장 큰 이점은 재활용과 시점의 분리라는 것이다. i~j 모두를 잇는 것이 아니라 i시점에 -pre[i-1]을 해놓고 나중에 계속 j를 바꿔가면서, pre[j]를 바꿔서 더해가면서 그 시점에서 값을 다시 취할 수 있다는 것에 장점이 있게 된다.