Windycaution's blog

Is there any persistent segment tree impl by std::vector ?
By Windycaution, history, 4 years ago, In English

Hello, I have recently got haunted by telling the size of memory pool of persistent segment tree, getting WA / RE / MLE results on many problems. Therefore, I'd appreciate it if someone could give me a implementation of persistent segtree applying std::vector to manage the memory (in order to avoid getting WA / RE / MLE by telling wrongly the size of arrays), which I could not find one anywhere on the Internet.

If the code could be laconic as well, it would be better.

Thank you!

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

»
4 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

It is bad and not-templated though ((

→ Reply
»
4 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Here's mine

→ Reply
»
4 years ago, hide # |
← Rev. 5  
Vote: I like it +1 Vote: I do not like it

mine; I choose not to templatize and prefer just to modify the PST for the problem, for example spoj dquery, kth smallest in range

→ Reply
  • »
    »
    4 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I still stick to tempatizing & formulating every data structure within a mathematical model, but still thank you for advising.

    → Reply
»
4 years ago, hide # |
 
Vote: I like it +44 Vote: I do not like it

I would highly recommend using std::deque instead of std::vector because of two reasons:

  1. Inserting and deleting elements from a deque at beginning or end will not invalidate pointers. This means your code could still use pointers everywhere. So by using std::deque your implementation could look almost identical to the usual implementation of a persistent segment tree .

  2. std::deque has lower memory overhead than std::vector. This is probably not super important, but it is something.

Another alternative you could look into is using a bump allocator.

→ Reply