FENWICK TREE: le sue applicazioni

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

1 Mi Piace

mi sapresti consigliare una buona guida/pagina riguaradante il segment tree.

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. :wink:

2 Mi Piace

Grazie per il consiglio.

Sfrutto questo topic per chiedere come potrei applicare un fenwick tree sull’esercizio partition.

In questo topic (già linkato in un post precedente) trovi spiegato come applicare il fenwick tree all’esercizio partition :wink:

1 Mi Piace

Ho visto quel topic ma non ho ancora compreso bene come applicare il fenwick tree e per quale motivo viene applicato.

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.

Dario

1 Mi Piace

sia fenwick1 che fenwick2 possono essere fatti con dei segment tree

Quindi riferendoci ad array partition e supponendo di avere un array di questo tipo:

N=10
4 2 6 1 3 8 7 9 0 5
Come prosego? Devo tenermi un altro array dove metto gli 0 e gli 1?

Perché ho trovato questo: https://github.com/gautamkmr/Fenwick/blob/master/fenwick.cpp
Ma non capisco a cosa mi serve l’& .

Se intendi i & (-i), è un modo di ottenere il valore dell’ultimo bit di un numero i

1 Mi Piace

Ma a cosa mi serve ottenere il valore dell ultimo bit? Come nell esempio che ho proposto cosa ne faccio?

Ottenere il valore dell’ultimo bit non serve nel problema in sé, ma serve per far funzionare il Fenwick :stuck_out_tongue:
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.

Ti consiglio di dare una letta qui

Avevo gia provato a leggerlo qualche mese fa quando avevo fatto 90/100 in array partition ma non avevo capito molto :smile: 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

Confermo di non avere capito nulla :sweat_smile:.
Se c’è qualche buon’anima con un po di pazienza che riesce a spiegarmi di cosa si tratta mi farebbe un favorone.

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 … :joy:
VIDEO

1 Mi Piace

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

perchè io ho provato ma piu che andare in loop non ho fatto :smile:
codice: https://pastebin.com/Ykd6g8q5

Anche se comunque credo di avere fatto progressi :smile: !!!

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;
}
1 Mi Piace

Ho sistemato come hai detto ma ho ottenuto solo 1 subtask corretto e nell’ultimo ce un crea un “errore di memoria”

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:

 if(A[i]<i+1)
        fenwick[i]=1;

btw, il problema è partition giusto?

1 Mi Piace