区间最大值问题

给一个很大的数组a， 再给m个查询。查询是找出在给定a的某个区间中最大的那个元素。比如a是
a= {1,2,3,4,5,6,7,8,9,0} 查询是[0,3]则回答是4。设计一种算法或数据结构能最快的回答这m个查询。 (提示：做到任何范围查询在O(logn))

感觉应该是某种树吧。。把每个分支的最大值都储存在树枝上？

典型的RMQ问题，如果数组是静态的可以做到O(nlogn)预处理，O(1)查询时间。如果数组需要动态更新，也可以通过线段树把update和query都做到O(logn)。

典型的RMQ问题，如果数组是静态的可以做到O(nlogn)预处理，O(1)查询时间。如果数组需要动态更新，也可以通过线段树把update和query都做到O(logn)。
darksteel 发表于 2011-6-6 12:34

    有点像线段数，不过好像是点树

构造一棵树，跟节点是数组最大值，这个index把数组分成了两部分。
再次递归取最大值....

建好树之后就可以用二分查找得出结果

用sparse table