Αριθμός στοιχείων μικρότερο ή ίσο με έναν δεδομένο αριθμό σε μια δεδομένη υποπεριοχή


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις CodeNation DE Shaw Google Opera 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 του μπλοκ με το 1 στο arr [i].
  4. Για κάθε ερώτημα ενημέρωσης. Ενημερώστε την τιμή του πίνακα BIT, σε σχέση με το μπλοκ στην αρχική τιμή του πίνακα για το ευρετήριο με -1.
  5. Ενημερώστε τον πίνακα BIT του ίδιου μπλοκ με την τιμή 1 στο νέο στοιχείο ενός συγκεκριμένου ευρετηρίου.
  6. Για κάθε ερώτημα εκτύπωσης. Κάντε ένα ερώτημα στον πίνακα BIT, για να μετρήσετε την τιμή των στοιχείων μικρότερη ή ίση με k. Και για το πλήρες μπλοκ ή για το ημιτελές ή μερικό μπλοκ, διασχίστε όλα τα στοιχεία.

εξήγηση

Μας δίνεται ένας ακέραιος πίνακας και δύο τύποι ερωτημάτων. Ένα ερώτημα είναι να ενημερώσετε την τιμή σε ένα συγκεκριμένο ευρετήριο. Και ένα άλλο ερώτημα είναι να λάβετε το πλήθος των στοιχείων μικρότερο από ίσο με το k. Για το ερώτημα ενημέρωσης, θα μας δοθεί ένα ευρετήριο και μια τιμή. Θα ενημερώσουμε την τιμή v στο δεδομένο ευρετήριο του πίνακα [i]. Για το ερώτημα εκτύπωσης ή το ερώτημα καταμέτρησης, πρέπει να εκτυπώσουμε τον αριθμό των ακεραίων, που είναι μικρότερος ή ίσος με k.

Θα χωρίσουμε τον πίνακα σε μερικά μπλοκ. Αυτά τα μπλοκ θα έχουν μέγεθος όπως η τετραγωνική ρίζα του μήκους του πίνακα. Για κάθε μπλοκ, θα διατηρούμε ένα δυαδικό ευρετήριο. Το μέγεθος του δέντρου δυαδικού δείκτη θα είναι ένα περισσότερο από το μέγιστο στοιχείο για ένα συγκεκριμένο μπλοκ του στοιχείου πίνακα. Δεδομένου ότι έχουμε πίνακα BIT για κάθε μπλοκ, ενημερώστε τον πίνακα τιμών bit με την τιμή 1 σε κάθε θέση του πίνακα [i] και ανακαλύψτε επίσης το μπλοκ για κάθε στοιχείο του πίνακα στο οποίο ανήκει και ακολουθήστε την ίδια διαδικασία όπως παραπάνω ενημερώστε τον πίνακα bit αυτού του μπλοκ με 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

Ο (1) για ενημέρωση του πίνακα και O (n) για εκτύπωση του πίνακα.

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Το πρόβλημα «Αριθμός στοιχείων μικρότερο ή ίσο με έναν δεδομένο αριθμό σε μια δεδομένη υποπεριοχή» έχει γραμμικό διάστημα.