سوالات المپیاد:دوره ی تابستان:دوره ی ۲۳:تئوری نهایی اول:سوال ۳
سوال ۳
آرایهای شامل n عدد داریم. میخواهیم با اعمال حافظه و زمان پیشپردازش O(n2) به هر پرسمان از نوع زیر در زمان O(√nlgn) پاسخ دهیم. «از بین اعداد iام تا jام آرایه kامین عدد از نظر بزرگی کدام است.»
با حافظهی O(n) و پیشپردازش O(nlgn) هر پرسمان را در زمان O(n1100) پاسخ دهید.