THUẬT TOÁN ỨNG DỤNG QUY HOẠCH ĐỘNG Range Minimum Query 1 Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn Bài toán Range Minimum Query RMQ  Cho dãy a[0], a[1], …, a[N-1]. Với mỗi bộ chỉ số 0 ≤ i < j ≤ N -1, hãy thực hiện truy vấn RMQ(i, j) tìm và trả về chỉ số của phần tử nhỏ nhất trong dãy con a[i], a[i+1],…, a[j]. 0 2 1 4 2 6 3 1 4 6 5 8 6 7 7 3 8 3 9 5 10 11 12 8 9 1 RMQ(1,7) = 3 RMQ(6,11) = 7 2 Bài toán Range Minimum Query RMQ  Ký hiệu M[j, i] là chỉ số phần tử nhỏ nhất của dãy a[i], a[i+2],…, a[i+2j -1] (dãy bắt đầu từ chỉ số i và có độ dài là 2j). 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 4 6 1 6 8 7 3 3 5 8 9 1 2 6 4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 0 1 3 3 4 6 7 8 8 9 10 12 12 13 15 2 3 3 3 3 7 8 8 8 8 12 12 12 12 3 3 3 3 3 8 12 12 12 12 4 12 Bài toán Range Minimum Query RMQ  Bài toán con nhỏ nhất M[0,i] = i, i = 0,…, N-1  Công thức truy hồi  M[j,i] = M[j-1,i] nếu a[M[j-1,i]] < a[M[j-1,i+2j-1] M[j-1,i+2j-1], ngược lại i i+2j-1 -1 i + 2j - 1 i + 2j-1 M[j-1,i + 2j-1] M[j-1,i] 4 M[j, i] Bài toán Range Minimum Query RMQ preprocessing(){ for (i = 0; i < N; i++) M[0,i] = i; for (j = 0; 2j ≤ N; j++){ for(i = 0; i + 2j -1 < N; i++){ if a[M[j-1,i]] < a[M[j-1,i+2j-1]] then{ M[j,i] = M[j-1,i]; }else{ M[j,i] = M[j-1,i+2j-1]; } } } } 5 Bài toán Range Minimum Query RMQ  Truy vấn RMQ(i,j)  k = [log(j-i+1)]  RMQ(i,j) = M[k,i] nếu a[M[k,i]] ≤ a[M[k, j-2k+1]] M[k, j-2k+1]], ngược lại  RMQ(4,14) = ?  k = [log(14-4+1)]=3  a[7] > a[12]  RMQ(4,14) = 12 6 M[3,7] = 12 0 1 2 3