Sqrt(或平方根)分解技術  


難度級別
經常問 Cadence印度 貝寶 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)

將array [5]的值更新為8。

33 0和3範圍內的數字總和為14(1 + 5 + 8 + 9 + 10)

算法  

  1. 獲得n的平方根值作為塊大小並遍歷數組。
  2. 將輸入數組的值複製到我們創建的數組中,然後檢查是否有任何索引可被blocksize整除,然後再將blockindex的值增加1並將arr [i]的值添加到blockArray處的blockArray上。
  3. 要對給定範圍內的值求和,請將sum的值設置為0。
  4. 遵循三個while循環,直到left小於right的值,left不應為零,left不應為任何塊的拐角處,然後將array [left]的值添加到總和並增加左值。
  5. 在這種情況下,左加blocksize應該小於右,然後在索引處添加blockArray的值作為左和blocksize的除法,然後將blocksize的值添加到左側。
  6. 在這種情況下,left小於right,將array [left]的值添加到總和,並將left的值增加1,然後返回總和的值。
  7. 對於任何更新查詢,獲取索引和塊大小的除法,然後添加給定的值以更新並減去array [index]。 最後更新array [index]的“值”。
也可以看看
K個空插槽

解釋  

平方根分解是一種解決問題的技術,它可以降低sqrt(n)的平方根的複雜性。 給定一個數組和查詢範圍,以查找每個查詢的給定範圍內的所有數字的總和,另一個任務是更新給定索引處的值。 因此,在此我們提出了一些查詢,並且我們需要解決該問題,我們可以使用樸素的方法來解決它。 在這種方法中,我們將通過在給定的左右範圍內迭代數組中的每個元素並求和該範圍中存在的所有值來解決該問題,但是在此方法中,每種方法的時間複雜度將為O(n) 。

因此,為了最有效地優化查詢,我們將使用平方根分解,以幫助減少時間複雜度。 我們可以假設大小為n的數組包含n個元素。 我們將數組分成大小為sqrt(n)的小塊或塊。 對於每個完美的正方形,我們都會有精確的sqrt(n)塊。 通過對數組的這種分解,我們將在每個塊中都有sqrt(n)個塊。 如果n是一個完美的正方形,其中n是一個數組的大小,我們將擁有sqrt(n)元素。

假設我們有一個sqrt(16)塊,因為16是一個完美的正方形。 我們將有4個塊,每個塊將包含4個元素。 每個塊我們將擁有每個塊中所有元素的總和。 因此,如果我們要求找出任何範圍查詢的總和。 我們可以通過使用塊求和輕鬆地找到和。

也可以看看
數據結構設計

Sqrt(或平方根)分解技術的C ++實現  

#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(或平方根)分解技術的Java實現  

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(平方(n)) 哪裡 “ n” 是數組中元素的數量。

也可以看看
除自身以外的數組乘積

空間複雜度

O(平方(n)) 哪裡 “ n” 是數組中元素的數量。