किसी दिए गए सबर्रे में दिए गए संख्या से कम या उसके बराबर तत्वों की संख्या


कठिनाई स्तर कठिन
में अक्सर पूछा कोडेशन डीई शॉ गूगल संचालित पेपैल Pinterest
ऐरे पेड़

समस्या का विवरण

समस्या "किसी दिए गए सबर्रे में दी गई संख्या से कम या उसके बराबर के तत्वों की संख्या" बताती है कि आपको एक पूर्णांक सरणी और क्यू संख्या प्रश्न दिए गए हैं। प्रश्न दो प्रकार के होंगे

  • queryUpdate (i, v): दो पूर्णांक i और v होंगे, जैसे कि सरणी [i] = v को अद्यतन करते हैं।
  • queryPrint (बाएं, दाएं, k): किसी सीमा के भीतर पूर्णांकों की संख्या प्रिंट करें जो k के बराबर कम हैं।

उदाहरण

arr[]={2, 4, 6, 1, 5)
queryPrint(0, 2, 2)
queryUpdate(2, 8)
queryPrint(1, 3, 5)
queryUpdate(4, 3)
queryUpdate(1, 3)
queryPrint(1, 2, 4)
1 2 1

व्याख्या

क्वेरीप्रिंट (0, 2, 2) इंडेक्स 2 से 0 अर्थात 2 से कम या 1 के बराबर तत्वों की संख्या को प्रिंट करेगा अर्थात XNUMX

queryUpdate (2, 8) इंडेक्स 2 में तत्व को वैल्यू 8 के साथ अपडेट करेगा, गिरफ्तारी {2, 4, 8, 1, 5} होगी

क्वेरीप्रिंट (1, 3, 5) इंडेक्स 5 से 1 अर्थात 3 से कम या 2 के बराबर तत्वों की संख्या को प्रिंट करेगा अर्थात XNUMX

queryUpdate (4, 3) सूचकांक 4 में तत्व को 3 के साथ अद्यतन करेगा, गिरफ्तारी {2, 4, 8, 1, 3} होगी

queryUpdate (1, 3) सूचकांक 1 में तत्व को 3 के साथ अद्यतन करेगा, गिरफ्तारी {2, 3, 8, 1, 3} होगी

क्वेरीप्रिंट (1, 2, 4) इंडेक्स 4 से 1 अर्थात 2 से कम या 1 के बराबर तत्वों की संख्या को प्रिंट करेगा अर्थात XNUMX

किसी दिए गए सबर्रे में दिए गए संख्या से कम या उसके बराबर तत्वों की संख्या

 

सबर्रे में संख्या <= दिए गए मान को खोजने के लिए एल्गोरिथम

  1. विभाजित करें सरणी n के वर्गमूल के बराबर आकार के ब्लॉक में, जहां n इनपुट सरणी का आकार है।
  2. किसी विशेष ब्लॉक में सरणी में मौजूद अधिकतम तत्व से एक से अधिक आकार के एक बाइनरी इंडेक्स ट्री का निर्माण करें।
  3. सरणी के प्रत्येक तत्व के लिए ब्लॉक का पता लगाएं कि वह कहाँ से है और 1 के साथ ब्लॉक के BIT सरणी को अद्यतन करें [i]।
  4. प्रत्येक अद्यतन क्वेरी के लिए। -1 के साथ सूचकांक के लिए सरणी के मूल मूल्य पर ब्लॉक के सापेक्ष बीआईटी सरणी के मूल्य को अपडेट करें।
  5. किसी विशेष इंडेक्स के नए तत्व पर उसी ब्लॉक के बीआईटी एरे को मान 1 के साथ अपडेट करें।
  6. प्रत्येक प्रिंट क्वेरी के लिए। बीआईटी ऐरे से एक क्वेरी करें, तत्वों के मान को के या उससे कम करने के लिए। और पूर्ण ब्लॉक के लिए या अपूर्ण या आंशिक ब्लॉक के लिए, सभी तत्वों के माध्यम से पार।

व्याख्या

हमें एक पूर्णांक सरणी और दो प्रकार के प्रश्न दिए गए हैं। एक क्वेरी किसी दिए गए विशेष सूचकांक पर मूल्य को अद्यतन करना है। और एक और प्रश्न के बराबर की तुलना में कम तत्वों की गिनती प्राप्त करना है। अपडेट क्वेरी के लिए, हमें एक इंडेक्स और एक मान दिया जाएगा। हम मान को अपडेट करेंगे v सरणी के दिए गए सूचकांक में [i]। प्रिंट क्वेरी या काउंट क्वेरी के लिए, हमें पूर्णांकों की संख्या को प्रिंट करने की आवश्यकता है, जो कि k से कम या उसके बराबर हैं।

हम सरणी को कुछ ब्लॉकों में विभाजित करने जा रहे हैं। ये ब्लॉक सरणी की लंबाई के वर्गमूल के आकार के होंगे। हर ब्लॉक के लिए, हम एक बनाए रखेंगे बाइनरी इंडेक्स ट्री। बाइनरी इंडेक्स ट्री का आकार सरणी तत्व के किसी विशेष ब्लॉक के लिए अधिकतम तत्व से एक अधिक होगा। चूँकि हमारे पास प्रत्येक ब्लॉक के लिए BIT सरणी है, सरणी के प्रत्येक स्थान पर मान 1 के साथ मान बिट सरणी को अद्यतन करें [i] और सरणी के प्रत्येक तत्व के लिए ब्लॉक का पता लगाएं, जहाँ यह संबंधित है और उपरोक्त प्रक्रिया का पालन करें गिरफ्तारी [i] पर 1 के साथ उस ब्लॉक की बिट सरणी को अपडेट करें।

