[LintCode] Range Addition

给定一个全为0的array的长度，以及一系列操作，每个操作会指明要操作的开始索引和结束索引，以及要加上的值，求出所给操作执行完之后的array情况，具体样例如下：

Given:
length = 5,
updates = 
[
[1,  3,  2],
[2,  4,  3],
[0,  2, -2]
]
return [-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 ]

一些提示：

1. Thinking of using advanced data structures? You are thinking it too complicated.
2. For each update operation, do you really need to update all elements between i and j?
3. Update only the first and end element is sufficient.
4. The optimal time complexity is O(k + n) and uses O(1) extra space.

解决方案：

class Solution:
    """
    @param length: the length of the array
    @param updates: update operations
    @return: the modified array after all k operations were executed
    """
    def getModifiedArray(self, length, updates):
        # Write your code here
        result = [0 for idx in range(length)]
        for item in updates:
            result[item[0]] += item[2]
            if item[1]+1 < length:
                result[item[1]+1] -= item[2]
        tmp = 0
        for idx in range(length):
            tmp += result[idx]
            result[idx] = tmp
        
        return result

思路：
其实想清楚了很简单，该算法有两个操作，第一：对每个operation中的start位置的值加上val，end位置值减去val；第二：最后求解整个list的值的时候，是从前到后逐个相加得到的，考虑一个操作：[start, end, val]，该操作是在目标list的start到end范围内加上val的值，考虑两个操作，从start开始，实际效果就是每个位置都会加上val值，一直加到end位置，因为end位置的操作是减去val，那么这个时候再加上这个负值，再往后计算，该操作就没有影响了，也就是说通过操作一，将[start, end, val]限定在给定的范围之内，通过操作二，实现给定范围内都加上所有 的值，这样就减少了循环遍历操作，整个思路还是非常巧妙地