ስኩርት (ወይም ካሬ ሥር) የመበስበስ ቴክኒክ


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ ካዴንስ ህንድ የ PayPal Qualtrics 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. የግብአት ድርድር ዋጋን በፈጠርነው ድርድር ላይ ገልብጠው ከዚያ የብሎዲንዴክስን እሴትን በ 1 ከፍ የሚያደርግ እና የ ”[”] እሴትን በብሎክኔክስ ላይ በማከል የማንኛውም መረጃ ጠቋሚዎች በብሎዝ የሚከፋፈሉ መሆናቸውን ያረጋግጡ።
  3. በተጠቀሰው ክልል ውስጥ እሴቱን ለማጠቃለል የድምር ዋጋን ወደ 0 ያቀናብሩ።
  4. ሦስቱን ቀለበቶች ይከተሉ ፣ ግራ ከቀኝ እሴት ያነሰ እስኪሆን ድረስ ፣ ግራው ዜሮ መሆን የለበትም እና ግራ ደግሞ የማንኛውም የማእዘን ጉዳይ መሆን የለበትም ፣ ከዚያ የመደመርን እሴት ከግራ ወደ ግራው ይጨምሩ እና ይጨምሩ የግራ እሴት
  5. በዚህ ውስጥ የግራ ፕላስ ማገጃ ከቀኝ በታች መሆን አለበት ፣ ከዚያ የግራ እና የማገጃ ክፍፍል ሆኖ በመረጃ ጠቋሚው ላይ የብሎክአርይ ዋጋን ያክሉ እና የማገጃ እሴቱን ወደ ግራ ያክሉ።
  6. በዚህ ውስጥ ግራ ከቀኝ ያነሰ ነው ፣ የድርድርን [ግራ] እሴትን በድምሩ ላይ ይጨምሩ እና የግራውን እሴት በ 1 ይጨምሩ ፣ እና የድምሩን ዋጋ ይመልሱ።
  7. ለማንኛውም የዝማኔ ጥያቄ የመረጃ ጠቋሚውን ክፍፍል ያግኙ እና አግድ ፣ እና ድርድር [ማውጫ] ን ለማዘመን እና ለመቀነስ የተሰጠውን እሴት ያክሉ። በመጨረሻ “እሴት” ን በድርድር [ማውጫ] ላይ ያዘምኑ።

ማስረጃ

የካሬ ሥር መበስበስ ከካሬ ስኩርት (n) አንፃር ውስብስብነቱን ለመቀነስ ጥያቄዎችን ለመፍታት የሚያስችል ዘዴ ነው ፡፡ በእያንዳንዱ መጠይቅ በተጠቀሰው ክልል ውስጥ የሚገኙትን የሁሉም ቁጥሮች ድምር ለማግኘት አንድ ድርድር እና መጠይቁ የተሰጠው ሲሆን ሌላ ሥራ ደግሞ በተጠቀሰው መረጃ ጠቋሚ ላይ ዋጋውን ማዘመን ነው። ስለዚህ በዚህ ውስጥ የተወሰኑ መጠይቆች ይሰጡንናል ፣ ያንን መፍታት ያስፈልገናል ፣ ቀለል ያለ አቀራረብን በመጠቀም ልንፈታው እንችላለን ፡፡ በዚያ አካሄድ በተጠቀሰው የግራ እና የቀኝ ክልል ውስጥ በእያንዳንዱ ክፍል ውስጥ በእያንዳንዱ ረድፍ ላይ በመለዋወጥ እንፈታዋለን ፣ እና በክልል ውስጥ ያሉትን እሴቶች በሙሉ ጠቅለል አድርገን እንይዛለን ፣ ግን እዚህ ለእያንዳንዱ የአቀራረብ ጊዜ ውስብስብነት O (n) .

ስለዚህ ጥያቄዎቹን በብቃት ለማመቻቸት የካሬ ሥር መበስበስን እንጠቀማለን ፣ የጊዜ ውስብስብነትን ለመቀነስ ይረዳናል ፡፡ N ንጥረ ነገሮችን ያካተተ የመጠን ድርድር እንደሆነ መገመት እንችላለን። ድርድርን ወደ ትናንሽ ቁርጥራጮች ወይም የመጠን ስኩርት (n) ብሎኮች እንከፍለዋለን ፡፡ ለእያንዳንዱ ፍጹም ካሬ እንደ አንድ ቁጥር ፣ ትክክለኛ ስኩርት (n) ቁርጥራጮች ይኖሩናል። በዚህ የድርድር መበስበስ ፣ ስኩርት (n) ብሎኮች እና በእያንዳንዱ ብሎክ ውስጥ ይኖረናል ፡፡ N ፍጹም ካሬ ከሆነ ፣ የ n ድርድር መጠን ያለው ከሆነ sqrt (n) አካላት ይኖረናል።

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

በጃቫ ውስጥ ለ ‹ስኩርት› (ወይም ካሬ ሥር) መበስበስ ቴክኒክ ተግባራዊነት

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 (n)) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።

የቦታ ውስብስብነት

ኦ (sqrt (n)) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።