Range Addition


  • 1

    Click here to see the full article post


  • 1

    An extension of this problem is to apply such updates on an array where all elements are not the same. In this case, the second approach requires that the original configuration must be stored separately before applying the final transformation. This incurs an additional space complexity of O(n).

    Why? Can't you just apply "reverse partial_sum" to initialize? For example if given the array [2, 3, 10, 5], just change it to [2, 1, 7, -5] first.


  • 0
    This post is deleted!

  • 0

    @StefanPochmann Wow. I had never thought of that. It's not exactly "reverse partial_sum" per se. But I get the idea. At this point it's a O(n) extra runtime vs O(n) extra space tradeoff.

    I'll update the article. Keep the suggestions coming. Thanks!


  • 0

    @babhishek21 I'd say the term might be ambiguous (which is why I included the example), but correct. If partial_sum is

    for i from 1 to n-1:
        a[i] += a[i-1]
    

    then doing it in reverse is exactly what's needed:

    for i from n-1 down to 1:
        a[i] -= a[i-1]
    

    I guess "inverse" would've been better, I did think of it as a mathematical function and that's the proper term there.


  • 0

    @StefanPochmann That makes sense.

    In my mind, reverse partial_sum meant something like:

    partial_sum(a.begin(), a.end(), minus<decltype(a)::value_type>());
    

    Anyway. I checked if your suggestion worked, and it does.


  • 0
    V

    Yes, it works, and that is a brilliant thought! Thanks @StefanPochmann


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.