AnotherRound's blog

By AnotherRound, history, 8 years ago, In English

Hello!

I've recently read about persistent segment trees and I found some good resources on the internet. I then remembered a problem I've seen earlier, which is requires algorithm for the following task:

You're given an array A1, A2, A3, ... An (n <= 100000) and lets say that this array is in version 1. Then m <= 100000 queries follow. For each query, we create a new "version" of the array, which is copied from some previous version v, then we increment all elements in the range [l, r] in this new version. Then we must say what is the sum of the elements in the range [i, j] for the new version.

This problem clearly resembles persistent segment tree (sum of ranges). Problem is, changes made aren't linear(if we draw a diagram of the versions, it will be a tree). I think this can be done using the following algorithm (in C++). For representing nodes of segment tree, we create a structure with pointers for left and right and we use lazy propagation. In some array we keep references to the roots of all versions up to now. When we have to build the new version, we take the tree of the old version, we create a new root for the new version. As we do the first step (updating the range [l, r]) we just create new nodes when a modification is needed and reuse those from the old version if they are not used. The problem is, I think that this approach would give correct answer, but I'm not sure about complexity of the algorithm (I need O(nlog(n))). Can somebody tell me whether my idea would work and if yes, what complexity would it have? Thank you in advance. I'll also appreciate if there is some other, easier way to create non-linear persistent segment tree.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
8 years ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

Your idea seems correct. The complexity will be O(NlogN) both time and memory (at each update you create O(logN) new nodes).

BTW: exactly the same task: http://www.math.bas.bg/infos/files/2014-11-23-A1-EN.pdf

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. Actually this is the original problem I mentioned in the post :)