प्रत्येक अद्यतन क्वेरी के लिए, BIT सरणी को अपडेट करें। चूंकि हमारे पास प्रत्येक सरणी तत्व के लिए एक ब्लॉक है। किसी विशेष इंडेक्स पर ऐरे के मान को वैल्यू -1 के साथ अपडेट करें और दिए गए इंडेक्स पर एरे के नए तत्व में वैल्यू 1 के साथ आवश्यक ब्लॉक के बीआईटी एरे को अपडेट करें। और प्रिंट की क्वेरी के लिए या मानों की गणना करें, बस लूप के माध्यम से पार करें। दो मामले होंगे जो पूर्ण ब्लॉक के लिए हैं या आंशिक पूर्ण ब्लॉक के लिए हैं। अंतिम मूल्य पर वापस।

कोड

सी ++ कोड संख्याओं को खोजने के लिए <= सबअरे में दिया गया मान

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>

using namespace std;

const int MAX = 10001;

void update(int index, int block, int val, int bit[][MAX])
{
    for (; index < MAX ; index += (index&-index))
        bit[block][index] += val;
}
int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][MAX])
{
    int sum = 0;
    while (left<right && left%blockSize!=0 && left!=0)
    {
        if (arr[left] <= k)
            sum++;
        left++;
    }

    while (left + blockSize <= right)
    {
        int index = k;
        for (; index > 0 ; index -= index&-index)
            sum += bit[left/blockSize][index];
        left += blockSize;
    }

    while (left <= right)
    {
        if (arr[left] <= k)
            sum++;
        left++;
    }
    return sum;
}
void preprocess(int arr[], int blockSize, int n, int bit[][MAX])
{
    for (int i=0; i<n; i++)
        update(arr[i], i/blockSize, 1, bit);
}

void queryUpdate(int i, int v, int blockSize,int arr[], int bit[][MAX])
{
    update(arr[i], i/blockSize, -1, bit);
    update(v, i/blockSize, 1, bit);
    arr[i] = v;
}
int main()
{
    int arr[] = {2,4,6,1,5};
    int n = sizeof(arr)/sizeof(arr[0]);

    int blockSize = sqrt(n);

    int bit[blockSize+1][MAX];

    memset(bit, 0, sizeof(bit));

    preprocess(arr, blockSize, n, bit);

    cout << queryPrint (0, 2, 2, arr, blockSize, bit) << endl;

    queryUpdate(2, 8, blockSize, arr, bit);

    cout << queryPrint(1, 3, 5, arr, blockSize, bit) << endl;

    queryUpdate(4, 3, blockSize, arr, bit);

    queryUpdate(1, 3, blockSize, arr, bit);

    cout << queryPrint (1, 2, 4, arr, blockSize, bit) << endl;
    return 0;
}
1
2
1

संख्या खोजने के लिए जावा कोड <= सबअरे में दिया गया मान

class NumberElements
{
    static final int MAX = 10001;

    static void update(int index, int block, int val, int bit[][])
    {
        for ( ; index < MAX ; index += (index&-index))
            bit[block][index] += val;
    }
    static int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][])
    {
        int sum = 0;
        while (left < right && left % blockSize != 0 && left != 0)
        {
            if (arr[left] <= k)
                sum++;
            left++;
        }
        while (left + blockSize <= right)
        {
            int index = k;
            for (; index > 0 ; index -= index&-index)
                sum += bit[left/blockSize][index];
            left += blockSize;
        }
        while (left <= right)
        {
            if (arr[left] <= k)
                sum++;
            left++;
        }
        return sum;
    }
    static void buildArray(int arr[], int blockSize, int n, int bit[][])
    {
        for (int i=0; i<n; i++)
            update(arr[i], i/blockSize, 1, bit);
    }

    static void queryUpdate(int i, int v, int blockSize, int arr[], int bit[][])
    {
        update(arr[i], i/blockSize, -1, bit);
        update(v, i/blockSize, 1, bit);
        arr[i] = v;
    }

    public static void main(String args[])
    {
        int arr[] = {2,4,6,1,5};

        int blockSize = (int) Math.sqrt(arr.length);

        int bit[][] = new int[blockSize+1][MAX];
        buildArray(arr, blockSize, arr.length, bit);

        System.out.println(queryPrint(0, 2, 2, arr, blockSize, bit));

        queryUpdate(2, 8, blockSize, arr, bit);

        System.out.println(queryPrint(1, 3, 5, arr, blockSize, bit));

        queryUpdate(4, 3, blockSize, arr, bit);

        queryUpdate(1, 3, blockSize, arr, bit);

        System.out.println(queryPrint (1, 2, 4, arr, blockSize, bit));

    }
}
1
2
1

जटिलता विश्लेषण

समय जटिलता

ओ (1) सरणी और अद्यतन करने के लिए पर) सरणी मुद्रण के लिए।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। समस्या "किसी दिए गए सबर्रे में दिए गए नंबर से कम या बराबर तत्वों की संख्या" में रैखिक स्थान है।