Question
Formatted question description: https://leetcode.ca/all/370.html
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]
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 ]
@tagarray
Algorithm
Suppose our array range is [0, n)
, the interval to be updated is [start, end]
, and the updated value is inc.
Then add inc to each number in the interval [start, end]
, which is equivalent to
 Add inc to all numbers in the interval
(start, n)
 Then subtract inc from all the numbers in the interval
(end+1, n)
After understanding that this conversion can be done, we still can’t update all the values in the interval every time, so we need to change the marking method.
 The method is to add
inc
to the start position at the beginning of the coordinate, and addinc
to the position whereend adds 1
.
For example, we need to add 2 to the numbers in the new interval [1, 3]
, then we add 2 at the position of 1, and subtract 2 at the position of 4, so the array becomes [0, 2, 0, 0, 2]
.
If there is only one operation, how to get the final result?
The answer is to create a cumulative sum array, which becomes [0, 2, 2, 2, 0]
We found that it is exactly equivalent to directly adding 2 to the numbers in the interval [1, 3]
. Further analysis, the operation of establishing the accumulation and array actually means that the current number has an effect on the numbers in all subsequent positions.
 Then we add 2 to the start position, which means that every number in the range of [start, n) is added 2
 In fact, only the numbers in the [start, end] interval need to be added by 2
 In order to
eliminate this effect
, we need tosubtract 2 from the numbers in the [end+1, n) interval
, so we subtract 2 from the end+1 position
Then when the accumulation and array is created, it is equivalent to subtracting 2 from all the numbers behind. It should be noted that end may be equal to n1, then end+1 may be out of range, so we initialize the length of the array to n+1 to avoid the out of range.
Then according to the example in the title, we can get an array, nums = {2, 2, 3, 2, 2, 3}
, and then add it up and it is the result we require result = {2, 0 , 3, 5, 3}
Code
Java

import java.util.Arrays; public class Range_Addition { public static void main(String[] args) { Range_Addition out = new Range_Addition(); Solution s = out.new Solution(); System.out.println(Arrays.toString(s.getModifiedArray(5, new int[][]{ {1,3,2}, {2,4,3}, {0,2,2} }))); } class Solution { public int[] getModifiedArray(int length, int[][] updates) { int[] ans = new int[length]; for (int[] update : updates) { int start = update[0]; int end = update[1]; int inc = update[2]; ans[start] += inc; if (end + 1 < length) { ans[end + 1] += inc; } System.out.println(Arrays.toString(ans)); // [0, 0, 0, 0, 0] // [0, 2, 0, 0, 2] // [0, 2, 3, 0, 2] // [2, 2, 3, 2, 2] } for (int i = 1; i < length; i++) { ans[i] += ans[i  1]; // @note } // [2, 0, 3, 5, 3] return ans; } } }

// OJ: https://leetcode.com/problems/rangeaddition/ // Time: O(N + U) // Space: O(1) class Solution { public: vector<int> getModifiedArray(int length, vector<vector<int>>& A) { vector<int> ans(length); for (auto &v : A) { int start = v[0], end = v[1], diff = v[2]; ans[start] += diff; if (end + 1 < length) ans[end + 1] = diff; } int sum = 0; for (auto &n : ans) n = sum += n; return ans; } };

class Solution(object): def getModifiedArray(self, length, updates): """ :type length: int :type updates: List[List[int]] :rtype: List[int] """ ans = [0] * length for update in updates: start, end, delta = update ans[start] += delta if end + 1 < length: ans[end + 1] = delta delta = 0 for i in range(0, length): delta += ans[i] ans[i] = delta return ans