טכניקת פירוק Sqrt (או שורש מרובע)  


רמת קושי קשה
נשאל לעתים קרובות קדנס הודו פייפאל Qualtrics רובלוקס Twilio
מערך בעיית שאילתות

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

עדכון: (אינדקס, ערך) ניתן כשאילתה, שם עליך לעדכן את ערך המערך באינדקס המיקום עם 'הערך'.

סכום: (שמאלה, ימין) ניתנת לשאילתה, סיכמו את כל המספרים שמגיעים בטווח.

דוגמה  

קֶלֶט

arr [] = {2,4,7,1,5,8,9,10,3,6}

שאילתת סכום (0, 3)

שאילתת סכום (4, 9)

עדכון (5, 8)

שאילתת סכום (3, 7)

תְפוּקָה

14 סכום המספרים בטווח 0 ו -3 הוא 14 (2 + 4 + 7 + 1)

41 סכום המספרים בטווח 4 ו -9 הוא 41 (5 + 8 + 9 + 10 + 3 + 6)

עדכון הערך במערך [5] כ- 8.

33 סכום המספרים בטווח 0 ו -3 הוא 14 (1 + 5 + 8 + 9 + 10)

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

  1. קבל את ערך השורש הריבועי של n כגודל חסום וחצה את המערך.
  2. העתק את הערך של מערך הקלט למערך שיצרנו ובדוק אם אחד מהאינדקסים ניתן לחלוקה לפי קוביות גודל אם הוא מגדיל את הערך של blockindex ב- 1 ומוסיף את ערך arr [i] ל- blockArray ב- blockindex.
  3. לסיכום הערך בטווח הנתון, הגדר את ערך הסכום ל- 0.
  4. עקוב אחר שלושת הלולאות, עד שהשמאל קטן מערך הימין, שמאל לא צריך להיות אפס ושמאל לא צריך להיות המקרה הפינתי של בלוק כלשהו, ​​ואז הוסף את ערך המערך [שמאל] לסכום והגדיל את ערך השמאל.
  5. בזה, גודל שמאל פלוס חסם צריך להיות פחות מימין, ואז הוסף את הערך של blockArray באינדקס כחלוקה של שמאל ובלוק-סייז, והוסף את הערך של גודל בלוק לשמאל.
  6. בכך שמאל קטן מימין, הוסף את ערך המערך [שמאל] לסכום והגדיל את ערך השמאל ב- 1 והחזיר את ערך הסכום.
  7. עבור כל שאילתת עדכון, קבל את חלוקת האינדקס וגודל החסימה, והוסף את הערך שניתן לעדכון והחסר את המערך [אינדקס]. בסוף עדכן את 'הערך' במערך [אינדקס].
ראה גם
K חריצים ריקים

הסבר  

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

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

נניח שיש לנו קוביות sqrt (16) שכן 16 הוא ריבוע מושלם. יהיו לנו 4 בלוקים בדיוק וכל בלוק יכיל בדיוק 4 אלמנטים. בכל בלוק יהיה לנו סכום כל האלמנטים השוכבים בכל בלוק. אז אם אנו מבקשים לברר את סכום כל שאילתת טווח. אנו יכולים למצוא את הסכום בקלות באמצעות סכום בלוקים.

ראה גם
תכנון מבנה נתונים

יישום ב- C ++ עבור טכניקת פירוק Sqrt (או ריבוע שורש)  

#include<iostream>
#include<math.h>

using namespace std;


int arr[10000];
int blockArray[100];
int blockSize;

void buildArray(int input[], int n)
{
    int blockIndex = -1;

    blockSize = sqrt(n);

    for (int i=0; i<n; i++)
    {
        arr[i] = input[i];
        if (i%blockSize == 0)
        {
            blockIndex++;
        }
        blockArray[blockIndex] += arr[i];
    }
}

void update(int index, int value)
{
    int blockNumber = index / blockSize;
    blockArray[blockNumber] += value - arr[index];
    arr[index] = value;
}

int solveQuery(int left, int right)
{
    int sum = 0;
    while (left<right and left%blockSize!=0 and left!=0)
    {
        sum += arr[left];
        left++;
    }
    while (left+blockSize <= right)
    {
        sum += blockArray[left/blockSize];
        left += blockSize;
    }
    while (left<=right)
    {
        sum += arr[left];
        left++;
    }
    return sum;
}

int main()
{
    int inputArray[] = {2,4,7,1,5,8,9,10,3,6};
    int n = sizeof(inputArray)/sizeof(inputArray[0]);

    buildArray(inputArray, n);

    cout << "first Query : " << solveQuery(0, 3) << endl;
    cout << "second Query : " << solveQuery(4, 9) << endl;
    update(5, 8);
    cout << "third Query : " << solveQuery(3, 7) << endl;
    return 0;
}
first Query : 14
second Query : 41
third Query : 33

יישום ב- Java עבור טכניקת פירוק Sqrt (או Square Root)  

class SquareRootDecomposition
{

    static int []arr = new int[10000];
    static int []blockArray = new int[100];
    static int blockSize;

    static void buildArray(int input[], int n)
    {
        int blockIndex = -1;

        blockSize = (int) Math.sqrt(n);

        for (int i = 0; i < n; i++)
        {
            arr[i] = input[i];
            if (i % blockSize == 0)
            {
                blockIndex++;
            }
            blockArray[blockIndex] += arr[i];
        }
    }

    static void update(int idx, int val)
    {
        int blockNumber = idx / blockSize;
        blockArray[blockNumber] += val - arr[idx];
        arr[idx] = val;
    }

    static int solveQuery(int left, int right)
    {
        int sum = 0;
        while (left<right && left%blockSize!=0 && left!=0)
        {
            sum += arr[left];
            left++;
        }
        while (left+blockSize <= right)
        {
            sum += blockArray[left/blockSize];
            left += blockSize;
        }
        while (left<=right)
        {
            sum += arr[left];
            left++;
        }
        return sum;
    }

    public static void main(String[] args)
    {
        int input[] = {2,4,7,1,5,8,9,10,3,6};
        int n = input.length;

        buildArray(input, n);

        System.out.println("first Query: " + solveQuery(0, 3));
        System.out.println("second Query : " + solveQuery(4, 9));
        update(5, 8);
        System.out.println("third Query : " + solveQuery(3, 7));
    }
}
first Query: 14
second Query : 41
third Query : 33

ניתוח מורכבות לטכניקת פירוק Sqrt (או שורש מרובע)  

מורכבות זמן

O (sqrt (n)) איפה "N" הוא מספר האלמנטים במערך.

ראה גם
תוצר של מערך למעט עצמי

מורכבות בחלל

O (sqrt (n)) איפה "N" הוא מספר האלמנטים במערך.