Problem statement

https://leetcode.com/problems/range-addition/

Solution

Naive approach is $O(nk)$, where we just update numbers by definition. Smarter approach is to sort all ends of segments, with indications if it is beginning or ending and its weight. Then use the idea of line sweep, where we go from left to right and add weight to sum if we meet starting point and remove weight from sum if we meet ending point. We need to work with end+1 instead of end in fact and deal with all updates for given point, before update the data, complexity is $O(n + k\log k)$.

Actually we can do better: using Cumulative Sums: for example if we want to add $3$ to elements in $[2,4]$ and $5$ to elements in $[4,5]$, we can just summate $[0,0,3,0,0,-3,0]$ and $[0,0,0,0,5,0,-5]$ to get $[0,0,3,0,5,-3,-5]$ and compute cumulative sums: $[0,0,3,3,8,5,0]$. It is similar to Line Sweep, but it does not matter in which order we need to do it.

Complexity

Time complexity is $O(n+k)$, space complexity is $O(n)$.

Code

class Solution:
    def getModifiedArray(self, length, updates):
        ans = [0] * (length + 1)
        for i,j,w in updates:
            ans[i] += w
            ans[j+1] -= w
        return list(accumulate(ans))[:-1]