Range Sum Query

Q: מהו מערך סכומי קידומות?

מערך שבו כל איבר הוא הסכום של כל הערכים שלפני מיקום מסוים: prefix[i] = nums[0] + ... + nums[i-1] , כאשר prefix[0] = 0 . בונים אותו במעבר אחד, ואז הסכום של כל טווח [left, right] הוא prefix[right+1] - prefix[left] .

Q: מהי סיבוכיות הזמן של שאילתות סכום טווח באמצעות סכומים מקדימים?

O(n) לבניית מערך הקידומות פעם אחת, ואז O(1) לכל שאילתה, כך שהסיבוכיות היא O(n + q) עבור q שאילתות. חיבור ישיר של כל טווח עולה עד O(n) לכל שאילתה, ובסך הכול O(n·q) .

Q: מה אם המערך יכול להשתנות בין שאילתות?

לכן מערך קידומות הוא הכלי הלא נכון, כי כל עדכון מזיז את כל הסכומים שאחריו, ותיקונם עולה O(n) . עץ Fenwick או עץ מקטעים מטפל גם בעדכון וגם בסכום טווח בעלות של O(log n) .

קלסכומי תחיליות

+10

ניתן לך מערך של מספרים שלמים nums שאינו משתנה, ורשימה של queries. כל שאילתה היא זוג [left, right] של אינדקסים שמתחילים ב-0, והיא מבקשת את nums[left] + nums[left+1] + ... + nums[right], כולל שני הקצוות. החזר את התשובות באותו סדר של השאילתות.

פונקציה

sumRange(nums: integer-array, queries: integer-2d-array) → integer-array

numsinteger-array: מערך המספרים השלמים, זהה לכל שאילתה
queriesinteger-2d-array: הטווחים שיש לחבר, כל אחד מהם זוג [left, right] שבו left ≤ right
מחזירהinteger-array: הסכום של כל טווח, אחד לכל שאילתה, לפי סדר השאילתות

אילוצים

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ queries.length ≤ 1500
0 ≤ 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]
הסבר: סכום המערך כולו הוא 18, סכום שני הערכים האחרונים הוא 1 + 8 = 9, סכום אינדקס 0 לבדו הוא 2, וסכום האינדקסים 1 עד 2 הוא 7 + 1 = 8.

שאלת המשך

אם המספרים מסודרים ברשת וכל שאילתה מבקשת את סכום המלבּן, איך תרחיבו סכומי קידומת כדי לענות על כל שאילתה בזמן קבוע?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

טווח יחיד הוא לולאה, אבל כל שאילתה יכולה לכסות את רוב המערך, ולכן חיבור כל טווח בנפרד חוזר על אותן פעולות חיבור. חברו את איברי המערך פעם אחת לסכומי קידומת, ואז כל טווח מסתכם בחיסור אחד.

חברו כל טווח

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

עבור כל שאילתה, הוסף לסכום את הערכים מ־nums[left] ועד nums[right]. זה נכון כי כך קוראים כל ערך בטווח, ועבור שאילתה אחת זה הדבר הטוב ביותר שאפשר לעשות. שאילתה יכולה לכלול עד n ערכים, ולכן העלות של q שאילתות היא עד n × q פעולות חיבור: 1.5 × 10^7 כאשר n = 10^4 ו־q = 1500, וכמעט כולן חוזרות על עצמן.

אלגוריתם

צור רשימת תשובות ריקה.
עבור כל שאילתה [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] מתקבל [0, 3, 1, 6, 7, 3, 9].

הטווח [left, right] הוא הסכום של כל הערכים עד לאינדקס right פחות הסכום של כל הערכים שלפני האינדקס left: prefix[right+1] - prefix[left]. עבור [1, 4] זהו prefix[5] - prefix[1] = 3 - 3 = 0. האפס המוביל מאפשר להשתמש באותה נוסחה עבור טווח שמתחיל באינדקס 0. מעבר אחד של n פעולות חיבור בונה את המערך, ואז כל שאילתה דורשת פעולת חיסור אחת.

אלגוריתם

צרו את 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 במקום 1.
יצירת prefix באורך של nums, כך ש-prefix[i] כולל את nums[i]. טווח שמתחיל ב-0 ידרוש אז את prefix[-1], שנמצא מחוץ לגבולות, ו-Python קוראת בשקט את האיבר האחרון במקום זאת.
עצירת לולאת הכוח הגולמי ב-i < right. שני הקצוות כלולים, ולכן הסכום של [3, 3] יהיה 0.
ב-Lua וב-R, שמתחילות לספור מ-1, השאילתה באינדקסים שמתחילים מ-0 [left, right] מכסה את nums[left+1] עד nums[right+1], וגם אינדקסי הקידומות זזים באותו אופן.

שאלות נפוצות3

מהו מערך סכומי קידומות?

מערך שבו כל איבר הוא הסכום של כל הערכים שלפני מיקום מסוים: 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).

מה אם המערך יכול להשתנות בין שאילתות?

לכן מערך קידומות הוא הכלי הלא נכון, כי כל עדכון מזיז את כל הסכומים שאחריו, ותיקונם עולה O(n). עץ Fenwick או עץ מקטעים מטפל גם בעדכון וגם בסכום טווח בעלות של O(log n).

def sumRange(nums, queries):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

ארגומנטים

nums = [3, -2, 5, 1, -4, 6]
queries = [[0, 2], [1, 4], [3, 3]]

הפלט הצפוי

[6, 0, 1]