You are viewing a single comment's thread. Return to all comments →
Can you explain this line
differenceArray[a] += k;
differenceArray [b+1] -= k;
Why are you adding k to only differenceArray[a]??
Let's view the array as a list of histograms. Each position in the array has a histogram with a certain variable heigth. It would be cumbersome to keep track of the heigth of every single histogram. Instead, you could just keep track of how much the height of a given histogram differs from the one preceding it (in a continuous setting, this would mean to keep track of the derivative of a function, not the function itself).
Here, we know there is an increment of k for the height of the histogram in position a (a positive slope of k from a-1 to a), but then the height remains constant at positions a+1, a+2,...,b. Then again, we know that position b was the last position where histograms were incremented by k, so there is a decrement of -k at position b+1 (negative slope of -k from b to b+1).
Hope this helps.