누적합을 통해서 배열의 부분합을 빠르게 구할 수 있다.
2차원 배열의 누적합을 구현하고, 원하는 영역의 합을 누적합을 이용해서 구하는 방법에 대해서 정리해보았다.
누적합 구현
요소가 1로 이루어진 3x3 배열이 있다고 가정하고, 이 배열을 matrix[][]라고 생각하자.
matrix = new int[3][3]
누적합 배열은 (3+1)x(3+1)배열로 만든다. 이 배열을 prefixSum[][]이라고 하자.
prefix=new int[4][4]
빨간색 원으로 표시한 곳의 누적합은 붉은 요소의 합 에 파란 요소를 뺀 것이라고 생각하면 편하다.
prefix[i][j]의 값을 넣으려면
prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]+prefix[i][j]-prefix[i-1][j-1]을 계산하면 된다.
prefix[i][j]를 기준으로 위의 값인 prefix[i-1][j] 와 왼쪽 값인 prefix[i][j-1] 은 둘다 prefix[i-1][j-1]을 가지고 있기 때문에, prefix[i-1][j]+prefix[i][j-1]을 하게되면 prefix[i-1][j-1]이 두번 더해지게 된다. 그래서 prefix[i-1][j-1]을 한번 빼주게 되는 것이다.
이런 방식으로 구한 누적합은 아래와 같다.
누적합을 이용해서 구간합 구하기
(1,1)에서 (2,2)까지 합한 결과값을 구하고 싶다고 가정하자.
누적합 배열을 보면 prefix[2+1][2+1] 값은 (0,0)부터 (3,3)까지의 합이다. 여기서
여기서 prefix[1][3]과 prefix[3][1]값은 배열 영역으로 생각하면 파란색과 같은 부분이다. 두 파란색 영역이 겹쳐지는 부분이 prefix[1][1]이기 때문에 두번 빠지는 부분이므로, 이 부분을 한번 더해준다.
최종적으로 prefix[3][3]-prefix[1][3]-prefix[3][1]+prefix[1][1]을 하면 원하는 영역의 합을 구할 수 있다.
matrix에서 (a,b)~(c,d) 영역의 합은 prefix[c+1][d+1]-prefix[a+1][d+1]-prefix[c+1][b+1]+prefix[a+1][b+1] 이다.
