Sqrt (կամ քառակուսի արմատ) քայքայման տեխնիկա


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Կադենս Հնդկաստան PayPal Քվեարկողներ 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)

Arանգում [5] արժեքը թարմացվում է որպես 8:

33 0 և 3 միջակայքերի թվերի գումարը 14 է (1 + 5 + 8 + 9 + 10)

Ալգորիթմ

  1. Ստացե՛ք n- ի քառակուսի արմատի արժեքը որպես բլոկավորված և անցեք զանգվածը:
  2. Ներածման զանգվածի արժեքը պատճենեք մեր ստեղծած զանգվածին և ստուգեք, թե արդյոք ցուցանիշներից որևէ մեկը բաժանվում է ըստ բլոկի, եթե այն այնուհետև մեծացնում է blockindex- ի արժեքը 1-ով և ավելացնում arr [i] արժեքը blockArray- ին blockindex- ում:
  3. Տրված տիրույթում արժեքն ամփոփելու համար գումարի արժեքը սահմանեք 0:
  4. Հետևեք երեք տևողությամբ օղակներին, մինչև ձախը աջից փոքր լինի, ձախը չպետք է զրո լինի, իսկ ձախը չպետք է լինի որևէ բլոկի անկյունային պատյան, այնուհետև գումարի վրա ավելացրեք զանգվածի [ձախ] արժեքը և ավելացրեք ձախի արժեքը:
  5. Դրանում ձախ գումարած բլոկիզացումը պետք է աջից պակաս լինի, ապա ինդեքսում ավելացնել blockArray- ի արժեքը որպես ձախի և բլոկի բաժանում, իսկ բլոկի մեծացման արժեքը ավելացնել ձախ:
  6. Դրանում ձախը աջից պակաս է, զանգվածի [ձախ] զանգվածին ավելացրու գումարին և ձախի արժեքը ավելացրու 1-ով, իսկ գումարի արժեքը վերադարձիր:
  7. Updateանկացած թարմացման հարցման համար ստացեք ինդեքսի բաժանում և բլոկավորում և ավելացրեք այն արժեքը, որը տրվել է զանգվածը [ինդեքս] թարմացնելու և հանելու համար: Վերջապես թարմացրեք զանգվածի [ցուցիչը] «արժեքը»:

բացատրություն

Քառակուսի արմատների քայքայումը sqrt (n) քառակուսի արմատի առումով բարդությունը նվազեցնելու համար հարցեր լուծելու մեթոդ է: Հաշվի առնելով զանգվածը և հարցման տիրույթը `յուրաքանչյուր հարցման տրված տիրույթում գտնվող բոլոր թվերի գումարը գտնելու համար, և մեկ այլ խնդիր` արժեքը թարմացնել տվյալ ցուցիչում: Այսպիսով, դրանում մեզ տրված են որոշ հարցումներ, և մենք պետք է լուծենք դա, մենք կարող ենք լուծել այն ՝ օգտագործելով միամիտ մոտեցում: Այդ մոտեցման մեջ մենք այն կլուծենք `կրկնելով զանգվածի յուրաքանչյուր էլեմենտի տրված ձախ և աջ տիրույթում և գումարելով տիրույթում առկա բոլոր արժեքները, բայց այստեղ այս մոտեցման համար յուրաքանչյուր մոտեցման ժամանակի բարդությունը կլինի O (n) ,

Այսպիսով, հարցումներն առավել արդյունավետ օպտիմալացնելու համար մենք կօգտագործենք քառակուսի արմատների քայքայում ՝ օգնելով մեզ նվազեցնել ժամանակի բարդությունը: Կարող ենք ենթադրել, որ n չափի զանգված է բաղկացած n տարրերից: Մենք զանգվածը բաժանելու ենք sqrt (n) փոքր կտորների կամ բլոկների: յուրաքանչյուր կատարյալ քառակուսիի համար որպես թիվ, մենք կունենանք ճշգրիտ sqrt (n) կտորներ: Rayանգվածի այս քայքայման դեպքում մենք կունենանք sqrt (n) բլոկ և յուրաքանչյուր բլոկում: Մենք կունենանք sqrt (n) տարրեր, եթե n- ը կատարյալ քառակուսի է, որտեղ n- ը զանգվածի չափ է:

Ենթադրենք, որ մենք ունենք sqrt (16) բլոկ, քանի որ 16-ը կատարյալ քառակուսի է: Մենք կունենանք ուղիղ 4 բլոկ, և յուրաքանչյուր բլոկ կպարունակի ուղիղ 4 տարր: Յուրաքանչյուր բլոկ կունենանք յուրաքանչյուր բլոկում ընկած բոլոր տարրերի հանրագումարը: Այսպիսով, եթե մենք խնդրենք պարզել տիրույթի ցանկացած հարցման հանրագումարը: Մենք կարող ենք հեշտությամբ գտնել գումարը `օգտագործելով բլոկների գումար:

Իրականացում C ++ - ով Sqrt (կամ Square Root) տարրալուծման տեխնիկայի համար

#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 (կամ Square Root) քայքայման տեխնիկայի համար

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 (կամ քառակուսի արմատ) քայքայման տեխնիկայի բարդության վերլուծություն

Timeամանակի բարդություն

O (sqrt (n)) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Տիեզերական բարդություն

O (sqrt (n)) որտեղ «Ն» զանգվածում տարրերի քանակն է: