مساله 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)$ محاسبه شود.

می‌توانیم برای هر پرسش تمام عنصرهای موجود در بازه‌ی مربوطه را بررسی کنیم و جواب کمینه را بدست بیاوریم. به این ترتیب برای جواب‌دادن به هر سوال زمان $\mathcal{O}(n)$ را صرف کرده‌ایم (زیرا بازه‌ی مربوطه در هر پرسش می‌تواند به طول حداکثر کل آرایه یا $n$ باشد)‌. به این ترتیب برای پاسخگویی به همه‌ی پرسش‌ها زمان $\mathcal{O}(nm)$ لازم است.

روش دیگری که می‌توانیم از آن بهره بگیریم این است که در ابتدا (قبل از پاسخگویی به پرسش‌ها) به ازای همه‌ی بازه‌های ممکن جواب را بدست بیاوریم (تعداد بازه‌های مختلف $\binom{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$ در مدت زمان $\mathcal{O}(n^2)$ پر می‌شود. سپس برای هر سوال کافیست $B[L][R]$ را خروجی دهیم. بنابراین مرتبه زمانی الگوریتم بیان شده $\mathcal{O}(n^2+m)$ می‌باشد.

برای بدست آوردن الگوریتمی بهتر آرایه $B$ را به این نحو تعریف می‌کنیم که $B[i][j] = \min(A[i,\ldots, i+2^j-1])$ به این ترتیب برای هر $i$، مقدار $B[i][0]$ برابر $A[i]$ بوده و مقدار $B[i][j]$ به ازای هر $j>0$ برابر $\min(B[i][j-1], B[i+2^{j-1}][j-1])$ می‌باشد. به این ترتیب با استفاده از روش برنامه‌نویسی پویا برای پرکردن خانه‌های آرایه، هر خانه در زمان $\mathcal{O}(1)$ پر شده و تعداد کل خانه ها هم $\mathcal{O}(n \log n)$ می‌باشد (چرا؟‌)، بنابراین پر کردن آرایه $B$ از مرتبه زمانی $\mathcal{O}(n \log n)$ است. حال برای پاسخ به هر سوال تابع بازگشتی $\text{MIN}(l,r,k)$ را به این نحو تعریف می‌کنیم که اگر $k$ کمتر از ۰ بود یا $l$ بزرگتر یا مساوی با $r$ بود، $\text{MIN}(l,r,k) = \infty$ (مقدار $\infty$ را یک عدد بسیار بزرگ در نظر می‌گیریم که اطمینان داشته باشیم هیچگاه جواب پرسش برابر آن نمی‌شود) اگر این شرایط وجود نداشت، و اگر $l+2^k$ کوچکتر مساوی $r$ بود آن وقت $\min(B[l][k], B[r - 2^k][k])$ و در غیر این صورت $\text{MIN}(l, r, k-1)$.

‌‌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
• https://cp-algorithms.com/data_structures/sparse-table.html