Τεχνική αποσύνθεσης Sqrt (ή Square Root)


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις Cadence Ινδία PayPal Qualtrics Roblox 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 ως blockize και διασχίστε τον πίνακα.
  2. Αντιγράψτε την τιμή του πίνακα εισαγωγής στον πίνακα που δημιουργήσαμε και ελέγξτε εάν κάποιο από τα ευρετήρια διαιρείται με blockize εάν στη συνέχεια αυξάνει την τιμή του blockindex κατά 1 και προσθέτει την τιμή arr [i] στο blockArray στο blockindex
  3. Για να συνοψίσετε την τιμή στο δεδομένο εύρος, ορίστε την τιμή του αθροίσματος σε 0.
  4. Ακολουθήστε τους τρεις ενώ βρόχους, έως ότου το αριστερό είναι μικρότερο από την τιμή του δεξιού, το αριστερό δεν πρέπει να είναι μηδέν και το αριστερό δεν πρέπει να είναι η γωνιακή περίπτωση οποιουδήποτε μπλοκ και, στη συνέχεια, προσθέστε την τιμή του πίνακα [αριστερά] στο άθροισμα και αυξήστε το τιμή αριστερά.
  5. Σε αυτό, το αριστερό και το μπλοκ μέγεθος θα πρέπει να είναι μικρότερο από το δεξί και, στη συνέχεια, προσθέστε την τιμή του blockArray στο ευρετήριο ως το τμήμα του αριστερού και του μπλοκ, και προσθέστε την τιμή του μπλοκ στο αριστερό.
  6. Σε αυτό, το αριστερό είναι μικρότερο από το δεξί, προσθέστε την τιμή του πίνακα [αριστερά] στο άθροισμα και αυξήστε την τιμή του αριστερού κατά 1 και επιστρέψτε την τιμή του αθροίσματος.
  7. Για οποιοδήποτε ερώτημα ενημέρωσης, λάβετε τη διαίρεση ευρετηρίου και μπλοκ, και προσθέστε την τιμή που δόθηκε για ενημέρωση και αφαίρεση του πίνακα [ευρετήριο]. Επιτέλους, ενημερώστε την «τιμή» στον πίνακα [index].

εξήγηση

Η αποσύνθεση τετραγωνικής ρίζας είναι μια τεχνική για την επίλυση των ερωτήσεων για τη μείωση της πολυπλοκότητας όσον αφορά την τετραγωνική ρίζα του sqrt (n). Δεδομένου ενός πίνακα και του εύρους ερωτήσεων για να βρείτε το άθροισμα όλων των αριθμών που βρίσκονται στο δεδομένο εύρος κάθε ερωτήματος και μια άλλη εργασία είναι να ενημερώσετε την τιμή στο δεδομένο ευρετήριο. Έτσι, σε αυτό μας δίνονται ορισμένα ερωτήματα, και πρέπει να το λύσουμε, μπορούμε να το λύσουμε χρησιμοποιώντας αφελή προσέγγιση. Σε αυτήν την προσέγγιση θα το λύσουμε επαναλαμβάνοντας κάθε στοιχείο του πίνακα εντός του δεδομένου εύρους αριστερά και δεξιά, και αθροίζοντας όλες τις τιμές που υπάρχουν στο εύρος, αλλά εδώ για αυτήν την προσέγγιση ο χρόνος πολυπλοκότητας για κάθε προσέγγιση θα είναι O (n) .

Έτσι, για να βελτιστοποιήσουμε τα ερωτήματα πιο αποτελεσματικά, θα χρησιμοποιήσουμε την αποσύνθεση τετραγωνικών ριζών, βοηθώντας μας να μειώσουμε την πολυπλοκότητα του χρόνου. Μπορούμε να υποθέσουμε ότι ένας πίνακας μεγέθους n αποτελείται από στοιχεία n. Θα χωρίσουμε τον πίνακα σε μικρά κομμάτια ή μπλοκ μεγέθους sqrt (n). για κάθε τέλειο τετράγωνο ως αριθμός, θα έχουμε ακριβή τεμάχια sqrt (n). Με αυτήν την αποσύνθεση του πίνακα, θα έχουμε μπλοκ sqrt (n) και σε κάθε μπλοκ. Θα έχουμε στοιχεία sqrt (n) εάν το n είναι ένα τέλειο τετράγωνο, όπου το n είναι μέγεθος πίνακα.

Ας υποθέσουμε ότι έχουμε ένα τετράγωνο (16) τετράγωνα αφού το 16 είναι ένα τέλειο τετράγωνο. Θα έχουμε ακριβώς 4 μπλοκ και κάθε μπλοκ θα περιέχει ακριβώς 4 στοιχεία. Σε κάθε μπλοκ θα έχουμε το άθροισμα όλων των στοιχείων που βρίσκονται σε κάθε μπλοκ. Αν λοιπόν ζητήσουμε να μάθουμε το άθροισμα οποιουδήποτε ερωτήματος εύρους. Μπορούμε εύκολα να βρούμε το άθροισμα χρησιμοποιώντας το άθροισμα μπλοκ.

Υλοποίηση σε C ++ για Τεχνική αποσύνθεσης Sqrt (ή Square Root)

#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 (ή Square Root)

Χρόνος πολυπλοκότητας

O (sqrt (n)) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Διαστημική πολυπλοκότητα

O (sqrt (n)) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.