Zadanie jedynki

Mam takie zadanie, ale kompletnie nie wiem jak je ugryźć i jak poradzić sobie z tym dodawaniem binarnym:

Mamy dany ciąg n liczb naturalnych a=a1,a2,…,an. Twoim zadaniem jest wyznaczenie liczby jedynek w zapisie binarnym każdej z sum ∑i=1k2ai dla k=1,2,…,n
Wejście

W pierwszym wierszu znajduje się liczba całkowita n ( 1≤n≤500000 ) - liczba elementów ciągu. W drugim wierszu znajduje się n liczb całkowitych ai ( 0≤ai≤500000 ) pooddzielanych pojedynczymi odstępami.

Wyjście

Twój program powinien wypisać n liczb całkowitych - k-ty wiersz powinien zawierać liczbę jedynek w rozwinięciu binarnym odpowiedniej sumy k potęg dwójki.

Przykład

Dla danych wejściowych:
4
0 1 2 1
poprawnym wynikiem jest:
1
2
3
2

Wyjaśnienie do przykładu: szukane sumy to kolejno: 1, 3, 7, 9.
Za wszelkie wskazówki byłbym wdzięczny :)

Musisz przekształcić ciąg danych wejściowych, tak aby miały różne wartości (*).
Korzystasz z przemienności dodawania, oraz faktu że 2^a + 2^a = 2^(a+1).
Stąd dane wejściowe
0 1 2 5 2 3 2 7 3 = 0 1 2 2 2 3 3 5 7 = 0 1 2 3 3 3 5 7 = 0 1 2 3 4 5 7
są tożsame i generują takie same wyniki.

(*) dla ciągu składającego się z różnych wartości - liczba jedynek sumy potęg dwójek jest równa ilości jego elementów.

Czy konieczne jest użycie tablicy?

Raczej std::vector, i std::map, mapa do częstotliwości występowania liczb.

To musiałbym poczytać jak dokładnie to działa bo pierwszy raz sie z czymś takim spotykam

To podstawowe struktury w STL - u, Poczytaj dokumentację.