கொடுக்கப்பட்ட துணை வரிசையில் கொடுக்கப்பட்ட எண்ணைக் காட்டிலும் குறைவாகவோ அல்லது சமமாகவோ உள்ள உறுப்புகளின் எண்ணிக்கை


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது கோட்நேஷன் டி.இ ஷா கூகிள் வேலை பேபால் இடுகைகள்
அணி மரம்

சிக்கல் அறிக்கை

“கொடுக்கப்பட்ட சப்ரேயில் கொடுக்கப்பட்ட எண்ணை விடக் குறைவாகவோ அல்லது சமமாகவோ உள்ள உறுப்புகளின் எண்ணிக்கை” என்ற சிக்கல் உங்களுக்கு ஒரு முழு வரிசை மற்றும் வினவல்களின் 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

வினவல் புதுப்பிப்பு (2, 8) மதிப்பு 2 உடன் குறியீட்டு 8 இல் உறுப்பை புதுப்பிக்கும், அதாவது arr {2, 4, 8, 1, 5 be

queryPrint (1, 3, 5) குறியீட்டு 5 முதல் 1 வரை 3 ஐ விடக் குறைவான அல்லது சமமான உறுப்புகளின் எண்ணிக்கையை அச்சிடும், அதாவது 2

வினவல் புதுப்பிப்பு (4, 3) குறியீட்டு 4 இல் 3 உடன் உறுப்பை புதுப்பிக்கும், அதாவது ar {2, 4, 8, 1, 3 be

வினவல் புதுப்பிப்பு (1, 3) குறியீட்டு 1 இல் 3 உடன் உறுப்பை புதுப்பிக்கும், அதாவது ar {2, 3, 8, 1, 3 be

queryPrint (1, 2, 4) குறியீட்டு 4 முதல் 1 வரை 2 ஐ விடக் குறைவான அல்லது சமமான உறுப்புகளின் எண்ணிக்கையை அச்சிடும், அதாவது 1

கொடுக்கப்பட்ட துணை வரிசையில் கொடுக்கப்பட்ட எண்ணைக் காட்டிலும் குறைவாகவோ அல்லது சமமாகவோ உள்ள உறுப்புகளின் எண்ணிக்கை

 

எண்களைக் கண்டுபிடிப்பதற்கான வழிமுறை <= சப்ரேயில் கொடுக்கப்பட்ட மதிப்பு

  1. பிரிக்கவும் வரிசை n இன் சதுர மூலத்திற்கு சமமான அளவு தொகுதிகளாக, இங்கு n என்பது உள்ளீட்டு வரிசையின் அளவு.
  2. ஒரு குறிப்பிட்ட தொகுதியில் வரிசையில் இருக்கும் அதிகபட்ச உறுப்பை விட ஒரு பைனரி குறியீட்டு மரத்தை உருவாக்குங்கள்.
  3. வரிசையின் ஒவ்வொரு உறுப்புக்கும் அது எங்குள்ளது என்பதைக் கண்டுபிடித்து, தொகுதியின் BIT வரிசையை 1 at arr [i] உடன் புதுப்பிக்கவும்.
  4. ஒவ்வொரு புதுப்பிப்பு வினவலுக்கும். -1 உடன் குறியீட்டுக்கான வரிசையின் அசல் மதிப்பில் உள்ள தொகுதிடன் தொடர்புடைய BIT வரிசையின் மதிப்பைப் புதுப்பிக்கவும்.
  5. ஒரு குறிப்பிட்ட குறியீட்டின் புதிய உறுப்பில் மதிப்பு 1 உடன் அதே தொகுதியின் BIT வரிசையை புதுப்பிக்கவும்.
  6. ஒவ்வொரு அச்சு வினவலுக்கும். உறுப்புகளின் மதிப்பு k ஐ விட குறைவாகவோ அல்லது சமமாகவோ எண்ண, BIT வரிசைக்கு வினவல் செய்யுங்கள். முழுமையான தொகுதிக்கு அல்லது முழுமையற்ற அல்லது பகுதி தொகுதிக்கு, அனைத்து கூறுகளையும் கடந்து செல்லுங்கள்.

விளக்கம்

எங்களுக்கு ஒரு முழு வரிசை மற்றும் இரண்டு வகையான வினவல்கள் வழங்கப்படுகின்றன. கொடுக்கப்பட்ட குறிப்பிட்ட குறியீட்டில் மதிப்பைப் புதுப்பிப்பது ஒரு கேள்வி. மற்றொரு வினவல், k க்கு சமமான உறுப்புகளின் எண்ணிக்கையைப் பெறுவது. புதுப்பிப்பு வினவலுக்கு, எங்களுக்கு ஒரு குறியீடும் மதிப்பும் வழங்கப்படும். மதிப்பைப் புதுப்பிப்போம் v கொடுக்கப்பட்ட வரிசையின் குறியீட்டில் [i]. அச்சு வினவல் அல்லது எண்ணிக்கை வினவலுக்கு, k ஐ விடக் குறைவான அல்லது சமமான முழு எண்களின் எண்ணிக்கையை அச்சிட வேண்டும்.

வரிசையை சில தொகுதிகளாகப் பிரிக்கப் போகிறோம். இந்த தொகுதிகள் வரிசையின் நீளத்தின் சதுர மூலமாக இருக்கும். ஒவ்வொரு தொகுதிக்கும், நாங்கள் ஒரு பராமரிப்போம் பைனரி குறியீட்டு மரம். பைனரி குறியீட்டு மரத்தின் அளவு வரிசை உறுப்பின் ஒரு குறிப்பிட்ட தொகுதிக்கான அதிகபட்ச உறுப்பை விட அதிகமாக இருக்கும். ஒவ்வொரு தொகுதிக்கும் எங்களிடம் BIT வரிசை இருப்பதால், வரிசையின் ஒவ்வொரு நிலையிலும் மதிப்பு 1 உடன் மதிப்பு பிட் வரிசையை புதுப்பிக்கவும் [i] மேலும் வரிசையின் ஒவ்வொரு உறுப்புக்கும் அது எங்குள்ளது என்பதைக் கண்டறிந்து மேலே உள்ள அதே நடைமுறையைப் பின்பற்றவும் அந்த தொகுதியின் பிட் வரிசையை 1 at 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

எண்களைக் கண்டுபிடிப்பதற்கான ஜாவா குறியீடு <= subarray இல் கொடுக்கப்பட்ட மதிப்பு

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) வரிசையை அச்சிடுவதற்கு.

விண்வெளி சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. “கொடுக்கப்பட்ட சப்ரேயில் கொடுக்கப்பட்ட எண்ணை விடக் குறைவாகவோ அல்லது சமமாகவோ உள்ள உறுப்புகளின் எண்ணிக்கை” என்ற சிக்கல் நேரியல் இடத்தைக் கொண்டுள்ளது.