Берилген подразделениеде берилген санга аз же ага барабар элементтердин саны


Кыйынчылык деңгээли катуу
Көп суралган CodeNation DE Shaw Гугл опера PayPal Pinterest
согуштук тизме дарак

Маселени билдирүү

"Берилген субарряддагы берилген санга жетпеген же ага барабар элементтердин саны" маселеси сизге бүтүн массив жана q суроолордун саны берилгенин билдирет. Суроолордун эки түрү болот à

  • queryUpdate (i, v): [i] = v массивин жаңырткан эки i жана v сандары болот.
  • queryPrint (сол, оң, 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 at arr [i] менен жаңыртыңыз.
  4. Ар бир жаңыртуу суроосу үчүн. BIT массивинин маанисин, индекс үчүн массивдин баштапкы маанисиндеги блокко салыштырмалуу -1 менен жаңыртыңыз.
  5. Ошол эле блоктун BIT массивин белгилүү бир индекстин жаңы элементиндеги 1 мааниси менен жаңыртыңыз.
  6. Ар бир басып чыгаруу суроосу үчүн. Элементтин маанисин k дан кем же барабар санап, BIT массивине суроо жасаңыз. Толук блок үчүн же толук эмес же жарым-жартылай блок үчүн бардык элементтерди аралап өтүңүз.

түшүндүрүү

Бизге бүтүндөй массив жана эки түрдөгү суроо берилет. Суроолордун бири - берилген индекстеги маанини жаңыртуу. Дагы бир суроо - элементтердин санын кге барабар алуу. Жаңыртуу сурамы үчүн бизге индекс жана маани берилет. Биз наркты жаңыртабыз v массивдин [i] берилген индекси боюнча. Басып чыгаруу суроосу же саноо суроосу үчүн, k дан кичине же барабар бүтүн сандардын санын басып чыгарышыбыз керек.

Массивди айрым блокторго бөлгөнү жатабыз. Бул блоктор массивдин узундугунун чарчы тамыры сыяктуу чоңдукта болот. Ар бир блок үчүн биз а экилик индекс дарагы. Экилик индекс дарагынын өлчөмү массив элементинин белгилүү бир блогу үчүн максималдуу элементтен чоңураак болот. Ар бир блок үчүн BIT массивибиз бар болгондуктан, [i] массивинин ар бир позициясындагы 1 мааниси бар бит бит массивин жаңыртып, массивдин ар бир элементине тиешелүү блокту таап, жогорудагыдай процедураны аткарыңыз. ошол блоктун бит массивин arr at 1 менен arr [i].

Ар бир жаңыртуу суроосу үчүн, BIT массивин жаңыртыңыз. Бизде ар бир массив элементтери үчүн блок бар. Массивдин маанисин белгилүү бир индексте -1 мааниси менен жаңыртып, керектүү блоктун BIT массивин 1 индексиндеги массивдин жаңы элементиндеги XNUMX мааниси менен жаңыртыңыз. Басып чыгаруу суранышы же баалуулуктарды эсептөө үчүн, цикл аркылуу өтүңүз. Толук блокко же жарым-жартылай толук блокко байланыштуу эки учур болот. Акырында маанини кайтарыңыз.

коду

Сандарды табуу үчүн C ++ коду <= subarrayдагы берилген маани

#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) массивди жаңыртуу үчүн жана O (N) массивди басып чыгаруу үчүн.

Космостун татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны. "Берилген субарряддагы берилген санга жетпеген же ага барабар элементтердин саны" маселеси сызыктуу мейкиндикке ээ.