3

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.

4
  • Why do you want to use BIT to find it, instead of finding it as well when you constructing the prefix sum array?
    – shole
    Apr 5, 2017 at 6:42
  • @shole cause i also need to update the main array
    – madMDT
    Apr 5, 2017 at 8:30
  • just do normal BIT operation, and use binary search to find the index?
    – shole
    Apr 5, 2017 at 8:34
  • can you specify the process of finding the index as an answer please?
    – madMDT
    Apr 5, 2017 at 8:37

2 Answers 2

3

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.

0

If elements in array a[n] is non-negative (and the prefix sum array p[n]is non-decreasing), you can locate an element by prefix sum as query prefix sum by index from BIT, which takes O(logn) time. The only difference is that you need to compare the prefix sum you get at each level to your input to decide which subtree you need to search subsequently -- if the prefix sum is smaller than your input, continue searching the left subtree; otherwise, search the right subtree; repeat this process until reach a node that sums up the desired prefix sum, in which case return the index of the node. The idea is analogous to binary search because the prefix sums are naturally sorted in BIT. If there are negative values in a[n], this method won't work since prefix sums in BIT won't be sorted in this case.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.