Using heaps fro range addition - example of when it is needed?

Hi all, I’ve just found this problem on:

It says: "
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.

Now, it gives 2 solutions, one is inefficient and one is optimal. The inefficient one puzzles me:

  • he makes an array of operations sorted by their start time, and a min heap of operations sorted by their endtime
  • then he iterates that array, for each element looking at the top of the heap thus deciding what is the current answer at that index

Quick question: this inefficient mehod could have real life applications where you are forced by the circumstances to use this array & heap method. I am thinking what if “+” is replaced by a complex operation ? Simply storing the total sum that was added until now is possible because “+” is transitive (& associative & commutative & only needs 2 parameters).

Could you please think of a complex operation that forces you to use the array & heap method, simply because storing how many times it was apply (and its parameters) is not possible/inefficient ?

I am trying to come up with a scenario for an operation that forces us to use the first approach.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.