구간 합 구하기

구간 합 공식
어떤 수의 배열에 i번째부터 j번째 까지의 합을 구하고자 한다면(index 기준으로)

S[j] - S[i-1]

 
배열을 입력 받는다면, 사실상 두 개의 배열 저장 공간이 필요한데,
이를 위하여 StringTokenizer를 사용하는 것을 추천
 

 

먄약 2차원의 배열이라면?

두 번의 과정을 거쳐야함

1) 합 2차원 배열 생성

D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]

2) 구하려는 구간들에 대하여 합배열 간의 연산

(x1, y1) ~ (x2, y2) 구간 합 구하기

D[x2][y2] - D[x1 - 1][1] - D[1][y1 - 1] + D[x1 - 1][y1 - 1]