שאילתות סכום טווח ללא עדכונים


רמת קושי קַל
נשאל לעתים קרובות בלקרוק GE Healthcare מעבדות מונפרוג סינופסיס Taxi4Sure Twilio
מערך לארסן וטוברו בעיית שאילתות

הצהרת בעיה

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

דוגמה

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

הסבר

סכום כל המספרים בין הטווח (0, 4) כולל 40 וסכום המספרים בין הטווח (1, 3) כולל 24.

שאילתות סכום טווח ללא עדכונים

 

אַלגוֹרִיתְם

  1. צור מערך סכום מערך בגודל זהה למערך הנתון.
  2. חצו את המערך הנתון ואחסנו את סכום האלמנט הקודם של sumArray ואת האלמנט הנוכחי של המערך הנתון ואחסנו אותו ב- sumArray.
  3. עבור כל שאילתה, אם השמאל שווה ל- 0, החזר את sumArray [ימין],
  4. אחר החזיר את sumArray [מימין] - sumArray [שמאל - 1].

הסבר

נתנו מערך של מספר שלם וטווח, התבקשנו לברר את סכום כל האלמנטים בטווח הנתון עבור כל שאילתה. כל אחת מהשאילתות מורכבת מטווח כנקודת ההתחלה והסיום של הטווח. שאלה זו אינה כוללת שאילתת עדכון כלשהי. פירוש הדבר שאין צורך לעדכן אף אחד מהדברים תוך כדי בירור תשובת השאילתה. אנו פשוט בונים את המערך הנתון כך שסכום כל האלמנטים מהאינדקס 0 לאינדקס הנוכחי יהיה במיקום ה- I של המערך הבנוי. באופן זה, כל שאילתה תיפתר ב- O (1), עם שטח נוסף של O (n).

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

כאשר נקבל שאילתה המורכבת מכל טווח כלשהו, ​​ואם מצאנו שהנקודה השמאלית או ההתחלה של הטווח שווה ל- 0, פשוט נחזיר את הערך של sumArray [ימין] זה מה שדנו לעיל, האם הטווח השמאלי הוא לא שווה ל- 0 נחזיר את ההפרש של sumArray [ימין] ו- sumArray [שמאל -1]. אלה יהיו תשובות נדרשות. גישה זו היא גם אחת הדרכים הקלות ביותר בה אנו משתמשים תכנות דינמי.

קופונים

קוד C ++ לשאילתות סכום טווח ללא עדכונים

#include<iostream>

using namespace std;

void buildSumArray(int arr[], int n, int sumArray[])
{
    sumArray[0] = arr[0];
    for (int i = 1; i < n; i++)
        sumArray[i] = arr[i] + sumArray[i - 1];
}

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

קוד Java לשאילתות סכום טווח ללא עדכונים

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

ניתוח מורכבות

מורכבות זמן

O (N + Q),  מכיוון שאנחנו צריכים O (N) כדי לחשב את הזמן sumArray ואז את O (1) עבור כל שאילתה.

מורכבות בחלל

כאן בגישה הנתונה יצרנו סכום מערך חדש לאחסון סכום האלמנטים מ- 0 עד i. לפיכך גישה זו דורשת עַל) מֶרחָב. אבל יכולנו גם לשנות את המערך המקורי. ואז מורכבות החלל הייתה מצטמצמת לקבועה.