Published: Sep 12, 2022

Medium Prefix Sum Array

## Introduction

If the problem is just about an array, prefix sum might work well. The problem may not look straightforward prefix one, but it’s good to think prefix solution.

## Problem Description

You are given an integer `length` and an array `updates` where `updates[i] = [startIdx(i), endIdx(i), inc(i)]`. You have an array `arr` of length `length` with all zeros, and you have some operation to apply on `arr`. In the i-th operation, you should increment all the elements `arr[startIdx(i)], arr[startIdx(i + 1)], ..., arr[endIdx(i)]` by inc(i).

Return `arr` after applying all the updates.

Constraints:

• `1 <= length <= 10**5`
• `0 <= updates.length <= 10**4`
• `0 <= startIdx(i) <= endIdx(i) < length`
• `-1000 <= inc(i) <= 1000`

## Examples

``````Example 1:
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]
``````
``````Exmaple 2:
Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]]
Output: [0,-4,2,2,2,4,4,-4,-4,-4]
``````

## Analysis

Every value within the update range doesn’t need to be updated every time. Only start and end range is enough. To mark the end, end + 1 is decremented by inc. After that, calculate prefix sum, which is the answer.

## Solution

``````class RangeAddition:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
prefix = [0 for _ in range(length)]
for start, end, inc in updates:
prefix[start] += inc
if end < length - 1:
prefix[end + 1] -= inc
for i in range(1, len(prefix)):
prefix[i] += prefix[i - 1]
return prefix
``````

## Complexities

• Time: `O(n + m)` – n: length of updates, m: length
• Space: `O(m)`