부분 합. [2167]

[1. 문제 설명]

[2. 풀이 접근]

문제의 요구 사항은 다음과 같다.

입력으로 주어진 i, j, x, y 가 배열 상에서 아래와 같은 그림과 같을 때

다음과 같은 영역의 존재하는 원소들의 합을 구하는 것 이다.

단순한 풀이, 매 TC 마다 배열의 구간 [i, j] ~ [x, y] 를 iterate 하면서 그 합을 구한다면,

전체 시간복잡도가 O(N*M*10000) 이고, 대략 300*300*10000 = 9*10⁸ ==> 1초가 넘어 갈 수 있다.

그러나 각 행마다 그 부분 합 들을 따로 구해 놓으면,

300*10000 = 3*10⁶ 으로 시간 복잡도를 대폭 줄일 수 있다.

각 행에 대해서는 루프를 돌지만, 그 행의 합은 O(1) 에 구할 수 있게 되는 것이다.

[3. 코드]

[4. 코드 개선]

loop 도는 부분을 조금 더 개선 (영역의 누적 합을 상수시간에 계산 할 수 있다.)

test_kernelv2