ఇచ్చిన సబ్‌రేలో ఇచ్చిన సంఖ్య కంటే తక్కువ లేదా సమానమైన మూలకాల సంఖ్య


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది కోడ్‌నేషన్ డిఇ షా గూగుల్ ఒపేరా పేపాల్ Pinterest
అర్రే ట్రీ

సమస్యల నివేదిక

“ఇచ్చిన సబ్‌రేలో ఇచ్చిన సంఖ్య కంటే తక్కువ లేదా సమానమైన మూలకాల సంఖ్య” అనే సమస్య మీకు పూర్ణాంక శ్రేణి మరియు q సంఖ్య ప్రశ్నలను ఇస్తుందని పేర్కొంది. రెండు రకాల ప్రశ్నలు ఉంటాయి

  • 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

వివరణ

queryPrint (0, 2, 2) సూచిక 2 నుండి 0 వరకు 2 కంటే తక్కువ లేదా సమానమైన మూలకాల సంఖ్యను ప్రింట్ చేస్తుంది, అంటే 1

queryUpdate (2, 8) విలువ 2 తో ఇండెక్స్ 8 వద్ద మూలకాన్ని నవీకరిస్తుంది, అంటే arr {2, 4, 8, 1, 5 be

queryPrint (1, 3, 5) సూచిక 5 నుండి 1 వరకు 3 కంటే తక్కువ లేదా సమానమైన మూలకాల సంఖ్యను ప్రింట్ చేస్తుంది, అంటే 2

queryUpdate (4, 3) 4 తో ​​ఇండెక్స్ 3 వద్ద మూలకాన్ని నవీకరిస్తుంది, అంటే {2, 4, 8, 1, 3 be

queryUpdate (1, 3) 1 తో ​​ఇండెక్స్ 3 వద్ద మూలకాన్ని నవీకరిస్తుంది, అంటే {2, 3, 8, 1, 3 be

queryPrint (1, 2, 4) సూచిక 4 నుండి 1 వరకు 2 కంటే తక్కువ లేదా సమానమైన మూలకాల సంఖ్యను ప్రింట్ చేస్తుంది, అంటే 1

ఇచ్చిన సబ్‌రేలో ఇచ్చిన సంఖ్య కంటే తక్కువ లేదా సమానమైన మూలకాల సంఖ్య

 

సంఖ్యలను కనుగొనడానికి అల్గోరిథం <= సబ్‌రేలో ఇచ్చిన విలువ

  1. విభజించండి అమరిక n యొక్క వర్గమూలానికి సమానమైన పరిమాణ బ్లాకుల్లోకి, ఇక్కడ n అనేది ఇన్పుట్ శ్రేణి యొక్క పరిమాణం.
  2. ఒక నిర్దిష్ట బ్లాక్‌లోని శ్రేణిలో ఉన్న గరిష్ట మూలకం కంటే ఒకటి కంటే ఎక్కువ పరిమాణంలోని బైనరీ ఇండెక్స్ చెట్టును నిర్మించండి.
  3. శ్రేణి యొక్క ప్రతి మూలకం కోసం బ్లాక్ ఎక్కడ ఉందో తెలుసుకోండి మరియు బ్లాక్ యొక్క BIT శ్రేణిని 1 వద్ద arr [i] తో నవీకరించండి.
  4. ప్రతి నవీకరణ ప్రశ్నకు. -1 తో సూచిక కోసం శ్రేణి యొక్క అసలు విలువ వద్ద బ్లాక్‌కు సంబంధించి BIT శ్రేణి యొక్క విలువను నవీకరించండి.
  5. ఒక నిర్దిష్ట సూచిక యొక్క క్రొత్త మూలకం వద్ద విలువ 1 తో అదే బ్లాక్ యొక్క BIT శ్రేణిని నవీకరించండి.
  6. ప్రతి ముద్రణ ప్రశ్నకు. మూలకాల విలువను k కంటే తక్కువ లేదా సమానంగా లెక్కించడానికి, BIT శ్రేణికి ప్రశ్న చేయండి. మరియు పూర్తి బ్లాక్ కోసం లేదా అసంపూర్ణమైన లేదా పాక్షిక బ్లాక్ కోసం, అన్ని అంశాల ద్వారా ప్రయాణించండి.

వివరణ

మాకు పూర్ణాంక శ్రేణి మరియు రెండు రకాల ప్రశ్నలు ఇవ్వబడ్డాయి. ఇచ్చిన నిర్దిష్ట సూచిక వద్ద విలువను నవీకరించడం ఒక ప్రశ్న. మరియు మరొక ప్రశ్న ఏమిటంటే k కి సమానమైన మూలకాల సంఖ్యను పొందడం. నవీకరణ ప్రశ్న కోసం, మాకు సూచిక మరియు విలువ ఇవ్వబడుతుంది. మేము విలువను నవీకరిస్తాము v ఇచ్చిన శ్రేణి సూచిక వద్ద [i]. ముద్రణ ప్రశ్న లేదా గణన ప్రశ్న కోసం, మేము k కంటే తక్కువ లేదా సమానమైన పూర్ణాంకాల సంఖ్యను ముద్రించాలి.

మేము శ్రేణిని కొన్ని బ్లాక్‌లుగా విభజించబోతున్నాం. ఈ బ్లాక్స్ శ్రేణి యొక్క పొడవు యొక్క వర్గమూలంగా ఉంటాయి. ప్రతి బ్లాక్ కోసం, మేము a ని నిర్వహిస్తాము బైనరీ ఇండెక్స్ చెట్టు. బైనరీ ఇండెక్స్ చెట్టు యొక్క పరిమాణం శ్రేణి మూలకం యొక్క ఒక నిర్దిష్ట బ్లాక్ కోసం గరిష్ట మూలకం కంటే ఒకటి. ప్రతి బ్లాక్‌కు మనకు BIT శ్రేణి ఉన్నందున, శ్రేణి యొక్క ప్రతి స్థానం వద్ద విలువ 1 తో విలువ బిట్ శ్రేణిని నవీకరించండి [i] మరియు శ్రేణి యొక్క ప్రతి మూలకం యొక్క బ్లాక్‌ను అది ఎక్కడ ఉందో తెలుసుకోండి మరియు పైన చెప్పిన విధానాన్ని అనుసరించండి ఆ బ్లాక్ యొక్క బిట్ శ్రేణిని 1 వద్ద arr [i] తో నవీకరించండి.

ప్రతి నవీకరణ ప్రశ్న కోసం, BIT శ్రేణిని నవీకరించండి. ప్రతి శ్రేణి మూలకానికి మాకు బ్లాక్ ఉన్నందున. విలువ -1 తో ఒక నిర్దిష్ట సూచిక వద్ద శ్రేణి యొక్క విలువను నవీకరించండి మరియు ఇచ్చిన సూచిక వద్ద శ్రేణి యొక్క క్రొత్త మూలకం వద్ద విలువ 1 తో అవసరమైన బ్లాక్ యొక్క BIT శ్రేణిని నవీకరించండి. మరియు ప్రింట్ యొక్క ప్రశ్న కోసం లేదా విలువలను లెక్కించడానికి, లూప్ ద్వారా ప్రయాణించండి. పూర్తి బ్లాక్ కోసం లేదా పాక్షిక పూర్తి బ్లాక్ కోసం రెండు కేసులు ఉంటాయి. చివరికి విలువను తిరిగి ఇవ్వండి.

కోడ్

సంఖ్యలను కనుగొనడానికి సి ++ కోడ్ <= సబ్‌రేలో ఇచ్చిన విలువ

#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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (1) శ్రేణిని నవీకరించడానికి మరియు పై) శ్రేణిని ముద్రించడానికి.

అంతరిక్ష సంక్లిష్టత

పై) (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య. “ఇచ్చిన సబ్‌రేలో ఇచ్చిన సంఖ్య కంటే తక్కువ లేదా సమానమైన మూలకాల సంఖ్య” సమస్య సరళ స్థలాన్ని కలిగి ఉంటుంది.