# 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}

Java