پرش به محتویات

پرس و جوی کمینه در بازه (Range Minimum Query)

یک آرایه $A[1..N]$ به شما داده شده است. شما باید به پرس و جوهای ورودی به شکل $(L, R)$ پاسخ دهید که درخواست یافتن عنصر کمینه در آرایه $A$ بین موقعیت‌های $L$ و $R$ (شامل خودشان) را دارند.

مسئله RMQ ممکن است مستقیماً در مسائل ظاهر شود یا در وظایف دیگری مانند مسئله پایین‌ترین جد مشترک (Lowest Common Ancestor) کاربرد داشته باشد.

راه‌حل

رویکردها و ساختمان داده‌های ممکن زیادی برای حل مسئله RMQ وجود دارد.

مواردی که در این سایت توضیح داده شده‌اند در زیر لیست شده‌اند.

ابتدا رویکردهایی که امکان تغییر در آرایه بین پاسخ به پرس و جوها را فراهم می‌کنند:

  • Sqrt-decomposition - به هر پرس و جو در $O(\sqrt{N})$ پاسخ می‌دهد، پیش‌پردازش در $O(N)$ انجام می‌شود. مزایا: یک ساختمان داده بسیار ساده. معایب: پیچیدگی زمانی بدتر.
  • درخت بازه‌ها (Segment tree) - به هر پرس و جو در $O(\log N)$ پاسخ می‌دهد، پیش‌پردازش در $O(N)$ انجام می‌شود. مزایا: پیچیدگی زمانی خوب. معایب: حجم کد بیشتر در مقایسه با سایر ساختمان داده‌ها.
  • درخت فنویک (Fenwick tree) - به هر پرس و جو در $O(\log N)$ پاسخ می‌دهد، پیش‌پردازش در $O(N \log N)$ انجام می‌شود. مزایا: کوتاه‌ترین کد، پیچیدگی زمانی خوب. معایب: درخت فنویک فقط برای پرس و جوهایی با $L = 1$ قابل استفاده است، بنابراین برای بسیاری از مسائل کاربرد ندارد.

و در اینجا رویکردهایی هستند که فقط روی آرایه‌های ایستا کار می‌کنند، یعنی امکان تغییر یک مقدار در آرایه بدون محاسبه مجدد کل ساختمان داده وجود ندارد.

  • جدول پراکنده (Sparse Table) - به هر پرس و جو در $O(1)$ پاسخ می‌دهد، پیش‌پردازش در $O(N \log N)$ انجام می‌شود. مزایا: ساختمان داده ساده، پیچیدگی زمانی عالی.
  • Sqrt Tree - به پرس و جوها در $O(1)$ پاسخ می‌دهد، پیش‌پردازش در $O(N \log \log N)$ انجام می‌شود. مزایا: سریع. معایب: پیاده‌سازی آن پیچیده است.
  • Disjoint Set Union / ترفند آرپا (Arpa's Trick) - به پرس و جوها در $O(1)$ پاسخ می‌دهد، پیش‌پردازش در $O(n)$. مزایا: کوتاه، سریع. معایب: تنها در صورتی کار می‌کند که تمام پرس و جوها از قبل مشخص باشند، یعنی فقط از پردازش آفلاین پرس و جوها پشتیبانی می‌کند.
  • درخت دکارتی (Cartesian Tree) و الگوریتم Farach-Colton and Bender - به پرس و جوها در $O(1)$ پاسخ می‌دهد، پیش‌پردازش در $O(n)$. مزایا: پیچیدگی بهینه. معایب: حجم کد زیاد.

نکته: پیش‌پردازش (Preprocessing) به پردازش اولیه‌ی آرایه داده شده از طریق ساخت ساختمان داده مربوط به آن گفته می‌شود.

مسائل تمرینی