Witam!
Mam taki problem algorytmiczny:
Mam jakiś ciąg liczb, dajmy na to 1 4 5 2 6 7 3. Każdy element występuje raz i mamy tu dokładnie n elementów od 1 do n. Chciałbym dla każdego elementu tego ciągu, idąc po kolei, tzn. najpierw element o wartości 1, potem 2 itd, zobaczyć ile na lewo od tego elementu jest liczb od niego większych. Po takiej operacji skreślam ten element - nadaję mu wartość 0. Mała wizualizacja:
Pierwszy element: 1 na pozycji 1. Ile jest na lewo większych? 0. Zatem wynik zwiększam o 0. Skreślam jedynkę, odtąd tu jest 0.
Drugi element: 2 na pozycji 4. Ile jest na lewo większych? 2. Zatem wynik zwiększam o 2. Skreślam tę dwójkę, odtąd tu jest 0.
Trzeci element: 3 na pozycji 7. Ile jest na lewo większych? 4. Zatem wynik zwiększam o 4. Skreślam tę trójkę, odtąd tu jest 0.
Robię tak dla wszystkich elementów. Chciałbym uzyskać złożoność O(n log n), tzn. pojedynczą operację sprawdzenia ile na lewo większych chciałbym zrobić w czasie log n.
Jak można takie coś zrealizować? Długo myślałem nad jakimś drzewem, chociażby potęgowym, ale tam trzymamy sumę elementów i za nic nie dałem rady tego przekształcić żeby działało jak chcę i wyszukiwało tylko elementy większe od danego.
Pomoże ktoś? Bardzo proszę!