جستجوی مینیمم بازه‌ای
در علوم کامپیوتر، یک جستجوی میبنیمم بازه‌ای (Range minimum query) الگوریتمی برای یافتن کوچکترین عنصر در یک زیر آرایه (بازه‌ای از یک آرایه) با عناصر قابل مقایسه است.
الگوریتم جستجوی مینیمم بازه‌ای در علوم و مهندسی کامپیوتر کاربردهای فراوانی دارند. از جمله آنان می‌توان به یافتن (مثلا در درخت یا هرم یا …) یا (LCP) اشاره کرد. ()
با توجه به یک آرایه [A[1 … n از n اشیاء از یک مجموعه منظم(خوش ترتیب) (مانند اعداد)، جستجوی مینیمم بازه‌ای [RMQ A(l,r) =arg min A[k (با ۱ ≤ l ≤ k ≤ r ≤ n ) موقعیت(اندیس ) کوچکترین عنصر را در زیربازه‌ی مشخص شده [A[l … r بازمی‌گرداند.
به عنوان مثال ، وقتی ، آنگاه پاسخ به سؤال از دامنه برای زیر مجموعه A برابر است با ۷. زیرا A[7] = ۱. و پاسخ، موقعیت کوچکترین عنصر در زیربازهٔ مشخص شده را به ما می‌دهد.
در یک مجموعه رایج، آرایه A استاتیک است، یعنی عناصر در طی یک سری پرس و جوها درج یا حذف نمی‌شوند؛ و جستجوهای داده شده باید به صورت درجا پاسخ داده شوند (یعنی کل مجموعه نمایش داده‌ها از قبل با الگوریتم مشخص نیست) در این حالت، پیش پردازش مناسب آرایه در یک داده ساختار، پاسخ سریع تر پرس و جو را تضمین می‌کند. یک راه حل ساده این است که پاسخ تمام جستجوهای ممکن را از قبل حساب کنیم، یعنی مینیمم تمام زیر مجموعه‌های A، و این موارد را در یک آرایه B ذخیره کنید به طوری که [B[i, j] = min(A[i…j) ؛ سپس با استفاده از جستجوی آرایه در B یک جستجوی مینیمم در زمان ثابت حل می‌شود. تعداد (Θ(n² جستجوی مختلف روی آرایه‌ای به طول n وجود دارد، و پاسخ به این سوالات را می‌توان در زمان (Θ(n² توسط برنامه‌نویسی پویا بدست آورد.
مانند راه حل بالا، پاسخ دادن به این سؤالات در زمان ثابت با نتایج از پیش محاسباتی حاصل می‌شود. با این حال، این آرایه جستجوهای مینیمم از پیش محاسبه شده را برای محدوده‌هایی که اندازه آن‌ها توانی از ۲ است برای همه عناصر ذخیره می‌کند. برای هر موقعیت شروع i به تعداد (Θ(log n از این جستجوها وجود دارد، بنابراین اندازه جدول برنامه‌نویسی پویا B برابر با (Θ (n log n است. هر عنصر [B [i, j دارای اندیس مینیمم محدوده [A [i … i + 2^j-1 است. جدول به کمک خاصیت بازگشت از اندیس‌های مینیمم‌ها پر شده‌است.
اگر ،
آن گاه .
در غیر این صورت، .
اکنون با تقسیم آن به دو پرس و جو جداگانه می‌توان به پرس و جو (RMQ A(l,r پاسخ داد: یکی پرس و جو از پیش محاسبه شده با دامنه از l تا بالاترین مرز کوچکتر از r (که طول این بازه توانی از ۲ است). مورد دیگر عبارت است از یک بازه با همان طول که r آن را به عنوان مرز سمت راست خود دارد. این فواصل ممکن است با هم هم پوشانی داشته باشند، اما با توجه به اینکه مینیمم به جای جمع، محاسبه می‌شود، این مهم نیست. نتیجه کلی را می‌توان در زمان ثابت بدست آورد زیرا می‌توان به این دو پرس و جو در زمان ثابت پاسخ داد و تنها کاری که باقی مانده‌است ، انتخاب عنصر کوچکتر بین دو عنصر جواب این دو نتیجه است. (که حتی ممکن است یکی باشند)
این راه حل RMQ را در (O(log n پاسخ می‌دهد. داده ساختار آن حافظه‌ای از مرتبهٔ (O(n می‌گیرد و از این داده ساختار نیز می‌توان برای پاسخ به جستجوها در زمان ثابت استفاده کرد. این آرایه ابتدا از نظر مفهومی به بلوک‌هایی با اندازه formula_1 تقسیم می‌شود. سپس عنصر مینیمم برای هر بلوک در (O(n محاسبه می‌شود و مینیمم‌ها در یک آرایه جدید ذخیره می‌شوند.
اکنون RMQها را می‌توان با مراجعه به بلوک‌های حاوی مرز سمت چپ و راست بازه داده شده در طرفین، و تمام بلوک‌های موجود در زمان لگاریتمی پاسخ دهید:
دو بلوک حاوی مرزها را می‌توان به سادگی جستجو کرد. عناصر خارج از مرز حتی لازم نیست مورد بررسی قرار گیرند. این کار در زمان لگاریتمی قابل انجام است.
مینیمم تمام بلوک‌هایی که به‌طور کامل در محدوده موجود است و دو مینیمم ذکر شده در بالا، برای پاسخ به پرس و جو باید مقایسه شوند. از آنجا که آرایه به بلوک‌هایی با اندازه formula_2 تقسیم شده‌است، حداکثر formula_3 بلوک وجود خواهند داشت که کاملاً در داخل محدوده قرار دارند.
با استفاده از راه حل خطی می‌توان مینیمم کلی را در بین این بلوک‌ها پیدا کرد. این داده ساختار دارای اندازه (O(formula_4 * log(formula_4)) است.
به عنوان مثال، با استفاده از آرایه [A = [۰٬۵٬۲٬۵٬۴٬۳٬۱٬۶٬۳ و اندازه بلوک ۳ (فقط برای اهداف مصور) آرایه مینیمم [A' = [۰٬۳٬۱ را برمی‌گرداند.
با استفاده از راه حل فوق ، زیر محدوده‌های داخل بلوک‌هایی که به‌طور کامل در آن محدوده قرار ندارند ، هنوز هم باید در زمان ثابت پاسخ داده شوند. حداکثر دو بلوک وجود دارد: بلوک حاوی l و بلوک حاوی r . با نگه داشتن درختان دکارتی برای تمام بلوک‌های موجود در آرایه ، زمان ثابت حاصل می‌شود. تعدادی از مشاهدات:
برای هر درخت این چنینی، نتیجه احتمالی برای همه سؤالات باید ذخیره شود. این به ورودی‌های از مرتبه یا بستگی دارد. این بدان معنی است که اندازه کلی جدول (O(n است.
برای جستجوی بهینهٔ نتایج، درخت دکارتی (ردیف) مربوط به یک بلوک خاص باید در زمان ثابت مورد قرار گیرد. راه حل این است که نتایج را برای کلیه درختان در یک آرایه ذخیره کرده و یک تصویرسازی و طرح‌ریزی منحصر به فرد از درختان باینری به اعداد صحیح برای آدرس دهی پیدا کنید. این کار را می‌توان با انجام یک پیمایش درخت روی درخت و اضافه کردن گره‌های برگ بدست آورد به طوری که هر گره موجود در درخت دکارتی دقیقاً دو فرزند داشته باشد. سپس عدد صحیح با به نمایش گذاشتن هر گره درونی به عنوان یک بیت ۰ و هر برگ به عنوان بیت ۱ در یک بیت کلمه (با ) ایجاد می‌شود. این برای هر درخت به اندازه formula_6 منجر می‌شود. برای فعال کردن دسترسی تصادفی در زمان ثابت به هر درخت، درختانی که در آرایه اصلی موجود نیستند نیز باید در آرایه درج شوند. آرایه‌ای با شاخص‌های به طول formula_6 بیت، اندازه‌ای از مرتبهٔ 2 دارند.
RMQها به عنوان ابزاری برای بسیاری از کارها در تطابق دقیق و تقریبی رشته استفاده می‌شوند. چندین کاربرد را می‌توان در مقاله‌های فیشر و هون (۲۰۰۷) یافت.
RMQها می‌توانند برای حل مسئله پایین‌ترین جد مشترک استفاده شوند و به عنوان ابزاری برای بسیاری از کارها در تطابق دقیق و تقریبی رشته استفاده می‌شوند. query از یک درخت ریشه دار و دو گره عمیق‌ترین گره (که ممکن است یا باشد) را در مسیرهای ریشه به هر دو بازمی‌گرداند؛ و گابوو ، بنتلی و تارجان (۱۹۸۴) نشان دادند که مسئله LCA می‌تواند در زمان خطی به مسئله RMQ تقلیل یابد. از این رو نتیجه می‌گیرد که مانند مسئله RMQ، مسئله LCA می‌تواند در زمان ثابت و حافظهٔ خطی حل شود.
الگوریتم جستجوی مینیمم بازه‌ای در علوم و مهندسی کامپیوتر کاربردهای فراوانی دارند. از جمله آنان می‌توان به یافتن (مثلا در درخت یا هرم یا …) یا اشاره کرد.
این مفهوم در برنامه‌های بسیاری بکار می‌رود.
در زمینه نمایه سازی متن، از RMQها می‌توان برای یافتن LCP (طولانی‌ترین پیشوند مشترک) استفاده کرد، جایی که LCP پسوندهایی را که در شاخص‌های و در شروع می‌شود محاسبه می‌کند. برای این کار ابتدا آرایه پسوند و آرایه پسوند معکوس را محاسبه می‌کنیم. سپس LCP آرایه را به کمک LCP پسوندهای مجاور در محاسبه می‌کنیم. پس از محاسبه این ساختارهای داده، و پردازش RMQ کامل می‌شود، طول LCP عمومی را می‌توان در زمان ثابت با فرمول محاسبه کرد: ، جایی که ما برای سادگی فرض می‌کنیم که (در غیر این صورت مبادله می‌کنیم).