Hello everyone!
I've been thinking about solution to the following problem for few days and didn't come up with any reasonable idea. Could you help me out?
You're given array of n elements and q queries. Every query is one of two type:
1) Reverse interval [l, r], e.g. for array 1 2 3 4 5 6 and query [2, 5] we end up with 1 5 4 3 2 6.
2) Ask for sum on interval [l, r].
Thanks and have a nice Sunday.
This is quite simple to do using treaps and lazy propagation on them. You can find resources by googling.
where can i find tutorial for treap in english?
http://lmgtfy.com/?q=treap+tutorial
That was really helpful!
https://threads-iiith.quora.com/Treaps-One-Tree-to-Rule-em-all-Part-2
https://e-maxx-eng.appspot.com/data_structures/treap.html
Burunduk1 code for a treap with reverse.
I honestly don't know how good are these tutorials since I learned about treaps at the university.
As it was mentioned, the problem can be solved using SQRT decomposition
Thank you :)
can you post the link to the question?
If you want a solution not using treaps then read Burunduk1's lecture note. (The Split and Rebuild variant)