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.