FENWICK TREE: le sue applicazioni

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?

Fai attenzione che il vettore di somme prefisse e il fenwick tree sono due cose diverse.
Il fenwick può fare due cose: modificare l’i-esimo elemento e restituire la somma dei primi i elementi, entrambe le operazioni hanno complessità logaritmica.
Quello che dobbiamo fare in partition è contare per ogni elemento il numero di elementi maggiori alla sua sinistra e il numero di elementi minori alla sua destra.
Prendiamo un problema più semplice: per ogni elemento contare quanti elementi minori ci sono alla sua sinistra. Si può fare facilmente con un fenwick. Per ogni elemento i, incremento l’i-esimo elemento del fenwick di 1 e per sapere quanti elementi minori ci sono alla sua sinistra basta contare quanti 1 ci sono nell’intervallo [0,i-1] ovvero la somma dei primi i-1 elementi del fenwick.
Prendiamo il caso di esempio: 2 6 1 5 7 8 9 4 3

  • incrementiamo di 1 l’elemento 2, contiamo la somma degli elementi da 0 a 1 che è 0
  • incrementiamo di 1 l’elemento 6, contiamo la somma degli elementi da 0 a 5 che è 1
  • incrementiamo di 1 l’elemento 1, contiamo la somma degli elementi da 0 a 0 che è 0
  • incrementiamo di 1 l’elemento 5, contiamo la somma degli elementi da 0 a 4 che è 2

e continuiamo fino alla fine.
Ovviamente devi riadattare la soluzione al problema ma una volta che hai capito come funziona il fenwick non è troppo difficile.

Se ancora non hai capito bene segui il consiglio di @aldo.carrolo.

Comunque come ho già detto prima c’è una soluzione molto più semplice da capire e da implementare per partition.

2 Mi Piace

grazie mille, ho capito la soluzione di partition con il fenwick e ho guardato il video consigliato. Prima hai detto che esiste una soluzione che fa uso di strutture dati della STL, a quale struttura ti riferivi?

Mi riferivo agli order statistic tree.
Torniamo al problema di prima: sapere quanti elementi più piccoli ci sono alla sua sinistra, il problema diventa più semplice se gli elementi sono ordinati, infatti basta solo sapere il suo indice.

2 Mi Piace

Piccola nota: è applicabile in tutti i casi di operatori “cumulabili”, cioè che dispongono di proprietà associativa. Ad esempio, è possibile concepire il Fenwick per fare prodotti anziché somme. L’unica cosa è che diventa più ostico capire il concetto di update.

Piccola nota 2: esiste SPOJ. Get fun

Non è vero.
Innanzitutto le Query su intervalli del fenwick sono composte di due Query prefissa su inizio e fine della sequenza da interrogare: è richiesta l’invertibilità dell’operazione.
Se invece ci limitiamo a fare Query su prefissi (esempio RMQ) negli update possiamo soltanto decrementare gli elementi. Quindi non basta che un opera sia associabile per poter usare il fenwick, ci sono molte limitazioni, ed inoltre per fare Query su intervalli occorre l’invertibilità.

1 Mi Piace

Quello che hai detto è vero, però utilizzando due Fenwick in modo furbo è possibile gestire RMQ e point update in O(logN) :wink:

Mi potresti dire come fai?

La spiegazione dettagliata la trovi qui, non dovrebbe essere troppo diffiicile capire come implementarlo ma nel caso posso condividere la mia implementazione (in ogni caso non penso possa essere particolarmente utile).

L’idea è quella che ogni indice del BIT mantiene l’informazione per un certo intervallo e che qualsiasi intervallo [L, R] può essere visto come l’unione di al più O(logN) di questi nodi - se consideriamo anche un ulteriore BIT costruito in modo analogo sull’array “reversato”.

L’unica difficoltà è capire come scegliere questi nodi - per capire come e perché penso convenga leggere per intero il paper linkato :slight_smile: