Help with BITs

Revision en1, by yesbutno1685, 2020-09-15 07:20:01

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English yesbutno1685 2020-09-15 07:20:40 12 Tiny change: ' that are below a certain' -> ' that are less than a certain'
en1 English yesbutno1685 2020-09-15 07:20:01 709 Initial revision (published)