Sqrt(または平方根)分解手法


難易度 ハード
よく聞かれる ケイデンスインド PayPal Qualtrics ROBLOX Twilio
配列 クエリの問題

範囲整数のクエリが与えられます 配列。 指定されたクエリの範囲内にあるすべての数値の合計を決定するように求められます。 指定されたクエリには、次のXNUMXつのタイプがあります–

更新:(インデックス、値)はクエリとして指定されます。ここで、位置インデックスの配列の値を「値」で更新する必要があります。

合計:(左、右)にクエリが与えられ、範囲内にあるすべての数値を合計します。

入力

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

合計クエリ(0、3)

合計クエリ(4、9)

Update(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. 入力配列の値を作成した配列にコピーし、インデックスのいずれかがブロックサイズで割り切れるかどうかを確認します。ブロックインデックスの値が1増加し、arr [i]の値がblockindexのblockArrayに追加されます。
  3. 指定された範囲の値を合計するには、sumの値を0に設定します。
  4. XNUMXつのwhileループをたどり、左が右の値より小さくなるまで、左がゼロであってはならず、左がブロックのコーナーケースであってはなりません。次に、array [left]の値を合計に追加し、左の値。
  5. この場合、左とブロックサイズの合計は右より小さくする必要があります。次に、インデックスのblockArrayの値を左とブロックサイズの分割として追加し、ブロックサイズの値を左に追加します。
  6. この場合、左は右よりも小さく、array [left]の値を合計に加算し、leftの値を1増やして、合計の値を返します。
  7. 更新クエリの場合は、インデックスとブロックサイズの除算を取得し、更新に指定された値を加算して、array [index]を減算します。 最後に、array [index]の「value」を更新します。

説明

平方根分解は、sqrt(n)の平方根に関する複雑さを軽減するための質問を解決する手法です。 配列とクエリ範囲を指定して、各クエリの指定された範囲内にあるすべての数値の合計を見つけます。別のタスクは、指定されたインデックスの値を更新することです。 したがって、これにはいくつかのクエリが与えられ、それを解決する必要があります。ナイーブなアプローチを使用して解決できます。 そのアプローチでは、指定された左右の範囲内で配列内の各要素を反復処理し、範囲内に存在するすべての値を合計することで解決しますが、このアプローチでは、各アプローチの時間計算量はO(n)になります。 。

したがって、クエリを最も効率的に最適化するために、平方根分解を使用して、時間の複雑さを軽減します。 n個の要素からなるサイズnの配列を想定できます。 配列をサイズsqrt(n)の小さなチャンクまたはブロックに分割します。 数としてのすべての完全な正方形に対して、正確なsqrt(n)チャンクがあります。 この配列の分解により、sqrt(n)ブロックと各ブロックが作成されます。 nが完全な正方形の場合、sqrt(n)要素があります。nは配列のサイズです。

16は完全な正方形であるため、sqrt(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(sqrt(n)) where 「n」 配列の要素数です。

スペースの複雑さ

O(sqrt(n)) where 「n」 配列の要素数です。