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.
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
Read this Code may help, Sadly the website you provided does not support C++17.