Өгөгдсөн дэд массив дахь өгөгдсөн тооноос бага эсвэл тэнцүү элементийн тоо


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг CodeNation DE Шоу Google-ийн Opera PayPal Pinterest
Array Мод

Асуудлын мэдэгдэл

“Өгөгдсөн дэд массив дахь өгөгдсөн тооноос бага буюу тэнцүү элементийн тоо” гэсэн асуудалд танд бүхэл тоон массив, q асуулгын тоо өгөгдсөн болно. Хоёр төрлийн асуулт байх болно à

  • queryUpdate (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 at 1 at [i] болгож шинэчил.
  4. Шинэчлэлт хийх хүсэлт бүрийн хувьд. BIT массивын утгыг индексийн массивын анхны утга дахь блоктой харьцуулан -1-ээр шинэчилнэ.
  5. Ижил блокийн BIT массивыг тодорхой индексийн шинэ элемент дээр 1 гэсэн утгатай шинэчил.
  6. Асуулт бүрийн хувьд. K-ээс бага эсвэл тэнцүү элементийн утгыг тоолохын тулд BIT массивт асуулга хийнэ. Бүрэн блок эсвэл бүрэн бус эсвэл хэсэгчилсэн блокын хувьд бүх элементүүдээр дамжина уу.

Тайлбар

Бид бүхэл тоон массив, хоёр төрлийн асуулга өгдөг. Нэг асуулт бол тухайн индекс дэх утгыг шинэчлэх явдал юм. Өөр нэг асуулт бол k-ээс бага элементийн тоог авах явдал юм. Шинэчлэлтийн асуулгын хувьд бидэнд индекс ба утга өгөх болно. Бид утгыг шинэчлэх болно v массивын өгөгдсөн индекс дээр [i]. Хэвлэх асуулга эсвэл тоолох асуулгын хувьд бид k-ээс бага буюу тэнцүү бүхэл тоон тоог хэвлэх хэрэгтэй.

Бид массивыг хэдэн блок болгон хуваах гэж байна. Эдгээр блокууд нь массивын уртын квадрат язгуурын хэмжээтэй байх болно. Блок бүрийн хувьд бид a-г хадгалах болно хоёртын индексийн мод. Хоёртын индексийн модны хэмжээ нь массив элементийн тодорхой блокийн хамгийн их элементээс их байх болно. Бидэнд блок тус ​​бүрт BIT массив байгаа тул [i] массивын байрлал бүрт утгын битийн массивыг 1 гэсэн утгатай шинэчилж, массивын элемент тус бүрийн блокыг харьяалагдах хэсэгт олж, дээрхтэй ижил процедурыг дагана уу. arr [i] дээр тухайн блокийн битийн массивыг 1-ээр шинэчлэх.

Шинэчлэлт хийх хүсэлт бүрийн хувьд 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) массивыг шинэчлэхэд зориулагдсан ба O (N) массивыг хэвлэх.

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. "Өгөгдсөн дэд массив дахь өгөгдсөн тооноос бага буюу тэнцүү элементийн тоо" гэсэн асуудал нь шугаман зайтай байна.