Број на елементи помали или еднакви на даден број во дадена под-низа


Ниво на тешкотија Тешко
Често прашувано во CodeNation ДЕ Шо Google Опера PayPal Pinterest
Низа Дрво

Изјава за проблем

Проблемот „Број на елементи помал или еднаков на даден број во дадена под-низа“ наведува дека ви е дадена цел ред низа и q број на пребарувања. Beе има два вида пребарувања à

  • queryUpdate (i, v): willе има два интеграла 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 на блокот со arr 1 [i].
  4. За секое барање за ажурирање. Ажурирајте ја вредноста на низата BIT, во однос на блокот во оригиналната вредност на низата за индексот со -1.
  5. Ажурирајте ја низата BIT на истиот блок со вредноста 1 на новиот елемент на одреден индекс.
  6. За секое барање за печатење. Направете барање до низата BIT, за да ги изброите елементите со вредност помала или еднаква на k. И за целосниот блок или за нецелосниот или делумниот блок, поминете низ сите елементи.

Објаснување

Дадена ни е цел број низа и два вида пребарувања. Едно барање е да се ажурира вредноста на даден посебен индекс. И друго барање е да се добие бројот на елементи помали од еднакви на k. За барањето за ажурирање, ќе добиеме индекс и вредност. Ние ќе ја ажурираме вредноста v на дадениот индекс на низа [i]. За барање за печатење или барање за броење, треба да испечатиме број на цели броеви, кои се помали или еднакви на k.

Toе ја поделиме низата на некои блокови. Овие блокови ќе бидат со големина како квадратниот корен на должината на низата. За секој блок, ќе одржуваме a дрво на бинарен индекс. Големината на стеблото на бинарен индекс ќе биде една повеќе од максималниот елемент за одреден блок од елементот на низата. Бидејќи имаме низа BIT за секој блок, ажурирајте ја низата бит со вредност со вредноста 1 на секоја позиција од низата [i] и, исто така, дознајте го блокот за секој елемент од низата до каде што припаѓа и следете ја истата постапка како погоре ажурирајте ја низата битови од тој блок со 1 во arr [i].

За секое барање за ажурирање, ажурирајте ја низата BIT. Бидејќи имаме блок за секој елемент од низата. Ажурирајте ја вредноста на низата во одреден индекс со вредноста -1 и ажурирајте ја низата BIT на потребниот блок со вредноста 1 на новиот елемент на низата кај дадениот индекс. И за барање за печатење или броење на вредностите, само поминете низ јамката. Beе има два случаи кои се однесуваат на целосниот блок или за делумниот целосен блок. Конечно вратете ја вредноста.

Код

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

Анализа на сложеност

Временска комплексност

О (1) за ажурирање на низата и Тој) за печатење на низата.

Комплексноста на просторот

Тој) каде „Н“ е бројот на елементи во низата. Проблемот „Број на елементи помал или еднаков на даден број во дадена под-низа“ има линеарен простор.