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

Question

假设我创建了一个二叉索引树，其前缀和的长度为 N。主数组仅包含 0 和 1。现在我想找到哪个索引的前缀和为 M(这意味着恰好有 M 1)。

比如我的数组是 a[]={1,0,0,1,1};

前缀和看起来像 {1,1,1,2,3};

现在第 3 个索引(基于 0)的前缀和为 2。

如何用 BIT 找到这个索引？

提前致谢。

Answer 1

为什么不能对该索引进行二分查找？这将花费 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) 函数。那应该在 O(log n) 时间内返回区间 [1,x] 的总和。整体复杂度为 O(log^2 n)。
希望能帮助到你。