tom's blog

Reverse & Sum On Interval
By tom, history, 8 years ago, In English

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.

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

Comments Comments (8)
| Write comment?
»
8 years ago, # |
  Vote: I like it +45 Vote: I do not like it

This is quite simple to do using treaps and lazy propagation on them. You can find resources by googling.

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

can you post the link to the question?

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

If you want a solution not using treaps then read Burunduk1's lecture note. (The Split and Rebuild variant)

→ Reply