Скрт (или квадратни корен) техника разлагања


Ниво тешкоће Тежак
Често питани у Цаденце Индиа ПаиПал Куалтрицс роблок Твилио
Ред Куери Проблем

Добија се упит опсега цео број поредак. Од вас ће бити затражено да одредите збир свих бројева који долазе у опсегу датог упита. Дати упит има две врсте, а то су -

Ажурирање: (индекс, вредност) даје се као упит, где треба да ажурирате вредност низа на индексу положаја са „вредност“.

Збир: (лево, десно) добија се упит, зброји све бројеве који долазе у опсегу.

Пример

Улазни

арр [] = {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. Добијте квадратну вредност корена н као величину блока и пређите низ.
  2. Копирајте вредност улазног низа у низ који смо креирали и проверите да ли је било који од индекса дељив величином блока ако тада повећава вредност блоцкиндек-а за 1 и додаје вредност арр [и] блоцкАрраи-у на блоцкиндек-у.
  3. Да бисте сумирали вредност у датом опсегу, поставите вредност суме на 0.
  4. Пратите петље вхиле, док лева страна не буде мања од вредности десне, лева не сме бити нула, а лева не сме бити угаони случај било ког блока, а затим додајте вредност низа [лево] збиру и повећајте вредност лево.
  5. У овом случају лева плус величина блока треба да буде мања од десне, затим додајте вредност блоцкАрраи у индекс као поделу левице и величине блока и додајте вредност величине блока лево.
  6. У овом је лево мање од десног, додајте вредност низа [лево] збиру и повећајте вредност левог за 1 и вратите вредност збира.
  7. За било који упит за ажурирање, поделите индекс и величину блока и додајте вредност која је дата за ажурирање и одузимање низа [индекс]. На крају ажурирајте 'вредност' у низу [индекс].

Објашњење

Декомпозиција квадратног корена је техника за решавање питања ради смањења сложености у смислу квадратног корена скрт (н). С обзиром на низ и опсег упита за проналажење збира свих бројева који се налазе у датом опсегу сваког упита, а други задатак је ажурирање вредности у датом индексу. Дакле, у овом делу су нам дата нека питања, а то морамо решити, можемо то решити наивним приступом. У том приступу ћемо га решити итерацијом преко сваког елемента у низу унутар датог опсега лево и десно и збројити све вредности присутне у опсегу, али овде ће за овај приступ временска сложеност за сваки приступ бити О (н) .

Дакле, да бисмо најефикасније оптимизирали упите, користићемо распадање квадратног корена, помажући нам да смањимо временску сложеност. Можемо претпоставити да је низ величине н који се састоји од н елемената. Низ ћемо поделити на мале делове или блокове величине скрт (н). за сваки савршени квадрат као број, имаћемо прецизне скрт (н) комаде. Са овом декомпозицијом низа, имаћемо скрт (н) блокова и у сваком блоку. Имаћемо скрт (н) елементе ако је н савршен квадрат, где је н величина низа.

Претпоставимо да имамо скрт (16) блокова јер је 16 савршен квадрат. Имаћемо тачно 4 блока и сваки блок ће садржати тачно 4 елемента. У сваком блоку имат ћемо збир свих елемената који леже у сваком блоку. Дакле, ако тражимо да сазнамо збир било ког упита о опсегу. Збир можемо лако пронаћи помоћу блокова сум.

Имплементација у Ц ++ за технику разлагања Скрт (или квадратни корен)

#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

Примена у Јави за Скрт (или квадратни корен) технику разлагања

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

Анализа сложености технике распадања Скрт-а (или квадратног корена)

Сложеност времена

О (скрт (н)) где „Н“ је број елемената у низу.

Сложеност простора

О (скрт (н)) где „Н“ је број елемената у низу.