Range Sum Query
נתון לך מערך של מספרים שלמים nums שאינו משתנה ורשימה של queries. כל שאילתה היא זוג [left, right] של אינדקסים שמתחילים מ־0, והיא מבקשת לחשב את nums[left] + nums[left+1] + ... + nums[right], כולל שני הקצוות. החזר את התשובות באותו סדר כמו השאילתות.
פונקציה
- numsinteger-array
- מערך המספרים השלמים, זהה עבור כל שאילתה
- queriesinteger-2d-array
- הטווחים שיש לחבר, כל אחד מהם זוג [left, right] שבו left ≤ right
- מחזירהinteger-array
- הסכום של כל טווח, אחד לכל שאילתה, לפי סדר השאילתות
אילוצים
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ left ≤ right < nums.lengthעבור כל שאילתה[left, right]
דוגמאות
- קלט
- nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
- פלט
- [6, 0, 1]
- הסבר
- האינדקסים 0 עד 2 מכילים
3 + (-2) + 5 = 6. האינדקסים 1 עד 4 מכילים-2 + 5 + 1 + (-4) = 0. הטווח[3, 3]הוא הערך היחיד1.
- קלט
- nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
- פלט
- [18, 9, 2, 8]
- הסבר
- הסכום של כל המערך הוא
2 + 7 + 1 + 8 = 18, של שני הערכים האחרונים הוא1 + 8 = 9, של אינדקס 0 בלבד הוא2, ושל האינדקסים 1 עד 2 הוא7 + 1 = 8.
+14 בדיקות נסתרות בשליחה
שאלת המשך
כעת המספרים יוצרים רשת, וכל שאילתה מבקשת את סכום המלבּן שמוגדר על ידי שתי פינות. איך היית מרחיב את סכומי הקידומות כדי לענות על כל שאילתה במספר קבוע של פעולות?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
שאילתות רבות מכסות כמעט את אותם ערכים. איזו עבודה תוכל לבצע פעם אחת, לפני שתקרא שאילתה כלשהי?
אם היית יודע את הסכום של
iהערכים הראשונים עבור כלi, טווח היה ההפרש בין שניים מהסכומים האלה.בנה את
prefixבעזרתprefix[0] = 0ו-prefix[i+1] = prefix[i] + nums[i]. לאחר מכן, כל שאילתה[left, right]היאprefix[right+1] - prefix[left].
פתרון
טווח אחד הוא לולאה. הבעיה היא מספר הטווחים: כל שאילתה יכולה לכסות את רוב המערך, ולכן חיבור כל אחת מהן בנפרד חוזר על אותן פעולות חיבור שוב ושוב. מחברים את הכול פעם אחת לסכומי קידומות, ואז כל טווח דורש חיסור אחד.
חברו את כל הטווחים
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
ענה על כל שאילתה בנפרד: התחל את הסכום ב־0, הוסף את nums[left] עד nums[right], ושמור את התוצאה. עבור [1, 4] בתוך [3, -2, 5, 1, -4, 6], הסכום הוא -2 + 5 + 1 + (-4) = 0.
הפתרון נכון, ולשאילתה יחידה הוא הטוב ביותר שאפשר: צריך לקרוא כל ערך בטווח פעם אחת. המחיר הוא החזרה. שאילתה יכולה לכלול עד n ערכים, ולכן q שאילתות דורשות עד n × q פעולות חיבור. עבור n = 10^4 ו־1500 שאילתות שכל אחת מהן מכסה את רוב המערך, מדובר בכ־1.3 × 10^7 פעולות חיבור, שכמעט כולן חוזרות על עבודה שבוצעה עבור שאילתה קודמת.
מלבד רשימת התשובות, נשמר סכום אחד, ולכן המקום הנוסף הוא O(1).
אלגוריתם
- צור רשימת תשובות ריקה.
- עבור כל שאילתה
[left, right], הגדרtotal = 0. - הוסף את
nums[i]ל-totalעבור כלiמ-leftעדright, כולל שניהם. - הוסף את
totalלתשובות, והחזר אותן לאחר השאילתה האחרונה.
def sumRange(nums, queries):
answers = []
for left, right in queries:
total = 0
for i in range(left, right + 1):
total += nums[i]
answers.append(total)
return answersסכומי קידומות
האינטואיציה
נסמן ב-prefix[i] את הסכום של i הערכים הראשונים, כאשר prefix[0] = 0 עבור התחלה ריקה. עבור [3, -2, 5, 1, -4, 6] מתקבל prefix = [0, 3, 1, 6, 7, 3, 9]. כל איבר הוא האיבר שלפניו ועוד ערך אחד, ולכן בניית המערך כולו דורשת n פעולות חיבור.
הטווח [left, right] הוא כל מה שנמצא עד וכולל האינדקס right, פחות כל מה שנמצא לפני האינדקס left. כלומר, prefix[right+1] - prefix[left]. עבור [1, 4]: prefix[5] - prefix[1] = 3 - 3 = 0. עבור [0, 2]: prefix[3] - prefix[0] = 6 - 0 = 6. ה-0 המוביל הוא מה שמאפשר לטווח שמתחיל באינדקס 0 לעבוד בלי מקרה מיוחד.
בניית המערך עולה O(n), וכל שאילתה עולה לאחר מכן פעולת חיסור אחת, ולכן סיבוכיות הזמן הכוללת היא O(n + q) והשטח הנוסף הוא O(n). אף סכום קידומת כאן אינו עולה בגודלו על 10^4 × 10^4 = 10^8, ולכן מספרים שלמים בני 32 סיביות מספיקים.
אלגוריתם
- יוצרים את
prefixבאורךn+1, כאשרprefix[0] = 0. - עבור כל
iמ-0עדn-1, מציביםprefix[i+1] = prefix[i] + nums[i]. - עבור כל שאילתה
[left, right], מוסיפים אתprefix[right+1] - prefix[left]לתשובות. - מחזירים את התשובות.
def sumRange(nums, queries):
# prefix[i] is the sum of the first i values, so prefix[0] = 0.
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
# nums[left..right] is the first right+1 values minus the first left values.
return [prefix[right + 1] - prefix[left] for left, right in queries]
מלכודות ומקרי קצה
כמעט כל הבאגים כאן נובעים מאינדקס שגוי בהפרש של אחד.
- כתיבת
prefix[right] - prefix[left]. כאשרprefix[0] = 0, הפעולה משמיטה אתnums[right], ולכן הטווח[3, 3]מחזיר0במקום את הערך באינדקס 3. - בניית
prefixבאורך זהה לזה שלnums, כך ש-prefix[i]כולל אתnums[i]. במקרה כזה, טווח שמתחיל ב-0דורש אתprefix[left-1], שנמצא מחוץ לתחום, וב-Python נקרא בשקט את האיבר האחרון. הוספת0בתחילת המערך מונעת את המקרה החריג הזה. - עצירת הכוח הגס בתנאי
i < right. שני קצות הטווח נכללים. - שוכחים שב-Lua וב-R הספירה מתחילה ב-1. השאילתה
[left, right], שמבוססת על אינדקסים המתחילים ב-0, מכסה שם אתnums[left+1]עדnums[right+1], וגם הפרש הסכומים המצטברים זז באותו אופן. - שימוש בסכום של 32 סיביות כשהערכים או האורכים גדלים. כאן הסכום המרבי הוא
10^8, אבל עם ערכים הקרובים ל-10^9סכום מצטבר גולש במהירות, ומערך של 64 סיביות הוא ברירת המחדל הבטוחה.
שאלות נפוצות4
מהו מערך סכומי קידומות?
זהו מערך שבו כל איבר הוא הסכום של כל הערכים שלפני מיקום: prefix[i] = nums[0] + ... + nums[i-1], כאשר prefix[0] = 0. בונים אותו במעבר אחד, ולאחר מכן הסכום של כל טווח [left, right] הוא prefix[right+1] - prefix[left], חיסור אחד.
מהי סיבוכיות הזמן של שאילתות סכום בטווח באמצעות סכומים מצטברים?
O(n) כדי לבנות את מערך הקידומות פעם אחת, ואז O(1) לכל שאילתה, כלומר O(n + q) עבור q שאילתות. חיבור ישיר של כל טווח עולה עד O(n) לכל שאילתה, כלומר O(n·q) בסך הכול.
למה למערך הקידומות יש איבר אחד יותר מאשר ל־nums?
הערך הנוסף prefix[0] = 0 מייצג את תחילת המערך הריקה. בעזרתו, כל טווח משתמש באותה נוסחה, כולל טווחים שמתחילים באינדקס 0: prefix[right+1] - prefix[0]. בלעדיו, צריך תנאי נפרד עבור left = 0.
מה אם המערך יכול להשתנות בין שאילתות?
לכן מערך קידומות הוא כלי לא מתאים, כי עדכון אחד מזיז את כל הסכומים שאחריו, ותיקונו עולה O(n). עץ Fenwick או עץ מקטעים מטפל גם בעדכון וגם בסכום טווח בעלות של O(log n). כשהמערך אינו משתנה לעולם, סכומי קידומות רגילים מהירים וקצרים יותר.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def sumRange(nums, queries):
# כתבו כאן קודמקרה 1
מקרה 2
קלט
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
צפוי
[6, 0, 1]