구간 갱신을 위한 차분 배열

누적 합은 구간 질의를 빠르게 처리했습니다. 차분 배열은 반대로 여러 구간 갱신을 빠르게 적용하게 해 줍니다. 🔁

구간의 모든 원소에 값을 더하는 작업을 여러 번 반복하면 갱신 한 번마다 O(n)이 걸립니다. q번 갱신을 수행하면 전체 비용이 급격히 커집니다.

모든 칸을 직접 수정하는 대신 변경이 시작되는 위치와 끝나는 위치만 기록하십시오. 가운데가 아니라 양 끝을 표시하는 것입니다.

차분 배열은 각 원소와 바로 앞 원소의 차이를 저장합니다. 차이 하나를 수정하면 그 뒤의 전체 구간이 바뀝니다.

l부터 r까지 v를 더하려면 인덱스 l에 v를 더하고 인덱스 r + 1에 v를 빼십시오. 두 번의 수정만으로 전체 구간을 처리할 수 있습니다.

l에서 더한 값은 변경을 시작하고, r + 1에서 뺀 값은 변경을 다시 끕니다. 두 표시가 함께 갱신을 하나의 구간 안에 가둡니다.

각 갱신은 배열에 두 번 쓰기만 하면 되므로 q번 갱신의 전체 비용은 O(q)입니다. 실제 계산은 마지막으로 미뤄집니다.

모든 표시를 마친 뒤 차분 배열에 누적 합을 적용하십시오. 한 번의 순회로 모든 최종 값을 복원할 수 있습니다.

배열을 한 칸 더 길게 만들어 r + 1이 끝을 벗어나지 않도록 하십시오. 여분의 보호용 칸이 인덱스 오류를 방지합니다.

갱신을 표시하는 데 O(q), 배열을 다시 만드는 데 O(n) 한 번의 순회가 필요합니다. 두 작업을 합친 비용은 단순한 O(n × q)보다 훨씬 작습니다.

차분 배열은 예약 수, 도로 통행료처럼 구간 더하기 작업이 많고 마지막에 한 번만 결과를 읽는 문제에서 특히 유용합니다.

인덱스 l부터 r까지의 모든 원소에 v를 더합니다.

차분 배열을 사용하면 구간 갱신을 모아서 처리할 수 있습니다. l과 r + 1을 표시한 다음 누적 합을 한 번 적용해 배열을 복원하십시오. 빠른 갱신과 한 번의 결과 조회가 가능합니다. ✅