تعداد عناصر کمتر یا مساوی با یک عدد داده شده در زیرآرایه داده شده


سطح دشواری سخت
اغلب در CodeNation دی شاو گوگل اپرا پی پال پینترست
صف درخت

بیان مسأله

مسئله "تعداد عناصر کمتر یا مساوی با یک عدد داده شده در یک زیرآرایه مشخص شده" بیانگر این است که به شما یک آرایه صحیح و تعداد تعداد پرسش به شما داده می شود. دو نوع درخواست وجود خواهد داشت

  • 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} خواهد بود

queryPrint (1 ، 3 ، 5) تعداد عناصر کمتر یا مساوی 5 را از شاخص 1 تا 3 چاپ می کند ، یعنی 2

queryUpdate (4 ، 3) عنصر را در شاخص 4 با 3 به روز می کند ، یعنی arr {2، 4، 8، 1، 3} خواهد بود

queryUpdate (1 ، 3) عنصر را در شاخص 1 با 3 به روز می کند ، یعنی arr {2، 3، 8، 1، 3} خواهد بود

queryPrint (1 ، 2 ، 4) تعداد عناصر کمتر یا مساوی 4 را از شاخص 1 تا 2 چاپ می کند ، یعنی 1

تعداد عناصر کمتر یا مساوی با یک عدد داده شده در زیرآرایه داده شده

 

الگوریتم پیدا کردن اعداد <= مقدار داده شده در زیرآرایه

  1. تقسیم کنید صف به بلوکهایی با اندازه برابر ریشه مربع n ، جایی که n اندازه آرایه ورودی است.
  2. یک درخت شاخص باینری با اندازه یک بیشتر از حداکثر عنصر موجود در آرایه در یک بلوک خاص ایجاد کنید.
  3. بلوک مربوط به هر یک از عناصر آرایه را به محلی که در آن قرار دارد پیدا کنید و آرایه BIT بلوک را با 1 در ar به روز کنید [i].
  4. برای هر پرسش به روزرسانی مقدار آرایه BIT را نسبت به بلوک در مقدار اصلی آرایه برای شاخص با -1 به روز کنید.
  5. آرایه BIT همان بلوک را با مقدار 1 در عنصر جدید یک شاخص خاص به روز کنید.
  6. برای هر پرسش چاپ. برای آرایه BIT پرس و جو کنید تا عناصر با مقدار کمتر از یا برابر آن شمارش شوند. و برای بلوک کامل یا برای بلوک ناقص یا جزئی ، از طریق تمام عناصر عبور کنید.

توضیح

به ما یک آرایه صحیح و دو نوع پرسش داده می شود. یک پرسش این است که مقدار را در یک شاخص خاص مشخص به روز کنید. و پرسش دیگر بدست آوردن تعداد عناصر کمتر از k است. برای پرس و جو به روزرسانی ، یک نمایه و یک مقدار به ما داده می شود. ما مقدار را به روز می کنیم v در فهرست داده شده آرایه [i]. برای پرس و جو چاپ یا پرسش تعداد ، باید تعداد عدد صحیح را که کمتر از k است یا برابر آن چاپ کنیم.

ما می خواهیم آرایه را به چند بلوک تقسیم کنیم. اندازه این بلوک ها به اندازه ریشه مربع طول آرایه خواهد بود. برای هر بلوک ، ما یک a را حفظ خواهیم کرد درخت شاخص باینری. اندازه درخت شاخص باینری یک بزرگتر از حداکثر عنصر برای یک بلوک خاص از عنصر آرایه خواهد بود. از آنجا که برای هر بلوک آرایه BIT داریم ، آرایه مقدار بیت را با مقدار 1 در هر موقعیت آرایه به روز کنید و همچنین بلوک مربوط به هر عنصر آرایه را به محلی که متعلق است پیدا کنید و همان روش بالا را دنبال کنید آرایه بیت آن بلوک را با 1 در arr به روز کنید [i].

برای هر درخواست به روزرسانی ، آرایه BIT را به روز کنید. از آنجا که برای هر عنصر آرایه یک بلوک داریم. مقدار آرایه را در یک شاخص خاص با مقدار -1 به روز کنید و آرایه BIT بلوک مورد نیاز را با مقدار 1 در عنصر جدید آرایه در فهرست داده شده به روز کنید. و برای پرس و جو از چاپ یا شمارش مقادیر ، فقط از طریق حلقه عبور کنید. دو مورد وجود دارد که برای بلوک کامل یا برای بلوک کامل جزئی است. در آخر مقدار را برگردانید.

رمز

کد C ++ برای یافتن اعداد <= مقدار داده شده در زیرآرایه

#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) برای به روزرسانی آرایه و O (N) برای چاپ آرایه

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است. مسئله "تعداد عناصر کمتر یا مساوی با یک عدد داده شده در زیر آرایه مشخص" دارای فضای خطی است.