To do this question in O(n) time follow the post "Segment trees" in this post of topcoder http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
Here in this given algorithm preprocessing time in O(n) and query time is O(log n). -- Akshat Sapra Under Graduation(B.Tech) IIIT-Allahabad(Amethi Campus) *--------------------------------------* [email protected] [email protected] rit20009008@ <[email protected]>iiita.ac.in -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
