שיעור 24: scan מקבילי (prefix sum) — הרעיון
סריקה (scan), או סכום-קידומות (prefix sum), הופכת מערך לסדרת הסכומים המצטברים שלו. בסריקה כוללת (inclusive) המוצא במקום i הוא הסכום של כל האיברים מ-0 עד i כולל: output[i] = in[0] + in[1] + ... + in[i]. למשל [3,1,2,4] הופך ל-[3,4,6,10]. יש גם וריאנט בלעדי (exclusive) שמתחיל מאפס ומזיז כל סכום מקום אח
דמיינו שורה של אנשים, כל אחד מחזיק מספר, וכל אחד צריך להחזיק בסוף את סכום כל מי שלפניו כולל עצמו. במקום ללחוש שכן-לשכן לאט, בכל סיבוב כל אחד מוסיף לעצמו את המספר של מי שעומד צעד אחד שמאלה, אחר כך שני צעדים, אחר כך ארבעה. הקפיצות מוכפלות — והשורה כולה מסיימת בכמה סיבובים בודדים.
- סכום-קידומות (prefix sum / scan)
- המרת מערך לסדרת הסכומים המצטברים שלו. בסריקה כוללת, output[i] הוא הסכום של in[0..i] כולל.
- כוללת מול בלעדית (inclusive vs exclusive)
- כוללת: כל מוצא כולל את האיבר במקומו ([3,1,2,4]->[3,4,6,10]). בלעדית: מתחילה מאפס ומזיזה ימינה ([0,3,4,6]).
- הרעיון המוכפל (doubling)
- בכל סיבוב כל איבר מוסיף את השכן במרחק d, ו-d מוכפל (1,2,4,...). אחרי log2(n) סיבובים כל מקום צבר את כל הקודמים.
- סכום מצטבר (running total)
- הסכום שנצבר עד נקודה מסוימת. בגרסה הסדרתית מחשבים אותו בלולאה אחת ב-O(n) צעדים.