مساله 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