[PS] 2010 Daejeon 4843 Sales

본 문제는 자신 앞에 자신보다 같거나 작은수의 개수를 모두 출력하는 문제이다.

주먹구구식으로 풀면 O(n^2) 시간에 풀 수 있지만

사실 이 문제는 BIT 문제이다(Binary Index Tree)

상향식으로 포문을 돌면서 현재 숫자를 BIT에 1을 Add 연산한다.

그리고 0부터 현재숫자까지의 합을 모두 구하면 O(nlogn) 시간에 답을 구할수 있다.