370. Range Addition (差分

T: O(k + n), k is size of updates, n is the length

S: O(n)

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] res = new int[length];
        
        for (int[] update : updates) {
            int startIdx = update[0];
            int endIdx = update[1];
            int value = update[2];
            res[startIdx] += value;
            
            if (endIdx < length - 1) {
                res[endIdx + 1] -= value;
            }
        }
        
        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum += res[i];
            res[i] = sum;
        }
        return res;
    }
}

/*

for example it will look like:

[1 , 3 , 2] , [2, 3, 3] (length = 5)


record number at start,
record negtive number out of ending (end+1) => key point
then use prefix sum add -> it's result
  
0 1 2 3 4 5
  2 2 2
    3 3

0 2 0 0 -2
    3   -3
    
[[1,3,2],[2,4,3],[0,2,-2]]


 0 1 2 3 4 5
   2     -2  
     3     -3 => no need record (last index)
-2     2

-2 0 3 5  3 

    
*/

diff new version

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] diff = new int[length];
        for (int[] update : updates) {
            int start = update[0];
            int end = update[1];
            int inc = update[2];
            
            diff[start] += inc;
            if (end + 1 < length) {
                diff[end+1] -= inc;
            }
        }
        int[] result = new int[length];
        result[0] = diff[0];
        for (int i = 1; i < length; i++) {
            result[i] = result[i-1] + diff[i];
        }
        return result;
    }
}

/*

diff[i] = nums[i] - nums[i-1]

so nums[i] = diff[i] + nums[i-1], so if change diff , the interval value will change, 
so diff[i] += number, and do diff[j+1] -= number


[0, 2,2,2,0 ]

diff[i] +=2 , diff[1] = 2
diff[j+1] -= 2 diff[4] = -2


res[i] = res[i-1] + diff[i]

 0 0 0 0 0
   1
 
 res[0] = 0
 res[1] = 2
 res[2] = res[1] + diff[2](0) = 2
 res[3] = res[2] + diff[3](0) = 2
 res[4] = res[3] + diff[4](-2) = 0

*/