تکنیک تجزیه Sqrt (یا ریشه مربع)


سطح دشواری سخت
اغلب در کادنس هند پی پال Qualtrics Roblox Twilio
صف مشکل پرس و جو

به شما کوئری از محدوده یک عدد صحیح داده می شود صف. از شما خواسته می شود مجموع تمام اعدادی را که در دامنه پرسش داده شده قرار دارند ، تعیین کنید. پرسش ارائه شده دو نوع است ،

بروزرسانی: (شاخص ، مقدار) به عنوان یک پرسش داده می شود ، جایی که شما باید مقدار آرایه را در شاخص موقعیت با "مقدار" به روز کنید.

جمع: (چپ ، راست) یک پرس و جو داده می شود ، تمام اعدادی را که در این محدوده هستند جمع کنید.

مثال

ورودی

arr [] = {2,4,7,1,5,8,9,10,3,6،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

جمع پرس و جو (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. برای جمع بندی مقدار در محدوده داده شده ، مقدار جمع را 0 قرار دهید.
  4. سه حلقه while را دنبال کنید ، تا وقتی که چپ کمتر از مقدار راست باشد ، چپ نباید صفر باشد و چپ نباید گوشه هر بلوک باشد ، سپس مقدار آرایه [چپ] را به جمع اضافه کنید و مقدار را افزایش دهید ارزش چپ
  5. در این قسمت ، بلوک بزرگ سمت چپ باید کمتر از راست باشد ، سپس مقدار blockArray را در شاخص به عنوان تقسیم سمت چپ و بلوک اضافه کنید و مقدار بلوک بزرگ را به سمت چپ اضافه کنید.
  6. در این قسمت ، چپ کمتر از راست است ، مقدار آرایه [چپ] را به مجموع اضافه کنید و مقدار چپ را 1 افزایش دهید و مقدار جمع را برگردانید.
  7. برای هر پرسش به روزرسانی ، تقسیم بندی index و blockize را بدست آورید و مقداری را که برای به روزرسانی و تفریق آرایه [index] داده شده اضافه کنید. در آخر مقدار "مقدار" در آرایه [index] را به روز کنید.

توضیح

تجزیه ریشه مربعی روشی برای حل سوالات برای کاهش پیچیدگی از نظر ریشه مربع مربع sqrt (n) است. با توجه به یک آرایه و دامنه پرس و جو ، مقدار کل اعدادی را که در محدوده داده شده هر پرس و جو قرار دارند ، پیدا کنید و وظیفه دیگر به روزرسانی مقدار در فهرست داده شده است. بنابراین در این ما چند پرسش به ما داده شده است و ما باید آن را حل کنیم ، ما می توانیم با استفاده از رویکرد ساده لوحانه آن را حل کنیم. در این روش ما با تکرار بیش از هر عنصر در آرایه در محدوده داده شده از چپ و راست ، آن را حل خواهیم کرد و همه مقادیر موجود در محدوده را جمع خواهیم کرد ، اما در اینجا برای این رویکرد پیچیدگی زمان برای هر رویکرد O (n) خواهد بود .

بنابراین برای بهینه سازی کارآمدترین درخواستها ، از تجزیه ریشه مربع استفاده خواهیم کرد و به ما در کاهش پیچیدگی زمان کمک می کنیم. می توانیم فرض کنیم که آرایه ای از اندازه n شامل n عنصر باشد. ما آرایه را به قطعات کوچک یا بلوکهایی با اندازه sqrt (n) تقسیم خواهیم کرد. برای هر مربع کامل به عنوان یک عدد ، مربع های مربع دقیق (n) خواهیم داشت. با این تجزیه آرایه ، بلوکهای sqrt (n) و در هر بلوک خواهیم داشت. اگر n یک مربع کامل باشد ، جایی که n به اندازه یک آرایه باشد ، عناصر sqrt (n) خواهیم داشت.

فرض کنید ما یک بلوک sqrt (16) داریم از آنجا که 16 یک مربع کامل است. ما دقیقاً 4 بلوک خواهیم داشت و هر بلوک دقیقاً شامل 4 عنصر خواهد بود. هر بلوک ما جمع تمام عناصر موجود در هر بلوک را خواهیم داشت. بنابراین اگر ما می خواهیم از مجموع هرگونه پرسش محدوده مطلع شویم. ما می توانیم با استفاده از بلوک های جمع ، به راحتی جمع را پیدا کنیم

پیاده سازی در 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

پیاده سازی در جاوا برای تکنیک تجزیه 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)) جایی که "n" تعداد عناصر آرایه است.

پیچیدگی فضا

O (sqrt (n)) جایی که "n" تعداد عناصر آرایه است.