پرسش محدودهای در علوم کامپیوتر
پرسش محدودهای در علوم کامپیوتر به یافتن کارآمد پاسخهایی برای بازههای مشخص در آرایهها میپردازد. برای مثال، یافتن کوچکترین مقدار در یک محدوده از اعداد، موسوم به پرسش حداقل محدودهای، یکی از کاربردهای رایج است.
تعریف
پرسش محدودهای روی یک آرایه، دو شاخص را دریافت کرده و نتیجه یک تابع را روی زیرآرایه مربوطه برمیگرداند. برای مثال، در تابعی که جمع عناصر را محاسبه میکند، پرسش محدودهای جمع عناصر در آن بازه را برمیگرداند.
راهحلها
آرایه پیشوندی: با پیشپردازش، پرسشهای جمع محدودهای را در زمان ثابت پاسخ میدهد.
پرسشهای پویا: برای دادههای پویا، ساختار دادههایی مانند درخت بخش استفاده میشود.
مثالها
عملگرهای شبهگروه: برای عملگرهایی مانند حداقل، راهحلهای کارآمدتری وجود دارد.
مُد: یافتن مُد در یک محدوده با استفاده از ساختار دادههای خاص انجام میشود.
میانه: یافتن میانه در یک محدوده با الگوریتمهایی مانند quickselect امکانپذیر است.