How to find which position have prefix sum M in BIT?

Question

Suppose I have created a Binary Indexed Tree with prefix sum of length N. The main array contains only 0s and 1s. Now I want to find which index has a prefix sum M(That means have exactly M 1s).

Like my array is a[]={1,0,0,1,1};

prefix-sum would look like {1,1,1,2,3};

now 3rd index(0 based) has prefix sum of 2.

How can i find this index with BIT?

Thanks in advance.

Answer 1

Why can't you do binary search for that index ? It will take O(log n * log n) time. Here is a simple implementation -

int findIndex(int sum) {
    int l = 1, r = n;
    while(l <= r) {
        int mid = l + r >> 1;
        int This = read(mid);
        if(This == sum) return mid; 
        else if(This < sum) l = mid+1; 
        else r = mid-1;
    } return -1;
} 

I used the read(x) function. That should return the sum of interval [1,x] in O(log n) time. The overall complexity will be O(log^2 n).
Hope it helps.