Количество элементов, меньшее или равное заданному числу в данном подмассиве


Сложный уровень Жесткий
Часто спрашивают в CodeNation Де Шоу Google Opera PayPal Pinterest
массив дерево

Постановка задачи

Задача «Число элементов, меньшее или равное заданному числу в данном подмассиве» утверждает, что вам дан целочисленный массив и q количество запросов. Будет два типа запросов à

  • queryUpdate (i, v): будет два целых числа i и v, которые обновят массив [i] = v.
  • queryPrint (left, right, 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.

Мы собираемся разделить массив на несколько блоков. Эти блоки будут иметь размер, равный квадратному корню из длины массива. Для каждого блока мы будем поддерживать дерево двоичных индексов. Размер двоичного индексного дерева будет на единицу больше, чем максимальный элемент для конкретного блока элемента массива. Поскольку у нас есть массив 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) для обновления массива и О (п) для печати массива.

Космическая сложность

О (п) в котором «Н» - количество элементов в массиве. Задача «Число элементов, меньшее или равное заданному числу в данном подмассиве» имеет линейное пространство.