Skip to content
Algorithm.js
Frame

Difference Array

구간에 대한 누적 변화를 차분 배열에 기록해 O(N) 시간에 원본 배열을 복원하는 Difference Array 기법 요약

Oct 17, 2025 — difference-array 
const differenceArray = Array(N + 1).fill(0);
// [left, right] apply change
for (const [ left, right ] of queries) {
    differenceArray[left] += value
    differenceArray[right + 1] -= value
}


// use this difference array to calculate the original array
for (let i = 0; i < N; i += 1) {
    // use differenceArray[i], usually compare this with current value nums[i]
}

기본 문제들

Reference