שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2011 - סיבוכיות זמן

נתון מערך $A$ של $n$ מספרים (לא ממוינים). עלינו לבצע עיבוד מקדים בזמן לינארי, כך שלאחר מכן בהינתן שאילתא $(L,R)$ עבור $1 \le L < R \le n$ נוכל להחזיר את הסכום של תת המערך $A[L,\dots,R]$ בזמן $O(1)$. תארו כיצד נבצע את העיבוד המקדים, מהם הערכים אותם נשמור, וכיצד נענה על כל שאילתא.

רמז: חשבו כיצד ניתן לחשב מראש, בזמן לינארי, את הסכומים של כל תתי-המערכים שמתחילים באינדקס הראשון. לאחר מכן, הראו כיצד ניתן להשתמש במידע זה כדי לחשב סכום של כל תת-מערך $A[L..R]$ בפעולה אריתמטית אחת.

פתרון: על מנת לענות על שאילתות סכום בטווח בזמן קבוע ($O(1)$) לאחר עיבוד מקדים לינארי ($O(n)$), נשתמש בטכניקה של **מערך סכומים מתחיליים** (Prefix Sum Array). **שלב העיבוד המקדים:** ניצור מערך עזר חדש, נקרא לו $P$, בגודל $n+1$. כל תא $P[i]$ במערך זה יכיל את סכום כל האיברים במערך המקורי $A$ מהאינדקס הראשון ועד לאינדקס $i$. כלומר, $P[i] = \sum_{j=1}^{i} A[j]$. נגדיר את המערך $P$ באופן הבא: 1. נאתחל את $P[0] = 0$. 2. נחשב את שאר ערכי המערך $P$ באופן איטרטיבי בלולאה מ-$i=1$ עד $n$: $P[i] = P[i-1] + A[i]$ **ניתוח סיבוכיות העיבוד המקדים:** הבנייה של המערך $P$ דורשת מעבר יחיד על המערך $A$. הלולאה רצה $n$ פעמים, ובכל איטרציה מתבצעת פעולת חיבור אחת והשמה אחת. לכן, **סיבוכיות הזמן** של העיבוד המקדים היא $O(n)$, כנדרש. **סיבוכיות המקום** הנוספת היא $O(n)$ עבור שמירת המערך $P$. **הערכים הנשמרים:** המידע היחיד שצריך לשמור לאחר העיבוד המקדים הוא מערך הסכומים המתחיליים $P$. **מענה על שאילתא $(L,R)$:** בהינתן שאילתא לחשב את סכום תת-המערך $A[L, \dots, R]$, נוכל להשתמש במערך $P$ כדי לקבל את התשובה בזמן קבוע. הסכום המבוקש הוא $\sum_{i=L}^{R} A[i]$. ניתן לבטא סכום זה באמצעות ערכים מתוך $P$: $\sum_{i=L}^{R} A[i] = (A[1] + \dots + A[R]) - (A[1] + \dots + A[L-1])$ על פי הגדרת המערך $P$, ביטוי זה שקול ל: $S(L,R) = P[R] - P[L-1]$ **ניתוח סיבוכיות השאילתא:** חישוב התשובה לשאילתא דורש שתי גישות למערך $P$ ופעולת חיסור אחת. כל הפעולות הללו לוקחות זמן קבוע, ולכן **סיבוכיות הזמן** למענה על שאילתא היא $O(1)$, כנדרש. לסיכום, על ידי בניית מערך סכומים מתחיליים $P$ בזמן לינארי, אנו יכולים לענות על כל שאילתת סכום בטווח בזמן קבוע. $\blacksquare$