Array partition 90/100

[bortoz]

Ti consiglio di guardare questo post:

FENWICK TREE: le sue applicazioni

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 nume…

Comunque se hai poca dimestichezza con gli alberi binari, esiste una soluzione molto più intuitiva che fa uso di una struttura dati della STL.