Recupero del valore massimo da un intervallo nella matrice non ordinata

Penso che potresti costruire una specie di albero binario in cui ogni nodo figlio sinistro contiene il valore massimo nella metà sinistra dell'intervallo coperto dal suo genitore e il nodo destro del bambino il valore massimo nella metà destra.

            78           
     45            78     
  23    45     78      6  
23 17  9 45   78 2    4 6   

Quindi devi solo trovare un modo per determinare quali nodi devi minimamente controllare per trovare il valore massimo nell'intervallo interrogato. In questo esempio, per ottenere il valore massimo nell'intervallo indice [2, 6] avresti max(45, 78, 4) anziché max(9, 45, 78, 2, 4) . Man mano che l'albero cresce, il guadagno sarà maggiore.

Il miglior algoritmo sarebbe nel tempo O (n) come sotto let start, end be the index of the bounds of range

int findMax(int[] a, start, end) {
   max = Integer.MIN; // initialize to minimum Integer

   for(int i=start; i <= end; i++) 
      if ( a[i] > max )
         max = a[i];

   return max; 
}

Per completare la risposta di ngoaho91.

Il modo migliore per risolvere questo problema è usare la struttura dei dati di Segment Tree. Ciò consente di rispondere a tali query in O (log (n)), ciò significherebbe che la complessità totale del proprio algoritmo sarebbe O (Q logn) dove Q è il numero di query. Se si è utilizzato l'algoritmo ingenuo, la complessità totale sarebbe O (Q n), che è evidentemente più lento.

Tuttavia, c'è un inconveniente nell'utilizzo di Segment Trees. Richiede molta memoria, ma molte volte ti interessa meno della memoria che della velocità.

Descriverò brevemente gli algoritmi utilizzati da questo DS:

L'albero del segmento è solo un caso speciale di un albero di ricerca binaria, in cui ogni nodo contiene il valore dell'intervallo a cui è assegnato. Al nodo radice, viene assegnato l'intervallo [0, n]. Al bambino sinistro viene assegnato l'intervallo [0, (0 + n) / 2] e il bambino destro [(0 + n) / 2 + 1, n]. In questo modo verrà costruito l'albero.

Crea albero :

/*
    A[] -> array of original values
    tree[] -> Segment Tree Data Structure.
    node -> the node we are actually in: remember left child is 2*node, right child is 2*node+1
    a, b -> The limits of the actual array. This is used because we are dealing
                with a recursive function.
*/

int tree[SIZE];

void build_tree(vector<int> A, int node, int a, int b) {
    if (a == b) { // We get to a simple element
        tree[node] = A[a]; // This node stores the only value
    }
    else {
        int leftChild, rightChild, middle;
        leftChild = 2*node;
        rightChild = 2*node+1; // Or leftChild+1
        middle = (a+b) / 2;
        build_tree(A, leftChild, a, middle); // Recursively build the tree in the left child
        build_tree(A, rightChild, middle+1, b); // Recursively build the tree in the right child

        tree[node] = max(tree[leftChild], tree[rightChild]); // The Value of the actual node, 
                                                            //is the max of both of the children.
    }
}

Struttura query

int query(int node, int a, int b, int p, int q) {
    if (b < p || a > q) // The actual range is outside this range
        return -INF; // Return a negative big number. Can you figure out why?
    else if (p >= a && b >= q) // Query inside the range
        return tree[node];
    int l, r, m;
    l = 2*node;
    r = l+1;
    m = (a+b) / 2;
    return max(query(l, a, m, p, q), query(r, m+1, b, p, q)); // Return the max of querying both children.
}

Se hai bisogno di ulteriori spiegazioni, fammelo sapere.

BTW, Segment Tree supporta anche l'aggiornamento di un singolo elemento o di un intervallo di elementi in O (log n)

Le soluzioni basate su albero ad albero binario / segmento sono davvero rivolte nella giusta direzione. Si potrebbe obiettare che richiedono molta memoria extra, comunque. Esistono due soluzioni a questi problemi:

1. Utilizza una struttura dati implicita invece di un albero binario
2. Usa un albero M-ary invece di un albero binario

