3

假设我创建了一个前缀和长度为 N 的二叉索引树。主数组仅包含0s 和1s。现在我想找出哪个索引有一个前缀总和 M（这意味着正好有 M 1s）。

就像我的数组是a[]={1,0,0,1,1};

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

现在第 3 个索引（基于 0）的前缀总和为 2。

我怎样才能用 BIT 找到这个索引？

提前致谢。

4

2 回答 2

3

为什么不能对该索引进行二进制搜索？这需要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).
希望能帮助到你。

于 2017-04-05T16:03:12.277 回答
0

如果数组a[n]中的元素是非负的（并且前缀和数组p[n]是非递减的），您可以通过前缀和作为查询前缀和从BIT的索引来定位元素，这需要O（logn）时间。唯一的区别是您需要将在每个级别获得的前缀总和与输入进行比较，以决定随后需要搜索哪个子树——如果前缀总和小于您的输入，则继续搜索左子树；否则，搜索右子树；重复这个过程，直到到达一个汇总所需前缀和的节点，在这种情况下返回节点的索引。这个想法类似于二分搜索，因为前缀和自然地按 BIT 排序。如果 中有负值a[n]，则此方法将不起作用，因为在这种情况下不会对 BIT 中的前缀和进行排序。

于 2017-08-25T01:40:42.890 回答