Sqrt (və ya Kvadrat Kök) Ayrışma Texnikası

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Cadence Hindistan PayPal Kvalifikasiya ROBLOX Twilio
Geyim Sorğu problemiBaxılıb 73

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Sizə bir sıra ədədi sorğusu verilir array. Verilən sorğu aralığında gələn bütün rəqəmlərin cəmini təyin etməyiniz istənəcəkdir. Verilən sorğu iki növdür, bunlar -

Yeniləmə: (indeks, dəyər) bir sıra sorğu şəklində verilir, burada 'indeks' ilə dizinin dəyərini yeniləməlisiniz.

Cəmi: (sola, sağa) bir sorğu verilir, aralığa daxil olan bütün rəqəmləri yekunlaşdırın.

misal

Input

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

Cəmi sorğu (0, 3)

Cəmi sorğu (4, 9)

Yeniləmə (5, 8)

Cəmi sorğu (3, 7)

Buraxılış

14 0 və 3 aralığındakı rəqəmlərin cəmi 14 (2 + 4 + 7 + 1)

41 4 və 9 aralığındakı rəqəmlərin cəmi 41-dir (5 + 8 + 9 + 10 + 3 + 6)

[5] massivindəki dəyər 8 olaraq yenilənir.

33 0 və 3 aralığındakı rəqəmlərin cəmi 14 (1 + 5 + 8 + 9 + 10)

Alqoritm

  1. Blok ölçüsü olaraq n-in kvadrat kök dəyərini əldə edin və massivi keçin.
  2. Giriş massivinin dəyərini yaratdığımız massivə kopyalayın və indekslərdən hər hansı birinin blokdaxa görə dəyərini 1-ə artırıb blokArray-a blockindex-də arr [i] dəyərini əlavə edərsə bloklaşdırma ilə bölündüyünü yoxlayın.
  3. Verilən aralığın dəyərini cəmləmək üçün cəmin dəyərini 0 olaraq təyin edin.
  4. Döngələr halında üçü izləyin, sol sağın dəyərindən az olana qədər, sol sıfır olmamalı və sol heç bir blokun künc vəziyyəti olmamalıdır, sonra cəmi [sol] dəyərini cəminə əlavə edin və artırın solun dəyəri.
  5. Bu vəziyyətdə sola və bloklaşdırma sağdan daha az olmalıdır, sonra blockArray dəyərini indeksə sol və bloklaşdırma olaraq əlavə edin və bloklaşdırma dəyərini sola əlavə edin.
  6. Bu vəziyyətdə sol sağdan azdır, cəmin üzərinə [sol] massivinin dəyərini əlavə edin və solun qiymətini 1 artırın və cəmin dəyərini qaytarın.
  7. Hər hansı bir yeniləmə sorğusu üçün indeks bölməsini alın və bloklaşdırın və serialı [indeks] yeniləmək və çıxarmaq üçün verilən dəyəri əlavə edin. Sonda serialdakı 'dəyər' yeniləndi [index].

Izahat

Kvadrat kök parçalanması, sqrt (n) kvadrat kökü baxımından mürəkkəbliyi azaltmaq üçün sualları həll etmək üçün bir texnikadır. Hər bir sorğunun verilmiş aralığında olan bütün rəqəmlərin cəmini tapmaq üçün bir sıra və sorğu diapazonu verilmişdir və başqa bir tapşırıq verilən indeksdəki dəyəri yeniləməkdir. Buna görə bizə bəzi sorğular verilir və bunu həll etməliyik, sadəlövh yanaşmadan istifadə edərək həll edə bilərik. Bu yanaşmada onu verilmiş sol və sağ aralığındakı sıra içindəki hər bir element üzərində təkrarlayaraq həll edəcəyik və aralıqdakı bütün dəyərləri cəmləyəcəyik, lakin burada bu yanaşma üçün hər yanaşma üçün zaman mürəkkəbliyi O (n) olacaq .

Beləliklə, sorğuları ən təsirli şəkildə optimallaşdırmaq üçün, vaxtın mürəkkəbliyini azaltmağa kömək edən kvadrat kök parçalanmasından istifadə edəcəyik. N ölçülü bir sıra n elementdən ibarət olduğunu düşünə bilərik. Dizini sqrt (n) ölçülü kiçik hissələrə və ya bloklara ayıracağıq. bir sıra olaraq hər bir mükəmməl kvadrat üçün dəqiq sqrt (n) hissələrə sahibik. Dizinin bu parçalanması ilə hər blokda sqrt (n) blokları olacaq. N bir sıra ölçüsü olduğu mükəmməl bir kvadratdırsa, sqrt (n) elementlərinə sahib olacağıq.

Tutaq ki, 16 sqrt (16) blok var, çünki 4 mükəmməl bir kvadratdır. Tam 4 bloka sahib olacağıq və hər blokda tam XNUMX element olacaq. Hər blokda hər blokda yatan bütün elementlərin cəmi olacaqdır. Beləliklə, hər hansı bir sıra sorğusunun cəmini tapmaq istəsək. Cəmi bloklar istifadə edərək cəmi asanlıqla tapa bilərik.

Sqrt (və ya Kvadrat Kök) Ayrışma Texnikası üçün C ++ dilində tətbiq

#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 (və ya Kvadrat Kök) Ayrışma Texnikası üçün Java-da tətbiqetmə

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 (və ya Kvadrat Kök) Ayrışma Texnikası üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (sqrt (n)) hara "N" massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

O (sqrt (n)) hara "N" massivdəki elementlərin sayıdır.

Crack Sistemi Dizayn Müsahibələri
Translate »