[算法题] 区间最大值问题
给一个很大的数组a，再给m个查询。查询是找出在给定a的某个区间中最大的那个元素。比如a是a= {1,2,3,4,5,6,7,8,9,0} 查询是则回答是4。设计一种算法或数据结构能最快的回答这m个查询。 (提示：做到任何范围查询在O(logn)) 典型的RMQ问题，如果数组是静态的可以做到O(nlogn)预处理，O(1)查询时间。如果数组需要动态更新，也可以通过线段树把update和query都做到O(logn)或者构造一棵树，跟节点是数组最大值，这个index把数组分成了两部分。再次递归取最大值....建好树之后就可以用二分查找得出结果
页:
[1]