Sqrt (वा वर्गमूल) विघटन तकनीक  


कठिनाई तह हार्ड
बारम्बार सोधिन्छ ताल भारत PayPal क्वालिट्रिक्स Roblox Twilio
एरे प्रश्न समस्या

तपाईलाई पूर्णांकको क्वेरी दिइन्छ array। तपाईंलाई दिइएको क्वेरीको दायरामा आउने सबै नम्बरहरूको योगफल निर्धारित गर्न सोधिनेछ। दिइएको क्वेरी दुई प्रकारको हो, ती हुन् -

अद्यावधिक: (अनुक्रमणिका, मान) क्वेरीको रूपमा दिइन्छ, जहाँ तपाइँले 'मान' को साथ स्थिति सूचकांकमा एर्रेको मान अपडेट गर्न आवश्यक छ।

योग: (बायाँ, दायाँ) क्वेरी दिइन्छ, दायरामा आउने सबै नम्बरहरूको जोड दिन्छ।

उदाहरणका  

आगत

एर [] = {२,2,4,7,1,5,8,9,10,3,6,१०,१,१२}

योग प्रश्न (०,))

योग प्रश्न (०,))

अद्यावधिक (,,))

योग प्रश्न (०,))

उत्पादन

14 ० र range दायरा भित्रको संख्याहरूको योग १ 0 (२ + + + + + १) हो

41 and र range दायरा भित्रको संख्याहरूको योग 4१ हो (+ + + + + + १० + + +))

Ray को रूपमा एर्रे []] मा मान अपडेट गर्दै।

33 ० र range दायरा भित्रको संख्याहरूको योग १ 0 (१ + + + + + + + १०) हो

अल्गोरिदम  

  1. ब्लॉकसाइजको रूपमा n को वर्ग मूल मान प्राप्त गर्नुहोस् र एर्रे पार गर्नुहोस्।
  2. हामीले सिर्जना गरेको एर्रेमा इनपुट एरेको मान प्रतिलिपि गर्नुहोस् र जाँच गर्नुहोस् यदि कुनै सूचकांक ब्लकसाइजद्वारा विभाजित छ कि छैन यदि यसले त्यसपछि blockindex को मान १ बढाउँदछ र एररको मूल्य [i] blockindex मा blockArray मा थप गर्दछ।
  3. दिइएको दायरामा मान जोड्न, ० को योगफलको मान सेट गर्नुहोस्।
  4. लुकाउँदा तीनलाई पछ्याउनुहोस्, बायाँ दायाँको मान भन्दा कम हुँदासम्म, बाँया शून्य हुनुहुन्न र बायाँ कुनै ब्लकको कुनामा केस हुनुहुन्न, त्यसपछि एरे [बायाँ] को मान जोड्न र बढाउनुहोस् बाँयाको मान।
  5. यसमा, बाँया प्लस ब्लॉकसाइज दायाँ भन्दा कम हुनुपर्दछ, त्यसपछि सूचकांकमा blockArray को मान बायाँ र blockize को विभाजनको रूपमा थप्नुहोस्, र blockize को मान बायाँमा थप्नुहोस्।
  6. यसमा बायाँ दायाँ भन्दा कम छ, एर्रेको मान [बायाँ] योगमा थप्नुहोस् र बायाँको मान १ बढाउँनुहोस्, र योगफलको मान फिर्ता गर्नुहोस्।
  7. कुनै पनि अद्यावधिक क्वेरीका लागि, अनुक्रमणिकाको अभाग र ब्लकसाइज प्राप्त गर्नुहोस्, र एर्रे [अनुक्रमणिका] अद्यावधिक गर्न र घटाउन दिइने मान थप गर्नुहोस्। अन्तिम अद्यावधिकमा एरे [अनुक्रमणिका] मा 'मान'।
पनि हेर्नुहोस्
K खाली स्लटहरू

स्पष्टीकरण  

वर्गमूल अपघटन वर्गफुल (एन) को वर्गमूल को रूप मा जटिलता कम गर्न प्रश्नहरु लाई समाधान गर्न एक प्रविधी हो। एक एर्रे र क्वेरी दायरा दिईएको सबै संख्याहरूको योग फेला पार्न जुन प्रत्येक क्वेरीको दिइएको दायरामा छ र अर्को कार्य भनेको इन्डेक्समा मान अपडेट गर्नु हो। त्यसैले यसमा हामीलाई केहि प्रश्नहरू दिइन्छ, र हामीले त्यसलाई समाधान गर्न आवश्यक छ, हामी यसलाई भोली दृष्टिकोण प्रयोग गरेर समाधान गर्न सक्छौं। त्यस दृष्टिकोणमा हामी यसलाई बाँया र दायाँको दायरा भित्र पर्ने एर्रेमा प्रत्येक एलिमेन्टमाथि दोहोर्याएर समाधान गर्नेछौं, र दायरामा उपस्थित सबै मानहरूको जोड दिन्छौं, तर यहाँ यस दृष्टिकोणको लागि प्रत्येक दृष्टिकोणको लागि जटिलता ओ (एन) हुनेछ। ।

त्यसोभए क्वेरीहरूलाई अधिक प्रभावकारिताका लागि अनुकूलन गर्न, हामी वर्ग जरा विघटन प्रयोग गर्नेछौं, हामीलाई समय जटिलता कम गर्न मद्दत गर्दै। हामी मान्न सक्छौं कि आकार एरेमेन्ट एन एराइमेन्ट एन एरिमेन्ट्स। हामी एर्रेलाई सानो टुक्रा वा आकार sqrt (n) को ब्लकमा विभाजन गर्दछौं। संख्याको रूपमा प्रत्येक पूर्ण वर्गको लागि हामीसँग सटीक वर्गमेट (n) भागहरू हुन्छन्। एर्रेको यो विघटनको साथ हामीसँग sqrt (n) ब्लक हुन्छ र प्रत्येक खण्डमा। हामी sqrt (n) एलिमेन्टहरू राख्नेछौं यदि n सही वर्ग हो, जहाँ n एउटा array को आकार हो।

मानौं हामीसँग sqrt (१)) ब्लक छ किनकि १ a उत्तम वर्ग हो। हामीसँग ठ्याक्कै blocks ब्लक हुनेछ र प्रत्येक खण्डमा ठ्याक्कै elements तत्वहरू समावेश हुन्छन्। प्रत्येक ब्लक हामीसँग प्रत्येक ब्लकमा रहेका सबै तत्वहरूको जोड हुन्छ। त्यसोभए यदि हामी कुनै दायरा क्वेरीको योग पत्ता लगाउन सक्छौं भने। हामी सजिलैसँग ब्लकहरूको योग प्रयोग गरेर योगफल फेला पार्न सक्छौं।

पनि हेर्नुहोस्
डाटा संरचना डिजाइनिंग

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 (वा वर्गमूल) विघटन तकनीकको लागि कार्यान्वयन  

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" एर्रेमा एलिमेन्ट्सको संख्या हो।