Sqrt (ან კვადრატული ფესვი) დაშლის ტექნიკა  


Რთული ტური Hard
ხშირად ეკითხებიან კადენს ინდოეთი PayPal Qualtrics რობლოქსი Twilio
Array შეკითხვის პრობლემა

თქვენ გეძლევათ მთლიანი დიაპაზონის მოთხოვნა მასივი. თქვენ მოგეთხოვებათ განსაზღვროთ ყველა რიცხვის ჯამი, რომელიც მოცემული მოთხოვნის დიაპაზონშია. მოცემული მოთხოვნა არის ორი სახის, ესენია -

განახლება: (ინდექსი, მნიშვნელობა) მოცემულია მოთხოვნის სახით, სადაც თქვენ უნდა განაახლოთ მასივის მნიშვნელობა პოზიციის ინდექსში "მნიშვნელობით".

ჯამი: (მარცხნივ, მარჯვნივ) მოცემულია მოთხოვნა, შეაჯამეთ ყველა რიცხვი, რომლებიც შემოდის დიაპაზონში.

მაგალითი  

შეყვანის

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). თითოეული სრულყოფილი კვადრატისთვის, როგორც რიცხვი, გვექნება ზუსტი კვ.მ (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

განხორციელება ჯავაში Sqrt (ან კვადრატული ფესვის) რღვევის ტექნიკისთვის  

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)) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

იხილეთ ასევე
მასივის პროდუქტი, გარდა საკუთარი თავისა

სივრცის სირთულე

O (sqrt (n)) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.