Sqrt (же чарчы тамыр) ажыроо ыкмасы  


Кыйынчылык деңгээли катуу
Көп суралган Каденс Индия 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)

Algorithm  

  1. N-дин квадраттык тамыр маанисин блокировка түрүндө алып, массивди айланып өтүңүз.
  2. Киргизилген массивдин маанисин биз түзгөн массивге көчүрүп, индекстердин кайсынысы болсо да блокировкага бөлүнөрүн текшерип, эгерде ал blockindex маанисин 1ге көбөйтсө жана arrinde [i] маанисин blockArray дарагына blockindex кылып кошсо.
  3. Берилген диапазондогу маанини жыйынтыктоо үчүн, сумманын маанисин 0 деп коюңуз.
  4. Үчөөнү ээрчип, цикл солго оңго жеткенге чейин, сол нөлгө жана сол эч кандай блоктун бурчу болбошу керек, андан кийин [сол] массивинин суммасына кошуп, көбөйт солдун мааниси.
  5. Мында солго плюс блокировка оңдон кичине болушу керек, андан кийин индексте blockArray маанисин солго жана блокировкага бөлүп кошуп, солго блокировка маанисин кошуңуз.
  6. Мында сол оңдон кичине болуп, суммага [сол] массивинин маанисин кошуп, солдун маанисин 1ге көбөйтүп, сумманын маанисин кайтарыңыз.
  7. Ар кандай жаңыртуу суроосу үчүн индекстин бөлүнүшүн алып, блокировкалап, [индекс] массивин жаңыртуу жана алып салуу үчүн берилген маанини кошуңуз. Акыркы жолу [индекс] массивиндеги 'маанини' жаңыртыңыз.
ошондой эле
K бош орундар

түшүндүрүү  

Квадраттык тамырдын ажыроосу - бул sqrt (n) чарчы тамыры жагынан татаалдыгын азайтуу үчүн суроолорду чечүү ыкмасы. Ар бир суроонун берилген диапазонундагы бардык сандардын суммасын табуу үчүн массив жана суроо диапазону берилген жана дагы бир тапшырма берилген индекстеги маанини жаңыртуу. Демек, бул жерде бизге бир нече суроо берилет, жана биз аны чечишибиз керек, биз аны жөнөкөй ыкманы колдонуу менен чече алабыз. Ошол ыкма менен биз аны сол жана оң берилген массивдеги ар бир элементтин үстүнөн кайталоо жолу менен чечебиз жана диапазондогу бардык баалуулуктардын суммасын кошобуз, бирок бул жерде ар бир ыкма үчүн убакыттын татаалдыгы O (n) болот .

Ошентип, суроолорду натыйжалуу оптималдаштыруу үчүн, биз убакыттын татаалдыгын азайтууга жардам берип, чарчы тамырдын ажырашын колдонобуз. N элементтен турган көлөмдөгү n массив деп болжолдой алабыз. Массивди кичинекей бөлүктөргө же sqrt (n) өлчөмүндөгү блокторго бөлөбүз. ар бир кемчиликсиз квадрат үчүн, биз так sqrt (n) бөлүктөргө ээ болобуз. Массивдин мындай ажыроосу менен, ар бир блокто sqrt (n) блок болот. N кемчиликсиз бир квадрат болсо, анда sqrt (n) элементтери болот, мында n массивдин өлчөмү.

Бизде sqrt (16) блок бар дейли, анткени 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 (же Square Root) ажыроо ыкмасы үчүн 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)) кайда "N" массивдеги элементтердин саны.

ошондой эле
Массивдин өзүнөн башка продукту

Космостун татаалдыгы

O (sqrt (n)) кайда "N" массивдеги элементтердин саны.