부분합

1차원 배열

sum[i] = arr[0]+arr[1]+...arr[i-1]

arr의 i항부터 j항까지의 합을 S(i,j)라고 했을 때, S(i,j)는 sum[j+1]-sum[i] 이다.

2차원 배열

sum[i][j] 에는 arr[0][0] 부터 arr[i-1][j-1] 까지의 합이 담겨있다.

sum 배열 만드는법

sum_arr[i][j] = arr[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1]