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]的值添加到blockindex处的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]的“值”。

说明

平方根分解是一种解决问题的技术,可以降低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” 是数组中元素的数量。