مساله Range Minimum Query، یافتن مقدار کمینه یک زیر‌آرایه از آرایه می باشد.
آرایه‌ای شامل $n$ عنصر خوش ترتیب (‌مثلا اعداد طبیعی) و $m$ پرسش به صورت بازه‌های $(L_i,R_i]$ که $0 \leq L_i \leq R_i < n$ داده‌شده است. به ازای هر $0 \leq i < m$ باید کوچکترین عضو آرایه در بازه‌ی $(L_i,R_i]$ محاسبه شود.

می‌توانیم برای هر پرسش تمام عنصرهای موجود در بازه‌ی را بررسی کنیم و جواب کمینه را بدست بیاوریم. به این ترتیب برای جواب دادن به هر سوال زمان (O(n را صرف کرده‌ایم (زیرا بازه‌ی داده شده در پرسش می‌تواند به طول حداکثر کل آرایه یا n باشد.)‌ به این ترتیب برای پاسخگویی به همه‌ی پرسش‌ها زمان (O(nm لازم است.
روش دیگری که می‌توانیم از آن بهره بگیریم این است که در ابتدا (قبل از پاسخگویی به پرسش‌ها) به ازای همه‌ی بازه‌های ممکن جواب را بدست بیاوریم (تعداد بازه‌های مختلف (C(n,2 می‌باشد.) سپس برای هر پرسش، جوابی که از قبل بدست آورده‌ایم را خروجی دهیم. برای بدست آوردن جواب به ازای همه‌ی بازه‌ها، آرایه ۲ بعدی ‌ B را به این نحو تعریف می‌کنیم که [B[l][r مقدار مینیمم در بازه (l,r] از آرایه باشد، به این ترتیب به ازای هر i ( که در اینجا i مقداری بین صفر تا n-1 است) ‌، [B[i][i+1] = A[i و به ازای هر (i , j (j>i+1 هم ([B[i][j] = min(B[i][j-1], A[j-1 تعریف می شود. بنابراین با استفاده از رابطه بازگشتی ذکر شده و روش پویا، آرایه B در مدت زمان (O(n^2 پر می شود. سپس برای هر سوال کافیست [B[L][R را خروجی دهیم. بنابراین مرتبه زمانی الگوریتم بیان شده(O(n^2+m می باشد.

برای بدست آوردن الگوریتم بهینه آرایه B را به این نحو تعریف می کنیم که ‌([B[i][j] = MIN(A[i…i+2^j-1 به این ترتیب برای هر i، مقدار ‌[B[i][0 برابر [A[i بوده و مقدار به ازای هر j>0 مقدار ([B[i][j] = min(B[i][j-1], B[i+2^(j-1)][j-1 می باشد. به این ترتیب با استفاده از روش پویا برای پر کردن خانه های آرایه، هر خانه در زمان (O(1 پر شده و تعداد کل خانه ها هم (O(nlogn می باشد ( چرا؟‌ ) بنابراین پر کردن آرایه B از مرتبه زمانی (O(nlogn است. حال برای پاسخ به هر سوال تابع بازگشتی (MIN(l,r,k را به این نحو تعریف می کنیم که اگر k کمتر از ۰ بود یا l بزرگتر یا مساوی با r بود، MIN(l,r,k) = inf ( مقدار inf را یک عدد بسیار بزرگ در نظر می گیریم که اطمینان داشته باشیم هیچگاه جواب به سوال برابر آن نمی شود) اگر این شرایط وجود نداشت، اگر l+2^k کوچکتر مساوی r بود آن وقت ((MIN(l,r,k) = min(B[l][k], MIN(l+2^k,r,k-1 وگرنه (MIN(l,r,k) = MIN(l,r,k-1. در واقع می توان گفت این تابع، بازه ی داده شده را به بازه هایی به طول توانی از ۲( که جواب را قبلا برای آنها بدست آوردیم ) تقسیم کرده و مینیمم آنها را بدست می آورد. به این ترتیب برای یک سوال، (MIN(L,R,[logn]+1 مقدار مینیمم در بازه خواسته شده را در زمان (O(logn به ما می دهد. ( چرا؟‌ ) به این ترتیب به تمامی سوالات در زمان (O(mlogn پاسخ داده میشود و بنابراین مرتبه زمانی این الگوریتم (O((n+m)logn می باشد.

‌‌rmq.cpp

#include<iostream>
 
using namespace std;
 
const int maxn = 100 * 1000, maxlog=20, inf = 1000 * 1000 * 1000;
 
int A[maxn], B[maxn][maxlog], n;
 
void preprocess()
{
	for(int i = 0; i < n ; i++)
		B[i][0]=A[i];
	for(int j = 1; j < maxlog ; j++)
		for(int i = 0; i < n ; i++)
		{
			if(i + ( 1 << ( j - 1 ) ) < n)
				B[i][j]=min( B[i][j-1], B[i + ( 1 << ( j - 1 ) )][j-1] );
			else
				B[i][j] = B[i][j-1];
		}
}
 
int MIN(int l, int r, int k)
{
	if(l >= r || k < 0) return inf;
	if(l + (1 << k) <= r) return min( B[l][k], MIN(l + (1 << k), r, k-1) );
	else return MIN(l, r, k-1);
 
}
 
int query(int L, int R)
{
	return MIN(L, R, maxlog-1);
}
 
int main()
{
	cin >> n;
	for(int i = 0 ; i < n ; i++)
		cin >> A[i];
	preprocess();
	int m;
	cin >> m;
	for(int i = 0 ; i < m ; i++)
	{
		int L, R;
		cin >> L >> R;
		cout << query ( L, R );
	}
	return 0;
}

محاسبه پایین ترین جد مشترک و محاسبه طولانی ترین پیشوند مشترک در رشته

• https://en.wikipedia.org/wiki/Range_minimum_query