Range Addition

Assume you have an array of length n initialized with all 0's and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

Example:

Given:

    length = 5,
    updates = [
        [1,  3,  2],
        [2,  4,  3],
        [0,  2, -2]
    ]

Output:

    [-2, 0, 3, 5, 3]

Explanation:

Initial state:
[ 0, 0, 0, 0, 0 ]

After applying operation [1, 3, 2]:
[ 0, 2, 2, 2, 0 ]

After applying operation [2, 4, 3]:
[ 0, 2, 5, 5, 3 ]

After applying operation [0, 2, -2]:
[-2, 0, 3, 5, 3 ]

思路分析

这道题最容易想的就是用python中的map function来实现：

class Solution(object):
    def getModifiedArray(self, length, updates):
        """
        :type length: int
        :type updates: List[List[int]]
        :rtype: List[int]
        """
        if length <=0: return []
        result = [0 for i in range(length)]
        for startIndex, endIndex, inc in updates:
            result[startIndex: endIndex+1] = map(lambda x: x+inc, result[startIndex: endIndex+1])    <<<<
        return result

这种实现方式的时间复杂度是多少呢？O(length * k)，这个时间复杂度在leetcode出现了TLE

那么怎么样用更小的时间复杂度来实现呢？参考了一下网上的思路，这道题可以用O(length+k)的时间复杂度来实现

We update the value at start index, because it will be used in the future when we are adding up the values for the sum at each index between start index and end index(both inclusive). We update the negative value at the end index + 1, because the positive value of it should be only added at its previous indices (from start index to end index). Thus, when we accumulate the sum at the end for each index, we will get the correct values for each index. If the end index is the last index in the resulting array, we don’t have to do the end index + 1part, because there is no more index after the last index and there will be no error when we accumulate the sum.

class Solution(object):
    def getModifiedArray(self, length, updates):
        """
        :type length: int
        :type updates: List[List[int]]
        :rtype: List[int]
        """
        if length <=0: return []
        result = [0 for i in range(length)]
        for startIndex, endIndex, inc in updates:
            result[startIndex] += inc
            if endIndex < length - 1: result[endIndex+1] -= inc
        sum = 0
        for i in xrange(length):
            sum += result[i]
            result[i] = sum
        return result