Тэхніка раскладання Sqrt (або квадратнага кораня)


Узровень складанасці Жорсткі
Часта пытаюцца ў Cadence Індыя PayPal 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)

Абнаўленне значэння ў масіве [5] як 8.

33 сума лікаў у дыяпазоне 0 і 3 складае 14 (1 + 5 + 8 + 9 + 10)

Алгарытм

  1. Атрымайце квадратнае каранёвае значэнне n у выглядзе блока і перабярыце масіў.
  2. Скапіруйце значэнне масіва ўводу ў створаны намі масіў і праверце, ці дзеліцца які-небудзь з індэксаў на памер блока, калі потым павялічвае значэнне blockindex на 1 і дадае значэнне arr [i] да blockArray у blockindex.
  3. Каб падвесці значэнне ў дадзеным дыяпазоне, усталюйце значэнне sum ў 0.
  4. Выконвайце тры цыклы while, пакуль левы не будзе меншым за значэнне правага, левы не павінен быць роўны нулю, а левы не павінен быць вуглом любога блока, затым дадайце значэнне масіва [злева] да сумы і павялічвайце значэнне злева.
  5. Пры гэтым левы плюс вялікі блок павінен быць меншым за правы, затым дадайце значэнне blockArray па індэксе як падзел левага і вялікага памераў і дадайце значэнне памеру блока злева.
  6. Пры гэтым злева менш, чым справа, дадайце значэнне масіва [злева] да сумы і павялічце значэнне злева на 1 і вярніце значэнне сумы.
  7. Для любога запыту абнаўлення атрымайце дзяленне індэкса і памеру блока і дадайце значэнне, якое было дадзена для абнаўлення і аднімання масіва [індэкс]. Нарэшце абнавіце "значэнне" ў масіве [індэкс].

Тлумачэнне

Разлажэнне квадратнага кораня - метад вырашэння пытанняў для памяншэння складанасці з пункту гледжання квадратнага кораня sqrt (n). Улічваючы масіў і дыяпазон запыту, каб знайсці суму ўсіх лікаў, якія знаходзяцца ў дадзеным дыяпазоне кожнага запыту, а іншая задача - абнавіць значэнне па дадзеным індэксе. Такім чынам, у гэтым пытанні мы атрымліваем некаторыя запыты, і мы павінны вырашыць гэта, мы можам вырашыць гэта, выкарыстоўваючы наіўны падыход. У гэтым падыходзе мы развяжам яго шляхам ітэрацыі па кожным элеменце масіва ў зададзеным дыяпазоне злева і направа і падвядзем усе значэнні, прысутныя ў дыяпазоне, але тут для гэтага падыходу складанасць часу для кожнага падыходу будзе O (n) .

Такім чынам, каб найбольш эфектыўна аптымізаваць запыты, мы будзем выкарыстоўваць раскладванне квадратных каранёў, што дапаможа нам паменшыць час. Можна меркаваць, што масіў памерам n, які складаецца з n элементаў. Мы падзелім масіў на невялікія кавалкі альбо блокі памерам sqrt (n). для кожнага ідэальнага квадрата як колькасці мы будзем мець дакладныя кавалкі sqrt (n). Пры гэтым раскладанні масіва мы будзем мець sqrt (n) блокаў і ў кожным блоку. Мы будзем мець элементы sqrt (n), калі n - ідэальны квадрат, дзе n - памер масіва.

Дапусцім, у нас ёсць блокі sqrt (16), бо 16 - ідэальны квадрат. У нас будзе роўна 4 блокі, і кожны блок будзе змяшчаць роўна 4 элементы. Кожны блок будзе мець суму ўсіх элементаў, якія ляжаць у кожным блоку. Такім чынам, калі мы просім даведацца суму любога запыту дыяпазону. Мы можам лёгка знайсці суму, выкарыстоўваючы блокі sum.

Рэалізацыя ў C ++ для тэхнікі раскладання Sqrt (або квадратнага кораня)

#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

Рэалізацыя ў Java для тэхнікі раскладання Sqrt (або квадратнага кораня)

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)) дзе "П" - колькасць элементаў у масіве.

Касмічная складанасць

O (sqrt (n)) дзе "П" - колькасць элементаў у масіве.