누적합을 통해서 배열의 부분합을 빠르게 구할 수 있다.
요소가 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]을 한번 빼주게 되는 것이다.
이런 방식으로 구한 누적합은 아래와 같다.
