Quale struttura dati per trovare il numero di elementi in un determinato intervallo in O (log n) tempo?

Question

Sto risolvendo un problema e mi sono reso conto che ho bisogno di una struttura dati con le seguenti proprietà, ma non riesco a trovarne una anche dopo poche ore di googling. Credo che la libreria STL sia troppo ricca per non avere questo, chiedendo quindi qui.

1. inserire qualsiasi elemento (dovrebbe essere in grado di contenere quelle ripetitiva) in O(log(n)) tempo
2. Rimuovere un elemento in O(log(n)) tempo pure.
3. Se voglio query per il numero di elemenes nell'intervallo [a, b], ho dovrei ottenere che contano in O(log(n)) volta ..

Se dovessi scrivere da zero, per la parte 1 e 2, vorrei usare uno set o e vorrei modificare il loro metodo find() (che viene eseguito nel tempo) per restituire indici invece di iteratori in modo che io possa fare abs(find(a)-find(b)) così ottengo il conteggio degli elementi nel tempo di log (N) . Ma sfortunatamente per me, find() ritorna e iteratore.

Ho esaminato multiset() e non è stato possibile soddisfare il requisito 3 nel tempo O(log(n)). Ci vuole O(n).

Eventuali suggerimenti per farlo facilmente?

Answer 1

Sebbene non faccia parte di STL, è possibile utilizzare Policy-Based Data Structures che fanno parte delle estensioni di gcc; In particolare è possibile inizializzare uno order statistics tree come di seguito. Il codice viene compilato con gcc senza librerie esterne:

#include<iostream> 
#include<ext/pb_ds/assoc_container.hpp> 
#include<ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds; 
using namespace std; 

int main() 
{ 
    tree<int,   /* key    */ 
     null_type, /* mapped    */ 
     less<int>, /* compare function */ 
     rb_tree_tag, /* red-black tree tag */ 
     tree_order_statistics_node_update> tr; 

    for(int i = 0; i < 20; ++i) 
     tr.insert(i); 

    /* number of elements in the range [3, 10) */ 
    cout << tr.order_of_key(10) - tr.order_of_key(3); 
} 

Answer 2

Anche se la libreria standard è davvero ben fornita, non penso che troverete qualcosa con questi requisiti particolari. Come hai notato, le strutture set-like restituiscono iteratori ad accesso non casuale - per fornire un accesso casuale (o qualche tipo di funzione di distanza, come richiesto) introdurrebbe una notevole complessità.

Si può essere in grado di raggiungere il tuo obiettivo attuando una skip list indicizzabile, che fornisce l'inserimento O (log (n)), la cancellazione, e la ricerca indicizzata, come descritto qui: https://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist

Una guida per l'attuazione può essere trovato qui: http://cg.scs.carleton.ca/~morin/teaching/5408/refs/p90b.pdf

Answer 3

Dovresti riuscire a farlo con un B-Tree standard o leggermente modificato.

In genere la maggior parte delle operazioni standard sono O (log (n)) per le implementazioni di B-Tree.

Answer 4

Le due strutture dati ovvie per questa attività sono la skip list (che Jack O'Reilly ha già citato) e qualche variante dell'albero statistica d'ordine (che Behzad menziona ma in realtà non spiega).

Un albero di statistiche dell'ordine memorizza un'ulteriore informazione in ciascun nodo. È possibile memorizzare una serie di cose diverse, ma quella che trovo più semplice da capire è se ogni nodo memorizza il numero di elementi nel suo sottoalbero sinistro.

Quando si inserisce, mentre si cammina lungo la struttura per memorizzare un elemento, si incrementa il conteggio ogni volta che si scende a sinistra nell'albero.Poiché stai solo modificando i nodi che avresti dovuto attraversare comunque, ciò non cambia l'inserimento di O(log N). Quando si riequilibra, è necessario regolare di conseguenza (ma, di nuovo, si modificano solo i conteggi nei nodi che si stanno già modificando quando si eseguono le rotazioni, quindi (di nuovo) non si influisce sulla complessità complessiva

Quando devi trovare una distanza tra un elemento e l'altro, trovi solo i due nodi, ognuno con complessità O (log N). Ottieni l'indice di ogni elemento nell'albero come lo trovi inizializzando un indice dal root, quindi aggiornarlo da lì (sottrarre il conteggio mentre si scende a sinistra, aggiungere mentre si scende a destra)

Answer 5

Non è certamente lo spazio più efficiente, fornendo O (3n), ma soddisfa i criteri di inserimento, rimozione e distanza elencati sopra. Il seguente utilizza un elenco collegato, una mappa e unordered_map.

L'elenco viene utilizzato per mantenere l'ordine. Normalmente l'inserimento in una lista in ordine è tempo lineare, ma con l'aiuto di una mappa di chiave per list_iterator, possiamo inserire in tempo costante. Il vantaggio di memorizzare i dati ordinati in una lista è che utilizza iteratori di accesso casuale che significa che è possibile ottenere un tempo costante std :: chiamata a distanza

La mappa viene utilizzata per ottenere un suggerimento sul punto in cui inserire un nodo nell'elenco . Ciò avviene creando una nuova voce di mappa per la chiave specificata, quindi decrementando l'iteratore di 1. Il valore di questo nuovo iteratore ci fornisce la posizione di inserimento appropriata nell'elenco collegato.

Il file non ordinato fornisce una (1) ricerca per gli iteratori di elenchi di accesso casuale, che ci consentono di ottenere una rimozione (logn) e il tempo di percorrenza.

class logn 
{ 
public: 
    using list_it = std::list<int>::iterator; 

    void insert(int i) 
    { 
     const bool first = list.empty(); 
     auto original_it = map.insert({i,list.end()}).first; // o(logn) 
     auto hint = original_it; 
     if (!first) 
      --hint; 
     umap[i] = list.insert(hint->second,i); // o(1) 
     original_it->second = umap[i]; 
    } 

    void remove(int i) 
    { 
     auto it = umap.find(i); // o(1) 
     list.erase(it->second); // o(1) 
     umap.erase(it);   // o(1) 
     map.erase(map.find(i)); // o(logn) 
    } 

    list_it get(int i) const 
    { 
     return umap.find(i)->second; 
    } 

    unsigned int distance(int lower, int upper) const 
    { 
     return std::distance(get(lower), get(upper)); 
    } 

private: 

    std::list<int> list; 
    std::unordered_map<int, list_it> umap; 
    std::map<int, list_it> map; 

};