# Halloween fenwick tree? **URL:** \ **Category:** Algoritmi\ **Created:** [8 Aprile 2020, 11:08am UTC](https://forum.olinfo.it/t/halloween-fenwick-tree/6136 "2020-04-08T11:08:33Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![jeppo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/4491bb/32.png) [@jeppo](https://forum.olinfo.it/u/jeppo)\ **Post date:** [8 Aprile 2020, 11:08am UTC](https://forum.olinfo.it/t/halloween-fenwick-tree/6136/1 "2020-04-08T11:08:33Z")
Ciao, stavo facendo [halloween](https://training.olinfo.it/#/task/ois_halloween/stats) (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 ---
**Author:** ![MyK\_00L](https://forum.olinfo.it/user_avatar/forum.olinfo.it/myk_00l/32/3000_2.png) [@MyK\_00L](https://forum.olinfo.it/u/MyK_00L)\ **Post date:** [8 Aprile 2020, 11:27am UTC](https://forum.olinfo.it/t/halloween-fenwick-tree/6136/2 "2020-04-08T11:27:46Z")
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. ---
**Author:** ![jeppo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/4491bb/32.png) [@jeppo](https://forum.olinfo.it/u/jeppo)\ **Post date:** [8 Aprile 2020, 3:40pm UTC](https://forum.olinfo.it/t/halloween-fenwick-tree/6136/3 "2020-04-08T15:40:41Z")
Questo dimostra che devo rivedermelo meglio, comunque sai qualche problema fattibile con il fenwick tree abbastanza semplice? ---
**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\ **Post date:** [8 Aprile 2020, 8:57pm UTC](https://forum.olinfo.it/t/halloween-fenwick-tree/6136/4 "2020-04-08T20:57:13Z")
Beh ci sono [fenwick1](https://training.olinfo.it/#/task/fenwick1/statement) e [fenwick2](https://training.olinfo.it/#/task/fenwick2/statement) 😄 (il più semplice secondo me è il 2, anche se dal nome non sembrerebbe 😆) ---
**Author:** ![jeppo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/4491bb/32.png) [@jeppo](https://forum.olinfo.it/u/jeppo)\ **Post date:** [9 Aprile 2020, 9:14am UTC](https://forum.olinfo.it/t/halloween-fenwick-tree/6136/5 "2020-04-09T09:14:35Z")
Grazie mille , vedo cosa riesco a fare ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [9 Aprile 2020, 3:19pm UTC](https://forum.olinfo.it/t/halloween-fenwick-tree/6136/6 "2020-04-09T15:19:40Z")
Lo puoi usare anche in tutti questi esercizi, in alcuni l’uso non è intuitivo ed in altri non è la soluzione ottimale - [Array Partition (partition)](https://training.olinfo.it/#/task/ois_partition/statement) - [Ordinamento a paletta](https://training.olinfo.it/#/task/paletta/statement) - [Cottarelle in classe (cotte](https://training.olinfo.it/#/task/cotte/statement) - [Piano degli studi (pianostudi)](https://training.olinfo.it/#/task/pianostudi/statement) - [Tournament Planning (poker)](https://training.olinfo.it/#/task/ois_poker/statement) - [Musical Notes (scmax)](https://training.olinfo.it/#/task/ois_scmax/statement) ---
**Author:** ![jeppo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/4491bb/32.png) [@jeppo](https://forum.olinfo.it/u/jeppo)\ **Post date:** [9 Aprile 2020, 4:59pm UTC](https://forum.olinfo.it/t/halloween-fenwick-tree/6136/7 "2020-04-09T16:59:17Z")
Ok grazie mille in questi giorni provo in caso chiedo