JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Inverse sub-array with the SegTrees | Reply
Can segment trees be used to solve these tasks in O(log(n))?

1) Inverse order of the elements of an array in range [i..j]
2) Query element standing in the i-th position
3) RMQ/RSQ in the same array
Re: Inverse sub-array with the SegTrees (response to post by mincer) | Reply
I don't think so.
Re: Inverse sub-array with the SegTrees (response to post by mincer) | Reply
Actually yes. I've seen a lecture (in Russian) by VitalyGoldstein describing a structure that can do that and much more.

The idea there is to use a cartesian tree with random priority-queue-keys (so in fact it works in O(log(n)) expected time) and implicit BST-keys. Implicit means that the keys aren't actually stored, but assumed to be 1..n as in inorder traversal. Storing the sizes of sub-trees at each nodes helps traverse the tree. You will also need merge and split operations.

Merging two trees with implicit keys 1..n and 1..m works as if the second tree had keys (n+1),(n+2)...(n+m). Basically it allows appending one array after the other in logarithmic time.

Reversing the order of elements in a range works then using the lazy update technique - split the tree two times (at boundaries of the interval), lazily update the middle tree and merge them back in correct order.

Querying element at i-th position is simply an elementAtRank query.

Basically you get an "array" that supports joining, reversing, splitting and the range queries you mentioned in log-time. However "indexing" the array is also log-time.

EDIT: So it's not really a segment tree, but the principles are very similar.
Re: Inverse sub-array with the SegTrees (response to post by mincer) | Reply
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
Re: Inverse sub-array with the SegTrees (response to post by VladBelous) | Reply
Please could you post a link to the tutorial that shows how to implement a data structure that supports these operations?
RSS