차분 배열은 범위 업데이트를 선형시간에 처리하기 위한 기법입니다. 차분 배열에 변화량을 기록하고, 누적 합 기법을 통해 지정 범위의 값을 원하는 값으로 모두 업데이트 하는 방식입니다. 위 예시는 차분 배열과 누적합을 활용하여 2차원 배열에서 (1,1) ~ (2,2) 범위의 원소를 모두 5로 업데이트 하는 과정입니다.
1.2 특징
추가적인 메모리 공간 필요, 차분 배열.
변화량 중심의 사고 방식.
상수 시간의 시간 복잡도(O(N)), 시작점과 끝점만 알면 네 개의 모서리만 수정하면 된다.
동일 값 제약, 지정 범위에 모두 동일한 값이 적용될 때 사용 가능함.
2. 동작 방식
2.1 차분 배열
diff[r1][c1] += v
diff[r1][c2+1] -= v
diff[r2+1][c1] -= v
diff[r2+1][c2+1] = +v
차분 배열을 준비하고, 지정된 직사갹형 범위의 (r1, c1) ~ (r2, c2) 네 모서리에 위와 같이 준비합니다. 만약, 범위가 (1,1) ~ (2, 2) 까지라면, diff[1][1] 에 5를 넣고, diff[1][3] 에 -5, diff[3][1] 에 -5, 그리고 diff[3][3] 에 +5를 넣어 준비합니다.
* 차분 배열 최초 생성 시 r2+1 행 크기와 c2+1 크기로 할당 받고, 모두 0으로 초기화 합니다.
2.2 누적 합
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 포함-배제 원리를 사용한 2차원 누적합
result[i][j] = diff[i][j];
// 위쪽 값 더하기
if (i > 0) {
result[i][j] += result[i-1][j];
}
// 왼쪽 값 더하기
if (j > 0) {
result[i][j] += result[i][j-1];
}
// 대각선 값 빼기 (중복 제거)
if (i > 0 && j > 0) {
result[i][j] -= result[i-1][j-1];
}
}
}
차분 배열에 업데이트 하고자 하는 범위의 네 모서리의 값을 설정한 후 원본 배열을 전체적으로 순회하며 현재 위치의 값을 위에 위치한 값 + 왼쪽에 위치한 값 - 왼쪽 대각선 위에 위치한 값 해주며 누적합 계산을 진행해줍니다. 최종적으로, (1,1) ~ (2,2) 범위의 값들이 모두 '5'로 업데이트 됩니다.
