આપેલ સબબ્રેમાં આપેલ સંખ્યા કરતા ઓછા અથવા સમાન તત્વોની સંખ્યા


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે કોડનેશન ડીઇ શw Google ઓપેરા પેપાલ Pinterest
અરે વૃક્ષ

સમસ્યા નિવેદન

સમસ્યા "આપેલ સબબ્રેમાં આપેલ સંખ્યા કરતા ઓછી અથવા સમાન તત્વોની સંખ્યા" જણાવે છે કે તમને પૂર્ણાંક એરે અને પ્રશ્નોની સંખ્યા આપવામાં આવે છે. ત્યાં બે પ્રકારના પ્રશ્નો હશે à

  • ક્વેરીUpdate (i, v): ત્યાં બે પૂર્ણાંકો i અને v હશે, જેમ કે એરેને અપડેટ કરે છે [i] = v.
  • ક્વેરી પ્રિંટ (ડાબે, જમણે, કે): 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 કરતા ઓછા અથવા બરાબર તત્વોની છાપશે

ક્વેરીઅપડેટ (2, 8) અનુક્રમણિકા 2 પર તત્વને 8 ની કિંમત સાથે અપડેટ કરશે, એટલે કે {2, 4, 8, 1, 5 ar હશે

ક્વેરી પ્રિંટ (1, 3, 5) અનુક્રમણિકા 5 થી 1 એટલે કે 3 થી 2 કરતા ઓછા અથવા બરાબર તત્વોની છાપશે

ક્વેરીઅપડેટ (,,)) અનુક્રમણિકા at પર element સાથે તત્વને અપડેટ કરશે, એટલે કે r 4, 3, 4, 3, 2 ar હશે

ક્વેરીઅપડેટ (,,)) અનુક્રમણિકા at પર element સાથે તત્વને અપડેટ કરશે, એટલે કે r 1, 3, 1, 3, 2 ar હશે

ક્વેરી પ્રિંટ (1, 2, 4) અનુક્રમણિકા 4 થી 1 એટલે કે 2 થી 1 કરતા ઓછા અથવા બરાબર તત્વોની છાપશે

આપેલ સબબ્રેમાં આપેલ સંખ્યા કરતા ઓછા અથવા સમાન તત્વોની સંખ્યા

 

સંખ્યા શોધવા માટે અલ્ગોરિધમનો <= સબબ્રેમાં આપેલ મૂલ્ય

  1. વિભાજીત કરો એરે n ના ચોરસ રુટ જેટલા કદના બ્લોક્સમાં, જ્યાં n ઇનપુટ એરેનું કદ છે.
  2. ચોક્કસ બ્લોકમાં એરેમાં રહેલા મહત્તમ તત્વ કરતાં એક કરતા વધુ કદના બાઈનરી ઇન્ડેક્સ ટ્રી બનાવો.
  3. એરેના દરેક તત્વ માટે તે બ્લોક શોધી કા whereો જ્યાં તે અનુલક્ષે છે અને બ્લોકની બીઆઈટી એરેને એઆર પર 1 સાથે અપડેટ કરો [i].
  4. દરેક અપડેટ ક્વેરી માટે. -1 સાથે અનુક્રમણિકા માટે એરેના મૂળ મૂલ્યના બ્લોકને અનુરૂપ બીઆઈટી એરેનું મૂલ્ય અપડેટ કરો.
  5. કોઈ ચોક્કસ અનુક્રમણિકાના નવા તત્વ પર મૂલ્ય 1 સાથે સમાન બ્લોકની બીઆઈટી એરે અપડેટ કરો.
  6. દરેક પ્રિન્ટ ક્વેરી માટે. K થી ઓછા અથવા બરાબર તત્વોનું મૂલ્ય ગણવા માટે, બીઆઇટી એરેની ક્વેરી બનાવો. અને સંપૂર્ણ અવરોધ માટે અથવા અપૂર્ણ અથવા આંશિક અવરોધ માટે, બધા તત્વોમાંથી પસાર થવું.

સમજૂતી

અમને પૂર્ણાંક એરે અને બે પ્રકારના પ્રશ્નો આપવામાં આવે છે. એક ક્વેરી એ આપેલ ચોક્કસ અનુક્રમણિકા પર મૂલ્યને અપડેટ કરવાની છે. અને બીજી ક્વેરી એ છે કે k ની બરાબર તત્વોની ગણતરી. અપડેટ ક્વેરી માટે, આપણને અનુક્રમણિકા અને મૂલ્ય આપવામાં આવશે. આપણે વેલ્યુ અપડેટ કરીશું v એરેના આપેલ અનુક્રમણિકા પર [i]. પ્રિન્ટ ક્વેરી અથવા ગણતરી ક્વેરી માટે, આપણે પૂર્ણાંકોની સંખ્યા પ્રિન્ટ કરવાની જરૂર છે, કે જે k કરતા ઓછી અથવા તેના બરાબર છે.

આપણે એરેને કેટલાક બ્લોક્સમાં વહેંચીશું. આ બ્લોક્સ એરેની લંબાઈના ચોરસ રુટ જેવા કદના હશે. દરેક બ્લોક માટે, અમે એક જાળવી રાખીશું દ્વિસંગી અનુક્રમણિકા વૃક્ષ. બાઈનરી ઇન્ડેક્સ ટ્રીનું કદ એરે એલિમેન્ટના ચોક્કસ બ્લોક માટેના મહત્તમ તત્વ કરતાં એક હશે. અમારી પાસે દરેક બ્લોક માટે બીઆઈટી એરે હોવાથી, એરેના દરેક સ્થાન પર મૂલ્ય 1 સાથે મૂલ્ય બીટ એરે અપડેટ કરો [i] અને એરેના દરેક ઘટક માટેનો અવરોધ શોધવા માટે જ્યાં તે સંબંધિત છે અને ઉપરની સમાન પ્રક્રિયાને અનુસરો એ બ્લ blockકની બીટ એરેને 1 સાથે અરમાં [i] સાથે અપડેટ કરો.

દરેક અપડેટ ક્વેરી માટે, બીઆઇટી એરેને અપડેટ કરો. અમારી પાસે દરેક એરે એલિમેન્ટ માટે અવરોધ છે. એરેનું મૂલ્ય -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) એરે અપડેટ કરવા માટે અને ઓ (એન) એરે છાપવા માટે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. સમસ્યા "આપેલ સબબ્રેમાં આપેલ સંખ્યા કરતા ઓછી અથવા સમાન તત્વોની સંખ્યા" માં રેખીય જગ્યા છે.