Տրված թվից պակաս կամ հավասար է տարրերի քանակը տրված ենթաշարքում


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են CodeNation ԴԵ Շոուն Google Օպերա PayPal Pinterest
Դասավորություն ծառ

Խնդիրի հայտարարություն

«Տրված ենթածրագրում տրված թվից պակաս կամ հավասար տարրերի քանակը» խնդրում նշվում է, որ ձեզ տրվում է ամբողջ զանգված և հարցումների քանակ: Կլինեն երկու տեսակի հարցում

  • 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 զանգվածը arr- ի 1-ով [i]:
  4. Յուրաքանչյուր թարմացման հարցման համար: Թարմացրեք BIT զանգվածի արժեքը `1-ով ցուցանիշի համար զանգվածի սկզբնական արժեքի բլոկի համեմատ:
  5. Թարմացրեք նույն բլոկի BIT զանգվածը որոշակի ինդեքսի նոր տարրի 1 արժեքով:
  6. Տպման յուրաքանչյուր հարցման համար: Հարցում կատարեք BIT զանգվածին ՝ k- ից պակաս կամ հավասար տարրերի հաշվարկի համար: Իսկ ամբողջական բլոկի կամ թերի կամ մասնակի բլոկի համար անցեք բոլոր տարրերով:

բացատրություն

Մեզ տրվում է ամբողջ զանգված և երկու տեսակի հարցումներ: Հարցերից մեկը արժեքը թարմացնել տվյալ որոշակի ինդեքսում: Եվ մեկ այլ հարց է `k- ի հավասարից պակաս տարրերի քանակը ստանալ: Թարմացման հարցման համար մեզ կտրվի ցուցիչ և արժեք: Մենք կթարմացնենք արժեքը v զանգվածի տվյալ ցուցիչում [i]: Տպման հարցման կամ հաշվարկի հարցման համար մենք պետք է տպենք ամբողջ թվերի քանակը, որոնք k- ից պակաս են կամ հավասար են:

Մենք պատրաստվում ենք զանգվածը բաժանել որոշ բլոկների: Այս բլոկների չափը կլինի զանգվածի երկարության քառակուսի արմատ: Յուրաքանչյուր բլոկի համար մենք պահպանելու ենք a երկուական ցուցիչ ծառ, Երկուական ցուցիչի ծառի չափը կլինի զանգվածի տարրի որոշակի բլոկի առավելագույն տարրից ավելին: Քանի որ յուրաքանչյուր բլոկի համար ունենք BIT զանգված, թարմացրեք բիթի զանգվածի զանգվածը զանգվածի յուրաքանչյուր դիրքի 1-ի արժեքով և նաև պարզեք զանգվածի յուրաքանչյուր տարրի այն հատվածը, որտեղ նա պատկանում է և հետևեք նույն ընթացակարգին, ինչ վերևում: թարմացրեք այդ բլոկի բիտ զանգվածը arr- ով 1-ով [i]:

Յուրաքանչյուր թարմացման հարցման համար թարմացրեք BIT զանգվածը: Քանի որ յուրաքանչյուր զանգվածի համար մենք ունենք բլոկ: Indexանգվածի արժեքը որոշակի ինդեքսում թարմացրեք -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

Բարդության վերլուծություն

Timeամանակի բարդություն

Ո (1) զանգվածը թարմացնելու համար և O (n) զանգվածը տպելու համար:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: «Տրված ենթածրագրում տրված թվից պակաս կամ հավասար տարրերի քանակը» խնդիրն ունի գծային տարածություն: