yesbutno1685's blog

Help with BITs
By yesbutno1685, history, 4 years ago, In English

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 less than 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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Basically, you are trying to create an indexed set

I'll describe how to do it with a segment tree because I am unfamiliar with BITs. To insert an element,x, into the set, do segtree.update(x,1). To get the index of an element,x, do segtree.query(0,x).

The BIT solution is almost the same

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Read this Code may help, Sadly the website you provided does not support C++17.

→ Reply