טווח זמן קבוע להוסיף פעולה במערך


רמת קושי קַל
נשאל לעתים קרובות CodeNation דה שו דירקטי Expedia Google
מערך תכנות דינמי

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

דוגמה

arr[] = {0, 0, 0, 0, 0}

Query: {(0, 2, 50), (3, 4, 20), (1, 3, 30)}
50 80 80 50 20

הסבר

50 מתווסף ל 0 עד 2 במערך, המערך יהפוך {50, 50, 50, 0, 0}

20 מתווסף ל 3 עד 4 במערך, המערך יהפוך {50, 50, 50, 20, 20}

30 מתווסף ל 1 עד 3 במערך, המערך יהפוך {50, 80, 80, 80, 20}

טווח זמן קבוע להוסיף פעולה במערך

 

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

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

הסבר לטווח זמן קבוע להוסיף פעולות במערך

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

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

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

קופונים

יישום ב- C ++ לטווח זמן קבוע להוסיף פעולות במערך

#include<iostream>

using namespace std;

void update(int arr[], int N)
{
    for (int i = 1; i < N; i++)
        arr[i] += arr[i - 1];
}

void addOperation(int arr[], int N, int left, int right, int value)
{
    arr[left] += value;
    if (right != N - 1)
        arr[right + 1] -= value;
}

void printArray(int arr[], int N)
{
    update(arr, N);
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int N = 5;

    int arr[N] = {0};

    addOperation(arr, N, 0, 2, 50);
    addOperation(arr, N, 3, 4, 20);
    addOperation(arr, N, 1, 3, 30);

    printArray(arr, N);
    return 0;
}
50 80 80 50 20

יישום ב- Java לטווח זמן קבוע להוסיף פעולות במערך

class AddOperation
{
    static void update(int arr[], int N)
    {
        for (int i = 1; i < N; i++)
            arr[i] += arr[i - 1];
    }
    static void addOperation(int arr[], int N, int left, int right, int value)
    {
        arr[left] += value;
        if (right != N - 1)
            arr[right + 1] -= value;
    }
    static void printArray(int arr[], int N)
    {
        update(arr, N);

        for (int i = 0; i < N; i++)
            System.out.print(""+arr[i]+" ");
        System.out.print("\n");
    }
    public static void main (String[] args)
    {
        int N = 5;

        int arr[] = new int[N];

        addOperation(arr, N, 0, 2, 50);
        addOperation(arr, N, 3, 4, 20);
        addOperation(arr, N, 1, 3, 30);
        printArray(arr, N);
    }
}
50 80 80 50 20

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

מורכבות זמן

O (N + Q) איפה "N" הוא מספר האלמנטים במערך ו- "ש" הוא מספר השאילתות. מכיוון שהגדלנו את הערך באינדקס שמאל והורדנו את הערך באינדקס ימין + 1 אם הוא קיים בגבול המערך.

מורכבות בחלל

עַל) איפה "N" הוא מספר האלמנטים במערך.