CQXYM's blog

Binary Search Based on Fenwick Tree
By CQXYM, 5 years ago, In English

Hello!

You may have met these kinds of problems that require you to calculate the prefix sum with modifying, and you can use a fenwick tree SUM in order to solve it. When you want to lower_bound on it, you can reference this way as follows: You wonder the minimum index in the array SUM[L~R] satisfied SUM[index]≥K.

Set l=0, r=R, mid=R three pointers as the left, right, middle.
If log2(r-l) is a positive interger, mid = (r - l)/2, or mid = pow(2, ceil(r-l) ) + l.
If SUM[mid]≥K, r = mid, or l = mid.
Continue to do it if l < mid < r.
In the end, index = mid.

The Picture

For this algorithm, it's not difficult to prove that the time complexity is about log2(R). You can understand it better with the help of this picture. And also you can solve such problems with a segment tree If there is something wrong with my algorithm, please tell me. Thanks.

  • Vote: I like it
  • -31
  • Vote: I do not like it

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

I can't see the picture. Is the link ok?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm so sorry, but now it is fixed.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In addition, if the final mid≤L, index=L, or index=mid

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

I can't understand what you are explaining. Maybe just because I'm too vegtable.

→ Reply