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 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.
Per ottenere i numeri minori di un determinato elemento alla sua destra puoi fare un ragionamento analogo scorrendo da destra.
Dario