ਦਿੱਤੇ ਗਏ ਸਬਅਰੇਅ ਵਿਚ ਦਿੱਤੇ ਨੰਬਰ ਤੋਂ ਘੱਟ ਜਾਂ ਇਸਦੇ ਬਰਾਬਰ ਤੱਤ ਦੀ ਗਿਣਤੀ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਕੋਡਨੇਸ਼ਨ ਡੀਈ ਸ਼ਾ ਗੂਗਲ ਓਪੇਰਾ ਪੇਪਾਲ ਕਿਰਾਏ ਨਿਰਦੇਸ਼ਿਕਾ
ਅਰੇ ਟ੍ਰੀ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ "ਕਿਸੇ ਦਿੱਤੇ ਉਪਨਗਰੀ ਵਿਚ ਦਿੱਤੀ ਗਈ ਗਿਣਤੀ ਤੋਂ ਘੱਟ ਜਾਂ ਇਸ ਦੇ ਬਰਾਬਰ ਤੱਤ ਦੀ ਗਿਣਤੀ" ਦੱਸਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਪੂਰਨ ਅੰਕ ਅਤੇ ਪ੍ਰਸ਼ਨਾਂ ਦੀ ਗਿਣਤੀ ਦਿੱਤੀ ਜਾਂਦੀ ਹੈ. ਇੱਥੇ ਦੋ ਕਿਸਮਾਂ ਦੇ ਪ੍ਰਸ਼ਨ ਹੋਣਗੇ à

  • queryUpdate (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 ਦੇ ਨਾਲ ਅਪਡੇਟ ਕਰੇਗੀ ਭਾਵ ਅਰਰ ar 2, 4, 8, 1, 5} ਹੋਵੇਗਾ

ਪੁੱਛ-ਪੜਤਾਲ (1, 3, 5) ਸੂਚਕਾਂਕ 5 ਤੋਂ 1 ਭਾਵ 3 ਤੋਂ ਘੱਟ ਜਾਂ ਇਸਦੇ ਬਰਾਬਰ ਦੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਪ੍ਰਿੰਟ ਕਰੇਗੀ, ਭਾਵ 2

ਪੁੱਛਗਿੱਛ ਅਪਡੇਟ (4, 3) ਸੂਚਕਾਂਕ 4 ਤੇ ਤੱਤ ਨੂੰ 3 ਨਾਲ ਅਪਡੇਟ ਕਰੇਗੀ ਭਾਵ ਅਰਰ {2, 4, 8, 1, 3} ਹੋਵੇਗਾ

ਪੁੱਛਗਿੱਛ ਅਪਡੇਟ (1, 3) ਸੂਚਕਾਂਕ 1 ਤੇ ਤੱਤ ਨੂੰ 3 ਨਾਲ ਅਪਡੇਟ ਕਰੇਗੀ ਭਾਵ ਅਰਰ {2, 3, 8, 1, 3} ਹੋਵੇਗਾ

ਪੁੱਛ-ਪੜਤਾਲ (1, 2, 4) ਸੂਚਕਾਂਕ 4 ਤੋਂ 1 ਭਾਵ 2 ਤੋਂ ਘੱਟ ਜਾਂ ਇਸਦੇ ਬਰਾਬਰ ਦੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਪ੍ਰਿੰਟ ਕਰੇਗੀ, ਭਾਵ 1

ਦਿੱਤੇ ਗਏ ਸਬਅਰੇਅ ਵਿਚ ਦਿੱਤੇ ਨੰਬਰ ਤੋਂ ਘੱਟ ਜਾਂ ਇਸਦੇ ਬਰਾਬਰ ਤੱਤ ਦੀ ਗਿਣਤੀ

 

