Блог пользователя yesbutno1685

Автор yesbutno1685, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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