给定数组A[1…N]，它查找具有两个给定索引之间的最小值的元素的位置。
它在常数时间内返回答案。RMQ问题可以用来在常量时间内恢复图中的lca(最低公共祖先)。看到http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor为更多的细节。
时间复杂度:O(N log(N))
空间复杂度:O(N log(N))
例子
A = [-1 5 0 3 -6 4 2 1 0 -1];
N =长度(一个);
M = rmq(一个);
求最小元素在下标i, j之间的位置
我= 2;
j = 6;
k = floor(log2(j - i + 1));
如果A(M(i,k+1)) <= A(M(j-2^k+1,k+1))
idx = M (i (k + 1);
其他的
idx = M (j2 ^ k + 1, k + 1);
结束