Il primo punto è che poiché l'albero è altamente strutturato, è possibile utilizzare una struttura ad heap per definire implicitamente l'albero piuttosto che rappresentare l'albero con nodi, puntatori sinistro e destro, intervalli ecc. Ciò consente di risparmiare un sacco di memoria con essenzialmente nessun impatto sulle prestazioni: è necessario eseguire un po 'più di aritmetica del puntatore.

Il secondo punto è che, a costo di un po 'più di lavoro durante la valutazione, è possibile utilizzare un albero M-ary piuttosto che un albero binario. Ad esempio se si utilizza un albero 3-ary si calcola il massimo di 3 elementi alla volta, quindi 9 elementi alla volta, quindi 27, ecc. La memoria aggiuntiva richiesta è quindi N / (M-1) - è possibile dimostrare usando la formula della serie geometrica. Se si sceglie M = 11, ad esempio, sarà necessario 1/10 della memorizzazione del metodo dell'albero binario.

Puoi verificare che queste implementazioni ingenue e ottimizzate in Python diano gli stessi risultati:

class RangeQuerier(object):
    #The naive way
    def __init__(self):
        pass

    def set_array(self,arr):
        #Set, and preprocess
        self.arr = arr

    def query(self,l,r):
        try:
            return max(self.arr[l:r])
        except ValueError:
            return None

vs.

class RangeQuerierMultiLevel(object):
    def __init__(self):
        self.arrs = []
        self.sub_factor = 3
        self.len_ = 0

    def set_array(self,arr):
        #Set, and preprocess
        tgt = arr
        self.len_ = len(tgt)
        self.arrs.append(arr)
        while len(tgt) > 1:
            tgt = self.maxify_one_array(tgt)
            self.arrs.append(tgt)

    def maxify_one_array(self,arr):
        sub_arr = []
        themax = float('-inf')
        for i,el in enumerate(arr):
            themax = max(el,themax)
            if i % self.sub_factor == self.sub_factor - 1:
                sub_arr.append(themax)
                themax = float('-inf')
        return sub_arr

    def query(self,l,r,level=None):
        if level is None:
            level = len(self.arrs)-1

        if r <= l:
            return None

        int_size = self.sub_factor ** level 

        lhs,mid,rhs = (float('-inf'),float('-inf'),float('-inf'))

        #Check if there's an imperfect match on the left hand side
        if l % int_size != 0:
            lnew = int(ceil(l/float(int_size)))*int_size
            lhs = self.query(l,min(lnew,r),level-1)
            l = lnew
        #Check if there's an imperfect match on the right hand side
        if r % int_size != 0:
            rnew = int(floor(r/float(int_size)))*int_size
            rhs = self.query(max(rnew,l),r,level-1)
            r = rnew

        if r > l:
            #Handle the middle elements
            mid = max(self.arrs[level][l/int_size:r/int_size])
        return max(max(lhs,mid),rhs)

prova la struttura dei dati "ad albero del segmento"
ci sono 2 step
build_tree () O (n)
query (int min, intmax) O (nlogn)

link

modifica:

voi ragazzi non leggete il wiki che ho inviato!

questo algoritmo è:
- attraversi l'array 1 volta per costruire l'albero. O (n)
- Le successive 100000000+ volte che si desidera conoscere il massimo di qualsiasi parte dell'array, basta chiamare la funzione query. O (logn) per ogni query
- c ++ implementa qui geeksforgeeks.org/segment-tree-set-1-range-minimum-query/
vecchio algoritmo è:
ogni query, basta attraversare l'area selezionata e trovare.

quindi, se vuoi usare questo algoritmo per elaborare una volta, OK, è più lento del vecchio modo. ma se elaborerai un numero enorme di query (miliardi), sarà molto efficiente puoi generare un file di testo come questo, per test

riga 1: numero casuale 50000 da 0 a 1000000, diviso per "(spazio)" (è l'array)
riga 2: 2 numeri casuali da 1 a 50000, divisi per "(spazio)" (è la query)
...
line 200000: likes line 2, è anche una query casuale

questo è il problema dell'esempio, scusa ma questo è in vietnamita link
se lo risolvi alla vecchia maniera, non passi mai.