LC: 370. Range Addition - spiralgo/algorithms GitHub Wiki

370. Range Addition

The Essence:

Applying changes over an entire range is inefficient. The idea is then to propagate some change beginning from some start point across its range without modifying those values directly.

Details:

The resulting value of the entire array can be calculated at the end. The individual update queries can be linearly preprocessed before this, with the start of the range getting the positive value and the end of the range getting a negative value. The usage of this system is that, when processing the entire array at the end, these individual updates provide which number should be added to the next element in the array. The negative value terminates this process. This is like a ripple-effect. Code can be found here.

This problem can also be solved using Segment Trees. This data structure is important for handling query problems, it's however not the best choice here. Slower both to implement and use.