Sqrt (ё решаи чоркунҷа) Усули таҷзия  


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Cadence Ҳиндустон PayPal Qualities Roblox Тиллио
тартиботи ҳарбӣ Масъалаи пурсиш

Ба шумо дархости диапазони бутун дода мешавад асал. Аз шумо хоҳиш карда мешавад, ки ҳаҷми ҳамаи рақамҳои дар доираи пурсиш додашударо муайян кунед. Дархости додашуда ду навъ аст, ки инҳоянд:

Навсозӣ: (индекс, арзиш) ҳамчун дархост дода мешавад, ки дар он шумо бояд арзиши массивро дар индекси мавқеъ бо 'арзиш' нав кунед.

Ҷамъ: (аз чап, рост) пурсиш дода мешавад, ҳамаи рақамҳои дар диапазон омадаро ҷамъбаст кунед.

мисол  

вуруди

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 at blockindex илова кунад.
  3. Барои ҷамъбаст кардани арзиши диапазони додашуда, арзиши суммаро ба 0 таъин кунед.
  4. Се ҳолати ҳалқаҳоро пайравӣ кунед, то он даме ки чап аз арзиши рост кам шавад, чап бояд сифр ва чап набояд кунҷи ягон блок набошад, пас арзиши массивро [чап] -ро ба сумма илова кунед ва ҳосили онро зиёд кунед арзиши чап.
  5. Дар ин ҳолат, блок бастани чап бояд аз рост камтар бошад, пас арзиши blockArray дар индекс ҳамчун тақсимоти чап ва блок илова кунед ва арзиши бастабандро ба чап илова кунед.
  6. Дар ин ҳол, чап аз рост камтар аст, арзиши массивро [чап] -ро ба сумма илова кунед ва арзиши чапро ба 1 зиёд кунед ва арзиши суммаро баргардонед.
  7. Барои ҳар як дархости навсозӣ, тақсимоти индексро гиред ва блокировка кунед, ва арзиши барои навсозӣ ва тарҳ кардани массив [index] додашударо илова кунед. Дар охир навсозӣ 'арзиш' дар массиви [index].
ҳамчунин нигаред
K ҷойи холӣ

Шарҳ  

Тақсимоти решаи квадратӣ ин усули ҳалли саволҳо барои кам кардани мураккабӣ дар робита бо решаи квадратии sqrt (n) мебошад. Бо назардошти массив ва диапазони дархостҳо барои ёфтани ҷамъи ҳамаи рақамҳое, ки дар доираи ҳар як пурсиш мавҷуданд ва вазифаи дигар ин нав кардани қимат дар индекси додашуда мебошад. Аз ин рӯ, дар ин бора ба мо баъзе саволҳо дода мешаванд ва мо бояд инро ҳал кунем, мо метавонем онро бо истифодаи усули соддалавҳона ҳал кунем. Дар ин равиш, мо онро бо такрори ҳар як унсури массив дар ҳудуди додашудаи чап ва рост ҳал мекунем ва ҳамаи арзишҳои дар диапазон мавҷудбударо ҷамъбаст хоҳем кард, аммо дар ин ҷо мураккабии вақт барои ҳар як равиш O (n) хоҳад буд .

Аз ин рӯ, барои самараноктар кардани саволҳо, мо таҷзияи решаи квадратиро истифода мебарем ва ба мо кӯмак мекунад, ки мураккабии вақтро кам кунем. Мо тасаввур карда метавонем, ки массиви андозаи n иборат аз n унсур аст. Мо массивро ба қисмҳои хурд ё блокҳои андозаи sqrt (n) тақсим мекунем. барои ҳар як мураббаъ комил ҳамчун адад, мо қисмҳои дақиқи sqrt (n) дорем. Бо ин таҷзияи массив, мо блокҳои sqrt (n) ва дар ҳар як блок хоҳем дошт. Мо дорои унсурҳои sqrt (n) хоҳем буд, агар n як квадрати комил бошад, дар сурате ки n андозаи массив аст.

Фарз мекунем, ки мо блокҳои sqrt (16) дорем, зеро 16 як квадрати комил аст. Мо дақиқан 4 блок хоҳем дошт ва ҳар як блок маҳз 4 элементро дар бар мегирад. Ҳар як блок мо маҷмӯи ҳамаи элементҳои дар ҳар як блок ҷойгиршударо дорем. Пас, агар мо хоҳиш кунем, ки ҷамъи ягон пурсиши диапазонро ёбем. Мо бо истифода аз блокҳои сум мо метавонем маблағро ба осонӣ пайдо кунем.

ҳамчунин нигаред
Тарроҳии сохтори маълумот

Татбиқ дар C ++ барои Sqrt (ё решаи Square) Усули чудошавӣ  

#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)  

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)) ки дар "Н" шумораи унсурҳои массив аст.