אנחנו כבר כמה ימים מנסים לפתור בעייה מאוד מסובכת:

הראה מבנה נתונים עם זכרון (O(n ששומר מערך A של מספרים ועונה על השאילתה הבאה:

בהינתן t קטעים זרים על המערך, החזר את k המספרים הגדולים ביותר בקטעים אלו בזמן
O(t + klogk)

עכשיו יש בעייה דומה, שעובדת על מערך ומחזירה על קטע יחיד את האיבר המינימאלי - ב-O(1)
כלומר, בהינתן מערך:
10 32 45 81 34 55 66 22

ואינדקסים i=2 ו-j=4 נקבל: (תת מערך 81 34 55 66) והאיבר המינימאלי הוא 34.
* אולי זה המקום לציין שהאיבר הראשון במערך הוא i=1 ולא i=0 כמו שאנו רגילים בד"כ.

להעביר את הבעייה הזו לבעיית מקסימום - די קל.
מה שקשה הוא להכליל אותה ל-t קטעים(שלא יודעים מהם מראש...) ועדין להגיע לזמן סביר.
חשוב לציין שלא ניתן לדעת איפה כל אחד מה-top-k יהיה, כלומר, האם כל ה-topk יהיו בתת-קטע אחד של המערך, או לא מפוזרים בכולם וכו'.

מה מותר בבעייה?
מותר לעשות preprocessing שיקח כמה זמן שאתם רוצים, אך כמו שהבעיה מתארת אסור לשמור זיכרון גדול מ-O(n).

מה שאני חושב, זה שאי אפשר לשנות באופן דינאמי את תוצאת ה-preprocessing(זה פשוט ידרוש לשנות את כל מבני הנתונים, בעלות גדולה מהעלות שנדרשת - זה כנראה יהיה פונק' של n, וזה לא טוב לנו).

אם מישהו נתקל בבעייה דומה, או מכיר משהו, אפילו קצה חוט, אני(ועוד קבוצה די גדולה של אנשים) תשמח לקבל את עזרתכם.

**להנהלה, אני יודע שחל איסור על בקשות לתשובות מהשיעורי בית, אבל זאת השאלה הכי מאתגרת שנתקלתי בה בתואר לדעתי, ואנחנו באמת צריכים את מיטב המוחות.