thanhnhan.gl's blog

How to use Splay Tree to solve this problem?
By thanhnhan.gl, history, 8 years ago, In English

My problem is: Given a sequence of integers (a_n): a_1, a_2, ..., a_n. We do Q queries, each of them (l, r) requires reverse elements from a_l to a_r.

For example, Given a sequence: 2, 3, 4, 5. The query (1, 3) changes the sequence into 4, 3, 2, 5.

After performing Q queries, the problem asks us to print out the modified sequence.

How to solve this problem, if n and Q are large integers (such as 10^5)?

I hear that the solution uses an approach of Splay Tree.

Please help me and thank you.

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

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

Auto comment: topic has been updated by thanhnhan.gl (previous revision, new revision, compare).

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

Auto comment: topic has been updated by thanhnhan.gl (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it

//First of all, you need to know how to use a splay tree to solve problems on an sequence.

struct node{
    int son[2];
    int value;
    bool reverse;
};

just maintain the reverse tag when you splay.

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

Hello,i don't now splay tree but this problem can be solved using treap (and i think any balanced binary search tree can do the job).

btw i explained here how the treap work and you can modify the code to solve this problem, soon i will post some explanation for how to solve the "reverse sub-array query" using treap, so now you can check the code here

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

First you need to implement the split and merge operations . Then you need to split the splay tree at the index l , Then again you have to split the right tree at index r-l . The left tree of this split operation holds the segment (l,r) . Now recursively swap the left and right pointers of the tree . After doing the swap operation we have reversed the tree . Now merge the three trees again . All these operation can be done in O(log(n)) amortized time .

Learn more about splay trees here : SplayTree

→ Reply