שיעור 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) צעדים.