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!
It is bad and not-templated though ((
Thank you, that may be exactly what I want!
Here's mine
Thanks.
mine; I choose not to templatize and prefer just to modify the PST for the problem, for example spoj dquery, kth smallest in range
I still stick to tempatizing & formulating every data structure within a mathematical model, but still thank you for advising.
I would highly recommend using
std::dequeinstead ofstd::vectorbecause of two reasons: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::dequeyour implementation could look almost identical to the usual implementation of a persistent segment tree .std::dequehas lower memory overhead thanstd::vector. This is probably not super important, but it is something.Another alternative you could look into is using a bump allocator.
benchmarking agrees! vector 153512865 deque 153583279
I would consider it a great idea, and I will try to implement one. Thanks for advising!
But, seemingly,
std::dequeis less efficiency thanstd::vector. (Comparing the running time of some random case, between implementations usingstd::dequeandstd::vector, time(deque) ≈ 2 * time(vector))