I was working on this USACO problem: http://usaco.org/index.php?page=viewproblem2&cpid=898, when I realized that I would need to use a BIT(Binary Indexed Tree) and find the number of values that are below a certain value x.

I was wondering how to find the number of numbers that are below x using a binary indexed tree. I searched online and couldn't get a good answer. The closest I got to a "decent" answer was a stack-overflow with a promising title, but then the only response was not really helpful.

I hope the people here can provided some useful and helpful responses to help me out with this problem.

Thanks in advance.