- Input：array A[0, N]
- Output： the index of minimum(maximum) value between two given indices.
RMQ的功能是若有一群資料放在array中，在經過preprocessing後，可在O(1)的時間內找出index i~j之間的最小(大)的元素。目前preprocessing最快是O(n)，也就是只需要O(n)的時間就可以處理完成。
以下介紹O(nlog(n))的preprocessing方法，O(n)的方法是由此法去改進，所以先了解此法相當重要且因程式碼容易撰寫，所以也相當適合在ACM中使用。
- 假設array的長度2的n次方。
- 建立一個大小為n x log(n)的矩陣M，用來存放RMQ的結果，其中M[i][j]是指以index i開頭，長度為2^j次方內最小元素的index。
- 使用dynamic programming方法建立M，需O(nlogn) time。
 |  |
 |
- //time complexity: O(nlogn)
- void preprocess(int M[MAXN][LOGMAXN], int A[MAXN], int N)
- {
- int i, j;
-
- //initialize M for the intervals with length 1
- for (i = 0; i < N; i++)
- M[i][0] = i;
- //compute values from smaller to bigger intervals
- for (j = 1; 1 << j <= N; j++)
- for (i = 0; i + (1 << j) - 1 < N; i++)
- if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
- M[i][j] = M[i][j - 1];
- else
- M[i][j] = M[i + (1 << (j - 1))][j - 1];
- }
- //output: the index of the minimum value between index i and j
- int RMQ(int i, int j, int M[MAXN][LOGMAXN], int A[MAXN], int N)
- {
- if(i<0 || i>=N || j<0 || j>=N)
- return -1;
-
- if(i > j) //swap i, j
- i ^= j, j ^= i, i ^= j;
-
- int k = (int)(log(j-i)/log(2.0)),
- rem = j-(1<<k) + 1;
- return (A[M[i][k]] > A[M[rem][k]] ? M[rem][k] : M[i][k]);
- }
Reference：
