Ciao,
stavo facendo halloween (un problema semplice) e lo ho risolto con una soluzione banale ma non è questo il punto.
Il punto è che vorrei far diventare il mio codice più veloce ed efficiente e ragionando avevo pensato all’uso di un fenwick tree e la domanda è la seguente: è possibile usarlo per calcolare le somme dei vari intervalli così da rendere molto più veloce il confronto con m(le caramelle totali) rispetto a prima.
Se l’idea è corretta mi dareste qualche dritta sull’implementazione perchè ho usato il fenwick tree pochissime volte e solo in problemi fatti apposta per applicarlo.
Se l’idea invece è totalmente sbagliata potreste mettermi sulla retta via?
Grazie in anticipo
Il fenwick tree puo’ essere usato per fare somme di range qualsiasi in O(log(n)) quando servono gli update, che vengono anche essi fatti in O(log(n)).
In questo problema pero’ non servono le somme su range qualsiasi e non servono gli update.
se usassi un fenwick tree aumenteresti la complessita’ a O(n \cdot log(n)).
Per avere somme di range qualsiasi senza le update in O(1) con O(n) precalcolo puoi usare somme prefisse.
In questo problema pero’ ti basta solo sapere la somma totale e quella per ogni prefisso, che ti puoi quindi tenere aggiornata mentre iteri gli elementi.
Questo dimostra che devo rivedermelo meglio, comunque sai qualche problema fattibile con il fenwick tree abbastanza semplice?
Beh ci sono fenwick1 e fenwick2 
(il più semplice secondo me è il 2, anche se dal nome non sembrerebbe 
)
Grazie mille , vedo cosa riesco a fare
Lo puoi usare anche in tutti questi esercizi, in alcuni l’uso non è intuitivo ed in altri non è la soluzione ottimale
Ok grazie mille in questi giorni provo in caso chiedo