FENWICK TREE: le sue applicazioni

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

Si, ho cercato di seguire alla lettera questi[quote=“frakkiobello, post:17, topic:4480”]
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.
[/quote]

ho difficoltà a capire questa parte, dopo aver costruito il vettore di somme prefisse cosa devo fare?