ਨੰਬਰ ਲੱਭਣ ਲਈ ਐਲਗੋਰਿਦਮ <= ਸਬਰੇਅ ਵਿੱਚ ਦਿੱਤਾ ਮੁੱਲ

  1. ਵੰਡੋ ਐਰੇ n ਦੇ ਵਰਗ ਰੂਟ ਦੇ ਬਰਾਬਰ ਅਕਾਰ ਦੇ ਬਲਾਕਾਂ ਵਿਚ, ਜਿੱਥੇ n ਇਨਪੁਟ ਐਰੇ ਦਾ ਆਕਾਰ ਹੈ.
  2. ਕਿਸੇ ਖਾਸ ਬਲਾਕ ਵਿੱਚ ਐਰੇ ਵਿੱਚ ਮੌਜੂਦ ਵੱਧ ਤੋਂ ਵੱਧ ਤੱਤ ਤੋਂ ਵੱਧ ਅਕਾਰ ਦਾ ਇੱਕ ਬਾਇਨਰੀ ਇੰਡੈਕਸ ਲੜੀ ਬਣਾਉ.
  3. ਐਰੇ ਦੇ ਹਰੇਕ ਤੱਤ ਦੇ ਲਈ ਬਲਾਕ ਲੱਭੋ ਜਿੱਥੇ ਇਹ ਸੰਬੰਧਿਤ ਹੈ ਅਤੇ ਬਲਾਕ ਦੀ ਬੀ ਆਈ ਟੀ ਐਰੇ ਨੂੰ ਏਰ 1 ਤੇ ਅਪਡੇਟ ਕਰੋ [i].
  4. ਹਰੇਕ ਅਪਡੇਟ ਪੁੱਛਗਿੱਛ ਲਈ. -1 ਨਾਲ ਇੰਡੈਕਸ ਲਈ ਐਰੇ ਦੇ ਅਸਲ ਮੁੱਲ 'ਤੇ ਬਲਾਕ ਦੇ ਅਨੁਸਾਰੀ, ਬਿਟ ਐਰੇ ਦਾ ਮੁੱਲ ਅਪਡੇਟ ਕਰੋ.
  5. ਕਿਸੇ ਵਿਸ਼ੇਸ਼ ਸੂਚਕਾਂਕ ਦੇ ਨਵੇਂ ਤੱਤ ਤੇ ਮੁੱਲ 1 ਦੇ ਨਾਲ ਉਸੇ ਬਲਾਕ ਦੀ ਬੀਆਈਟੀ ਐਰੇ ਨੂੰ ਅਪਡੇਟ ਕਰੋ.
  6. ਹਰੇਕ ਪ੍ਰਿੰਟ ਪੁੱਛਗਿੱਛ ਲਈ. ਐਲੀਮੈਂਟਸ ਦੇ ਮੁੱਲ ਨੂੰ k ਤੋਂ ਘੱਟ ਜਾਂ ਇਸ ਦੇ ਬਰਾਬਰ ਗਿਣਨ ਲਈ, BIT ਐਰੇ ਲਈ ਕੋਈ ਪੁੱਛਗਿੱਛ ਕਰੋ. ਅਤੇ ਪੂਰੇ ਬਲਾਕ ਲਈ ਜਾਂ ਅਧੂਰੇ ਜਾਂ ਅੰਸ਼ਕ ਬਲਾਕ ਲਈ, ਸਾਰੇ ਤੱਤਾਂ ਨੂੰ ਪਾਰ ਕਰੋ.

ਕਥਾ

ਸਾਨੂੰ ਇਕ ਪੂਰਨ ਅੰਕ ਐਰੇ ਅਤੇ ਦੋ ਕਿਸਮਾਂ ਦੇ ਪ੍ਰਸ਼ਨ ਦਿੱਤੇ ਗਏ ਹਨ. ਇੱਕ ਪੁੱਛਗਿੱਛ ਇੱਕ ਦਿੱਤੇ ਖਾਸ ਇੰਡੈਕਸ ਤੇ ਮੁੱਲ ਨੂੰ ਅਪਡੇਟ ਕਰਨ ਲਈ ਹੈ. ਅਤੇ ਇਕ ਹੋਰ ਪੁੱਛਗਿੱਛ ਹੈ ਕੇ ਦੇ ਬਰਾਬਰ ਤੋਂ ਘੱਟ ਤੱਤ ਦੀ ਗਿਣਤੀ ਪ੍ਰਾਪਤ ਕਰਨਾ. ਅਪਡੇਟ ਪੁੱਛਗਿੱਛ ਲਈ, ਸਾਨੂੰ ਇੱਕ ਸੂਚਕਾਂਕ ਅਤੇ ਇੱਕ ਮੁੱਲ ਦਿੱਤਾ ਜਾਵੇਗਾ. ਅਸੀਂ ਮੁੱਲ ਨੂੰ ਅਪਡੇਟ ਕਰਾਂਗੇ v ਐਰੇ ਦੇ ਦਿੱਤੇ ਸੂਚਕਾਂਕ ਤੇ [i]. ਪ੍ਰਿੰਟ ਪੁੱਛਗਿੱਛ ਜਾਂ ਕਾ queryਂਟ ਪੁੱਛਗਿੱਛ ਲਈ, ਸਾਨੂੰ ਪੂਰਨ ਅੰਕ ਦੀ ਗਿਣਤੀ ਪ੍ਰਿੰਟ ਕਰਨ ਦੀ ਲੋੜ ਹੈ, ਜੋ ਕੇ ਕੇ ਤੋਂ ਘੱਟ ਜਾਂ ਬਰਾਬਰ ਹਨ.

