In questi giorni ho studiato il fenwick tree per la sua applicazione in alcuni problemi. Ho creato questo post per chiedere come effettivamente si può applicare questa struttura dati complessa in “problemi reali”.
P.S.: l’unico utilizzo che posso fare di ciò è la somma dei primi N elementi
Finora ho avuto una pessima esperienza con il fenwick. In particolare, alle nazionali non sono riuscito a fare classifica semplicemente perché come struttura dati ho puntato tutto proprio sul fenwick mentre la soluzione prevede anche di gestire lo scambio di posizioni, che il fenwick non gestisce.
Buona parte degli esercizi che richiede fenwick ammette come soluzione pure i segment tree, e molto spesso questi ultimi sono la soluzione cercata. Finora ho trovato questi esercizi che richiedono il Fenwick Three: partition (puoi leggere il thread associato per sapere perché) fenwick, che richiede un’applicazione speciale di Fenwick caffe e forse altavelocita, anche se non l’ho ancora fatto
Potresti seguire su youtube il tizio tushar roy, ha moltissimi video tra i quali ce ne sono 3 dedicati al segment tree. È bravissimo a spiegare, però è in inglese, un inglese abbastanza pulito e capibile.
Quello che vuoi ottenere è sapere, in tempo logaritmico, per un singolo elemento quanti elementi maggiori di lui ci sono alla sua sinistra e poi quanti ce ne sono minori alla sua destra. Il problema diventa un po’ più semplice se lavori su un solo lato alla volta. Ad esempio supponiamo di voler sapere per ogni elemento quanti elementi maggiori di lui ci sono alla sua sinistra.
Per farlo, possiamo mantenere un fenwick indicizzato da 0 a N - 1 dove in ogni posizione i metteremo un uno se il numero i è presente a sinistra e uno zero altrimenti. Per sapere quanti numeri da considerare ci sono alla sinistra di un elemento e ci basta sapere la somma dei valori del fenwick nell’intervallo [0; e - 1] e sottrarre questo valore al numero di numeri inseriti nel fenwick.
Se scorriamo da sinistra verso destra possiamo prima ottenere il risultato per l’elemento che stiamo considerando e poi inserire un uno nel fenwick nella posizione data dall’elemento stesso garantendo la correttezza della soluzione.
Per ottenere i numeri minori di un determinato elemento alla sua destra puoi fare un ragionamento analogo scorrendo da destra.
Ottenere il valore dell’ultimo bit non serve nel problema in sé, ma serve per far funzionare il Fenwick
L’idea è simile al Segment Tree dove ci sono dei nodi che salvano le informazioni su determinati Range, nel Fenwick questi Range vengono gestiti da “bucket” che sono lunghi una potenza di 2.
Avevo gia provato a leggerlo qualche mese fa quando avevo fatto 90/100 in array partition ma non avevo capito molto stasera provo a dagli una lettura, e volevo anche informarmi sul segment tree che non so minimamente cosa sia ma da quello che leggo sul forum sembra molto utile ed efficente
A spiegare faccio schifo però ti consiglio questo video tutorial (da cui ho imparato la seguente struttura) che mi ha aperto gli occhi ad un mondo pieno di strutture … VIDEO
Dimmi se ho capito bene: prima di tutto in un fenwick inserisco un 1 se l elemento fra quelli che mi da lui in posizione 1 è minore di i, quindi se per esempio l’elemento 1 è in posizione 0 altrimenti inserisco 0. poi mi basta fare la somma dei valori che sono presenti fino a quel momento e toglierli al numero di valori presenti, poi basta aggiornarlo inserendo un 1 in posizione i
Sbaglio o in ottienisomma rendi il fenwick 1-based (incrementi index) e in aggiorna no? Dovresti incrementarlo anche all’inizio di aggiorna e rendere la condizione di uscita del while index <= N
Se ti può servire, questa è un’implementazione compatta di un fenwick:
int N;
int ft[500001];
void ft_add(int p, int v)
{
for(++p; p <= N; p += p & -p)
ft[p] += v;
}
int ft_query(int p)
{
int res = 0;
for(++p; p > 0; p -= p & -p)
res += ft[p];
return res;
}
Porta tutte le dichiarazioni degli array grandi (A, fenwick, valorimaggiori, …) fuori dal main e dichiarali staticamente. Così eviti di allocare tutta quella memoria sullo stack ma la allochi sull’heap.
Poi non ho capito questa parte del codice cosa dovrebbe fare: