주뇽's 저장소

Difference Array Technique 이 기법은 주로 누적 합(Prefix Sum)과 함께 사용되며, 배열의 연속적인 부분에 대한 업데이트를 빠르게 수행할 수 있도록 해준다. 효율적인 업데이트: 배열의 큰 구간을 한 번의 연산으로 업데이트할 수 있다. 이는 구간에 포함된 각 요소를 개별적으로 업데이트하는 것보다 훨씬 빠르다. 시간 복잡도: 각 업데이트는 O(1) 시간에 수행된다. 전체 배열에 대한 누적 합 계산은 O(N) 시간이 소요된다 예시: 온도 조절 상황 : 7일 동안의 온도 기록을 가지고 있다. 각 날짜의 초기 온도는 0도로 설정되어 있다. 일: 1 2 3 4 5 6 7 온도: 0 0 0 0 0 0 0 이제 다음과 같은 온도 조절 작업을 수행한다고 가정해 보자 : 1. 2일부터 4일까지..