algorithm - 二叉索引树：如何找到具有给定累积频率的索引

Question

我试图在二进制索引树（BIT）中找到具有给定累积频率的索引。

我能够在 O(log(n)*log(n)) 中解决这个问题，方法是借助二进制搜索和计算任何索引处的累积频率的函数来实现它。

但我正在考虑在 O(log(n)) 中解决这个问题。

所以请帮忙。

Answer 1

这个来自topcoder 教程的算法展示了如何在 O(logn) 中找到具有给定累积频率的最大索引：

寻找具有给定 cumultive 频率的索引的最简单最简单的解决方案就是简单地遍历所有索引，计算累积频率，并检查它是否等于给定值。在负频率的情况下，它是唯一的解决方案。但是，如果我们的树中只有非负频率（这意味着更大索引的累积频率不会更小），我们可以计算出对数算法，这是对二分搜索的修改。我们遍历所有位（从最高位开始），制作索引，比较当前索引和给定值的累积频率，并根据结果取区间的下半部分或上半部分（就像在二进制搜索中一样）。

// if in tree exists more than one index with a same
// cumulative frequency, this procedure will return 
// the greatest one
int findG(int cumFre){
    int idx = 0;

    while ((bitMask != 0) && (idx < MaxVal)){
        int tIdx = idx + bitMask;
        if (cumFre >= tree[tIdx]){ 
            // if current cumulative frequency is equal to cumFre, 
            // we are still looking for higher index (if exists)
            idx = tIdx;
            cumFre -= tree[tIdx];
        }
        bitMask >>= 1;
    }
    if (cumFre != 0)
        return -1;
    else
        return idx;
}