चौरस (किंवा स्क्वेअर रूट) विघटन तंत्र


अडचण पातळी हार्ड
वारंवार विचारले कॅडन्स इंडिया पोपल गुण Roblox Twilio
अरे क्वेरी समस्या

आपल्याला पूर्णांक श्रेणीची क्वेरी दिली जाते अॅरे. आपणास दिलेल्या क्वेरीच्या श्रेणीत येणार्‍या सर्व क्रमांकाची बेरीज निश्चित करण्यास सांगितले जाईल. दिलेली क्वेरी दोन प्रकारची आहे, ती अशी-

अद्यतनः (अनुक्रमणिका, मूल्य) क्वेरी म्हणून दिले जाते, जिथे तुम्हाला 'व्हॅल्यू' च्या सहाय्याने अ‍ॅरेची व्हॅल्यू पोजीशन इंडेक्समध्ये अपडेट करणे आवश्यक असते.

बेरीज: (डावीकडे, उजवीकडे) एक क्वेरी दिली जाते, श्रेणीत येणार्‍या सर्व क्रमांकाची बेरीज करा.

उदाहरण

इनपुट

अरे [] = {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 ने वाढवते आणि ब्लॉकइंडेक्सवरील ब्लॉकअरेमध्ये एर [i] चे मूल्य जोडते.
  3. दिलेल्या श्रेणीतील मूल्याची बेरीज करण्यासाठी 0 ची बेरीज मूल्य सेट करा.
  4. लूपच्या तीन बाजूचे अनुसरण करा, जोपर्यंत डावी उजवीच्या मूल्यापेक्षा कमी नाही तोपर्यंत डावे शून्य नसावा आणि डाव्या कोनाचा केस नसावा, नंतर अ‍ॅरेचे मूल्य [डावीकडे] बेरीजमध्ये जोडा आणि वाढवा डावीकडे मूल्य.
  5. यामध्ये डावे प्लस ब्लॉकसाईज उजवीपेक्षा कमी असले पाहिजे, त्यानंतर डाव्या व ब्लॉकसाईजचे विभाजन म्हणून निर्देशांकात ब्लॉकअरेचे मूल्य जोडा आणि डाव्या बाजूला ब्लॉकसाइझचे मूल्य जोडा.
  6. यामध्ये डावीकडून उजवीपेक्षा कमी आहे, अ‍ॅरे [डावीकडे] चे मूल्य बेरीजमध्ये जोडा आणि डाव्या चे मूल्य 1 ने वाढवा आणि बेरीजचे मूल्य परत करा.
  7. कोणत्याही अद्ययावत क्वेरीसाठी, निर्देशांक आणि ब्लॉकसाईजचे विभाजन मिळवा आणि अ‍ॅरे [अनुक्रमणिका] अद्यतनित आणि वजा करण्यासाठी देण्यात आलेली मूल्य जोडा. शेवटी अ‍ॅरे [अनुक्रमणिका] वर 'मूल्य' अद्यतनित करा.

स्पष्टीकरण

चौरस (एन) च्या वर्गमूलच्या बाबतीत जटिलता कमी करण्यासाठी प्रश्नांचे निराकरण करण्याचे स्क्वेअर रूट अपघटन हे एक तंत्र आहे. प्रत्येक क्वेरीच्या दिलेल्या श्रेणीत असलेल्या सर्व क्रमांकाची बेरीज शोधण्यासाठी अ‍ॅरे आणि क्वेरी श्रेणी दिली आहे आणि दुसरे कार्य दिलेल्या निर्देशांकावरील मूल्य अद्यतनित करणे आहे. यामध्ये आम्हाला काही प्रश्न दिले आहेत आणि निराकरण करण्याची गरज आहे, आपण निराळे दृष्टिकोन वापरुन सोडवू शकतो. त्या दृष्टीकोनातून आम्ही डाव्या आणि उजव्या दिलेल्या श्रेणीत असलेल्या अ‍ॅरेमधील प्रत्येक घटकाबद्दल पुनरावृत्ती करून त्याचे निराकरण करू आणि श्रेणीतील सर्व मूल्यांची बेरीज करू, परंतु येथे या दृष्टिकोनासाठी प्रत्येक जटिलतेसाठी वेळ (ओ) असेल. .

म्हणून क्वेरी अधिक कार्यक्षमतेने ऑप्टिमाइझ करण्यासाठी, आम्ही वेळ गुंतागुंत कमी करण्यात मदत करून स्क्वेअर रूट अपघटन करू. आपण असे समजू शकतो की आकारात घटकांची एन ए घटक असतात. आपण अ‍ॅरेला लहान भागांमध्ये किंवा आकारातील स्क्वेअर (एन) च्या ब्लॉक्समध्ये विभागू. प्रत्येक परिपूर्ण वर्गासाठी संख्या म्हणून आपल्याकडे अचूक स्क्वेअर (एन) भाग असेल. अ‍ॅरेच्या या विघटनानंतर आपल्याकडे स्क्वेअर (एन) ब्लॉक आणि प्रत्येक ब्लॉकमध्ये असतील. जर एन परिपूर्ण वर्ग असेल तर एन (एस) चे घटक असतील तर एन (एस) घटक असतील.

समजा आपल्याकडे स्क्वेअर (16) ब्लॉक आहेत कारण 16 हा परिपूर्ण वर्ग आहे. आपल्याकडे नक्की 4 ब्लॉक्स असतील आणि प्रत्येक ब्लॉकमध्ये नक्की 4 घटक असतील. प्रत्येक ब्लॉकमध्ये आपल्यामध्ये प्रत्येक ब्लॉकमध्ये असलेल्या सर्व घटकांची बेरीज असेल. तर आम्ही कोणत्याही श्रेणी क्वेरीची बेरीज शोधण्यास सांगितले तर. ब्लॉक्सची बेरीज करून आपण सहज बेरीज शोधू शकतो.

स्क्वेअर (किंवा स्क्वेअर रूट) अपघटन तंत्रकरिता सी ++ मध्ये अंमलबजावणी

#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

स्क्वेअर (किंवा स्क्वेअर रूट) अपघटन तंत्रकरिता जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (चौरस (एन)) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

स्पेस कॉम्प्लेक्सिटी

ओ (चौरस (एन)) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.