Sto pensando di implementare un albero di Fenwick di dimensioni non fisse. Cioè, un albero di Fenwick che consente query di intervallo interleaving con l'aggiunta / rimozione di elementi.
Tutte le implementazioni e samples Ho visto finora sono gli alberi di Fenwick a dimensione fissa, in cui è noto il numero di elementi prima della preelaborazione delle frequenze. Usano una matrice di dimensioni fisse, quindi non è possibile aggiungere o rimuovere elementi dopo aver eseguito la pre-elaborazione. (Beh, è possibile, ma avrei bisogno di ricostruire la struttura).
Ho pensato di estendere TreeMap o forse AbstractMap , ma come TreeMap è in realtà un albero rosso-nero, non so come implementare la meccanica rosso-nero (in modo che l'albero rimanga bilanciato) senza perdere le somme cumulative dei nodi coinvolti nel processo di ribilanciamento.
Quindi ho pensato che forse avrei dovuto adottare un altro approccio: perché non estendere o adattare un semplice accesso casuale ArrayList e ricalcolare tutte le somme cumulative quando l'array sottostante viene ridimensionato? Questo naturalmente avrebbe un impatto ma, ehi, è esattamente ciò che fa HashMap .
Questo è il motivo per cui ho voluto chiedere prima qui, nel caso qualcuno l'abbia già fatto, e per verificare quale approccio pensi sia il migliore.