Leetcode 370. Range Addition

문제

You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].

You have an array arr of length length with all zeros, 
and you have some operation to apply on arr. In the ith operation, 
you should increment all the elements arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] by inci.

Return arr after applying all the updates.

• 0으로만 이루어진 배열의 길이와 [시작인덱스, 끝인덱스, 값] 으로 구성된 업데이트의 배열이 주어진다.
• 업데이트 배열 하나마다 시작인덱스 ~ 끝인덱스 만큼 범위에 값을 더한다
• 모든 업데이트가 이루어 졌을때 결과 배열을 리턴하시오.

예시

1 ~ 3번 인덱스에 2 더하기 [1, 3, 2]

2 ~ 4번 인덱스에 3 더하기 [2, 4, 3]

0 ~ 2번 인덱스에 -2 더하기 [0, 2, -2]

제한

• $1 <= length <= 10^5$
• $0 <= updates.length <= 10^4$
• $0 <= startIdx_i <= endIdx_i < length$
• $-1000 <= inci <= 1000$

풀이

• prefix sum 을 이용한다.
• 시작 인덱스 부분에 값을 더하고 끝 인덱스 부분 + 1 에 반대로 값을 더하면 만들어진 배열의 prefix sum 은 결과 배열이 될수 있다.
• 즉, 업데이트 부분을 O(1) 시간에 처리할수 있다.