# Fenwick2 in meno di O(N^2)

**URL:** <https://forum.olinfo.it/t/fenwick2-in-meno-di-o-n-2/3839>\
**Category:** Aiuto\
**Created:** [20 Agosto 2014, 4:35pm UTC](https://forum.olinfo.it/t/fenwick2-in-meno-di-o-n-2/3839 "2014-08-20T16:35:31Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\
**Post date:** [20 Agosto 2014, 4:35pm UTC](https://forum.olinfo.it/t/fenwick2-in-meno-di-o-n-2/3839/1 "2014-08-20T16:35:31Z")

</div>

Ieri sera ho letto troppo frettolosamente il problema “All Possible Incresing Subsequences” e ho considerato solo il caso in cui la sequenza è non-decrescente, tuttavia dopo quel 10/100 ho capito che non era così (ma dai? °L°).

  

Quindi volevo rimediare a quell’inguardabile punteggio ma l’unica soluzione che ho in mente ha complessità O(N^2).

Ho la mia sequenza A e un secondo array S dove S[i] rappresenta il numero di sottosequenze crescenti che terminano con A[i].  
Osservando poi che S[i] lo posso ottenere dalla somma degli S[j] per (0\<=j\<i && S[j]\<S[i]) +1, allora mi basta costruire S partendo dal caso base S[0]=1.

La soluzione del problema sarà la somma di tutti i valori di S.

  

Il problema quindi è: come faccio a farlo in modo efficiente?

  

Il Fenwick Tree ho letto cos’è ma ci ho capito ben poco, ma questo non è il grosso problema (alla fine basta avere la pazienza di mettersi a fare due disegnini).

Quello che è più grave è che non ho la minima idea di dove applicarlo in questo problema (oltre a sommare i valori di S, a che mi dovrebbe servire?)

---

<div class="post-metadata">

**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:** [20 Agosto 2014, 7:49pm UTC](https://forum.olinfo.it/t/fenwick2-in-meno-di-o-n-2/3839/2 "2014-08-20T19:49:39Z")

</div>

> Ho la mia sequenza A e un secondo array S dove S[i] rappresenta il numero di sottosequenze crescenti che terminano con A[i].
> 
> VashTheStampede

Prova a cambiare in: «S[i] rappresenta il numero di sottosequenze crescenti che terminano con i».
  

> Osservando poi che S[i] lo posso ottenere dalla somma degli S[j] per (0\<=j\<i && S[j]\<S[i]) +1
> 
> VashTheStampede

Tra l'altro qui intendevi A[j]\<A[i] vero?

---

<div class="post-metadata">

**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\
**Post date:** [20 Agosto 2014, 9:38pm UTC](https://forum.olinfo.it/t/fenwick2-in-meno-di-o-n-2/3839/3 "2014-08-20T21:38:44Z")

</div>

No ok, mi sto perdendo: cosa significa che terminano con i?

Dato che i valori in input il problema non li specifica, dovrei prepararmi un array S da 2^31-1 no?  
Ma questo non è fisicamente possibile…

Cosa sto fraintendendo? :0

  

Comunque si intendevo A[j]\<A[i] 🙂

---

<div class="post-metadata">

**Author:** ![Mazzetto](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/87869e/32.png) [@Mazzetto](https://forum.olinfo.it/u/Mazzetto)\
**Post date:** [20 Agosto 2014, 9:56pm UTC](https://forum.olinfo.it/t/fenwick2-in-meno-di-o-n-2/3839/4 "2014-08-20T21:56:50Z")

</div>

In realtà i valori possibili diversi che tu puoi avere sono al massimo N. Che la sequenza sia 1 2 3 o 10 20 30 non cambia la risposta. Quindi i tuoi N valori della sequenza li puoi rimappare in numeri da 1 a N.

---

<div class="post-metadata">

**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\
**Post date:** [21 Agosto 2014, 7:28pm UTC](https://forum.olinfo.it/t/fenwick2-in-meno-di-o-n-2/3839/5 "2014-08-21T19:28:43Z")

</div>

Ok, forse ho capito.

Ho pure letto fino alla fine il “tutorial” sui Fenwick Tree su Topcoder e devo dire che non sono difficili (l’altra volta ho letto solo le prime righe e trovavo tutto molto contorto, ma devo ammettere che poi la strada è tutta in discesa).

  

Insomma mi basta creare un ulteriore array B=sort(A) e mano a mano che “percorro” A cerco in B (tramite un Fenwick) quanti valori minori di A[i] ho già “visitato”. (o meglio, la somma delle soluzioni che hanno prodotto)

  

E’ corretto così, no?

Devo solo fare attenzione a quando possiedo in B due o più valori uguali.

  

EDIT: ok, risolto, grazie mille per l’aiuto! 🙂