# 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,
[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 ]

@tag-array



# 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 add -inc to the position where end 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 to subtract 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 n-1, 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) {
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/range-addition/
// 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:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
d = [0] * length
for l, r, c in updates:
d[l] += c
if r + 1 < length:
d[r + 1] -= c
return list(accumulate(d))

############

class Solution(object):
def getModifiedArray(self, length, updates):
"""
:type length: 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