ਅਰੇ ਨੂੰ ਕੁਝ ਬਲਾਕਾਂ ਵਿੱਚ ਵੰਡਣ ਜਾ ਰਹੇ ਹਾਂ. ਇਹ ਬਲਾਕ ਅਕਾਰ ਦੀ ਲੰਬਾਈ ਦੇ ਵਰਗ ਵਰਗ ਦੇ ਰੂਪ ਵਿੱਚ ਅਕਾਰ ਦੇ ਹੋਣਗੇ. ਹਰ ਬਲਾਕ ਲਈ, ਅਸੀਂ ਏ ਬਾਈਨਰੀ ਇੰਡੈਕਸ ਟ੍ਰੀ. ਬਾਈਨਰੀ ਇੰਡੈਕਸ ਲੜੀ ਦਾ ਆਕਾਰ ਐਰੇ ਐਲੀਮੈਂਟ ਦੇ ਕਿਸੇ ਖਾਸ ਬਲਾਕ ਲਈ ਵੱਧ ਤੋਂ ਵੱਧ ਤੱਤ ਤੋਂ ਵੱਧ ਇਕ ਹੋਵੇਗਾ. ਕਿਉਂਕਿ ਸਾਡੇ ਕੋਲ ਹਰੇਕ ਬਲਾਕ ਲਈ ਬਿਟ ਐਰੇ ਹੈ, ਐਰੇ ਦੀ ਹਰੇਕ ਸਥਿਤੀ ਤੇ ਮੁੱਲ 1 ਦੇ ਨਾਲ ਵੈਲਯੂ ਬਿੱਟ ਐਰੇ ਨੂੰ ਅਪਡੇਟ ਕਰੋ [i] ਅਤੇ ਐਰੇ ਦੇ ਹਰੇਕ ਤੱਤ ਦੇ ਲਈ ਬਲਾਕ ਦਾ ਪਤਾ ਲਗਾਓ ਜਿੱਥੇ ਇਹ ਸੰਬੰਧਿਤ ਹੈ ਅਤੇ ਉਪਰੋਕਤ ਵਾਂਗ ਉਸੇ ਪ੍ਰਕਿਰਿਆ ਦੀ ਪਾਲਣਾ ਕਰੋ. ਉਸ ਬਲਾਕ ਦੀ ਬਿੱਟ ਐਰੇ ਨੂੰ 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) ਐਰੇ ਨੂੰ ਅਪਡੇਟ ਕਰਨ ਲਈ ਅਤੇ ਹੇ (n) ਐਰੇ ਨੂੰ ਪ੍ਰਿੰਟ ਕਰਨ ਲਈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਹੇ (n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਸਮੱਸਿਆ "ਦਿੱਤੇ ਉਪਨਗਰੀ ਵਿੱਚ ਦਿੱਤੀ ਗਈ ਗਿਣਤੀ ਤੋਂ ਘੱਟ ਜਾਂ ਇਸ ਦੇ ਬਰਾਬਰ ਤੱਤ ਦੀ ਗਿਣਤੀ" ਵਿੱਚ ਲੀਨੀਅਰ ਸਪੇਸ ਹੈ.