 Shawn Lin

## Leetcode Diary - Range Addition

2022-07-26

Range addition is a common algo pattern. The problem statement will be along the line that:

Given an array, add i1 to all values from index s1 to e1, add i2 to all values from index s2 to e2.

There is a template we can use to solve it. It requires two steps:

1. Marking the position of start and end of the addition
2. Computing a cumulative sum

## Leetcode 370

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.

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]
• mark increments

def mark_inc(updates, length):
# create array of all zeros as stated in the question
# note we created one additional space to accomodate end index
arr =  * (length + 1)

# extract parameter
start_index = udpate
end_index   = update
inc         = update

# mark increment at start and end index
arr[start_index] += inc
arr[end + 1]     -= inc

return arr
• cumulative sum:

def calc_cumsum(inc):
n = len(inc)
cumsum = list(inc)
for i in range(1,n):
cumsum[i] += cumsum[i-1]
return cumsum
• combining together

def range_sum(updates, length):
return cumsum