Брой елементи, по-малки или равни на дадено число в даден подмасив


Ниво на трудност Трудно
Често задавани в CodeNation DE Шоу Google опера PayPal Pinterest
Array Дърво

Декларация за проблема

Проблемът „Брой елементи, по-малък или равен на дадено число в даден подмасив“, гласи, че сте получили цяло число масив и 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}

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 в arr [i].
  4. За всяка заявка за актуализация. Актуализирайте стойността на BIT масива спрямо блока при първоначалната стойност на масива за индекса с -1.
  5. Актуализирайте BIT масива на същия блок със стойността 1 в новия елемент на определен индекс.
  6. За всяка заявка за печат. Направете заявка към масива BIT, за да преброите стойността на елементите по-малка или равна на k. А за пълния блок или за непълния или частичния блок преминете през всички елементи.

Обяснение

Получават се масив от цяло число и два вида заявки. Една заявка е да актуализирате стойността при даден конкретен индекс. И друга заявка е да се получи броят на елементите, по-малък от равен на k. За заявката за актуализация ще ни бъде даден индекс и стойност. Ще актуализираме стойността v при дадения индекс на масив [i]. За заявката за печат или заявката за преброяване трябва да отпечатаме броя на целите числа, които са по-малко или равно на k.

Ще разделим масива на няколко блока. Тези блокове ще бъдат с размер като квадратен корен от дължината на масива. За всеки блок ще поддържаме a дърво на двоичен индекс. Размерът на дървото на двоичния индекс ще бъде този, който е повече от максималния елемент за определен блок от елемента на масива. Тъй като имаме BIT масив за всеки блок, актуализирайте масива от битове със стойност 1 на всяка позиция на масива [i] и също така открийте блока за всеки елемент от масива там, където му е мястото и следвайте същата процедура, както по-горе актуализирайте битовия масив на този блок с 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

Java код за намиране на числа <= зададена стойност в подмасив

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) за актуализиране на масива и О (п) за отпечатване на масива.

Сложност на пространството

О (п) където "н" е броят на елементите в масива. Задачата „Брой елементи, по-малки или равни на дадено число в даден подмасив“ има линейно пространство.