Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Windycaution's blog

Is there any persistent segment tree impl by std::vector ?
By Windycaution, history, 2 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

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

It is bad and not-templated though ((

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

Here's mine

→ Reply
»
2 years ago, # |
← 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
  • »
    »
    2 years ago, # ^ |
      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
»
2 years ago, # |
  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
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    benchmarking agrees! vector 153512865 deque 153583279

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

    I would consider it a great idea, and I will try to implement one. Thanks for advising!

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

    But, seemingly, std::deque is less efficiency than std::vector. (Comparing the running time of some random case, between implementations using std::deque and std::vector, time(deque) ≈ 2 * time(vector))

    → Reply