JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Inverse sub-array with the SegTrees
 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 position3) 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?
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Inverse sub-array with the SegTrees Previous Thread  |  Next Thread