370. 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]

HINT:

1. Update only the first and end element is sufficient.

如何做到只更新两个位置，那么中间哪些位置的值应该是通过ans[i+1] += ans[i] 来获得。

简化问题： 只有一个操作(n = 5, updates = { {1, 3, 2} })

• Initialize the result array
  result = [0, 0, 0, 0, 0]
• Then marks index 1 as 2 and marks index 3+1 as -2:
  result = [0, 2, 0, 0, -2, 0]
• Next, iterate through result, and accumulates previous sum to current position, just like 303. Range Sum Query - Immutable:
  result = [0, 0 + 2, 0 + 2, 0 + 2, 2 + (-2), 0] = [0, 2, 2, 2, 0, 0]
• Finally, trivial work to discard the last element because we don't need it:
  result = [0, 2, 2, 2, 0], which is the final result.

Now you might see why we do "puts inc at startIndex and -inc at endIndex + 1":

• Put inc at startIndex allows the inc to be carried to the next index starting from startIndex when we do the sum accumulation.
• Put -inc at endIndex + 1 simply means cancel out the previous carry from the next index of the endIndex, because the previous carry should not be counted beyond endIndex.

   public int[] getModifiedArray(int n, int[][] updates) {  
     int[] ans = new int[n];  
     for(int i = 0; i < updates.length; i++){  
       int start = updates[i][0];  
       int end = updates[i][1];  
       int val = updates[i][2];  
       ans[start] += val;  
       if(end!= n-1)  
         ans[end+1] -= val;  
     }  
     for(int i = 1;i < n; i++){  
       ans[i] += ans[i-1];  
     }  
     return ans;  
   }