algorithm - 如何找到BIT中有前缀和M的位置？

假设我创建了一个前缀和长度为n的二叉索引树。主数组只包含0s和1s。现在我想找出哪个索引有前缀和m（也就是说正好有m1s）。
就像我的数组是a[]={1,0,0,1,1};
前缀和看起来像{1,1,1,2,3};
现在，第三个索引（基于0）的前缀和为2。
如何找到带位的索引？
提前谢谢。

最佳答案

为什么不能用二进制搜索那个索引？这需要O(log n * log n)时间。下面是一个简单的实现-

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;
}

我使用了read(x)函数。它应该返回[1,x]时间中的间隔O(log n)的和。总体复杂度为O(log^2 n)。
希望有帮助。