I know how to convert an array to a cartesian tree in O(n) time
- http://en.wikipedia.org/wiki/Cartesian_tree#Efficient_construction and
- http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#From RMQ to LCA
However, the amount of memory required is too high (constants) since I need to associate a left and right pointer at least with every node in the cartesian tree.
Can anyone link me to work done to reduce these constants (hopefully to 1)?
You can use a heap to store your tree, essentially it is an array where the first element int he array is the root, the second is the left child of the root the third the right, etc.. it is much cheaper but requires a little more care when programming it.
http://en.wikipedia.org/wiki/Binary_heap