0

假设我有一个具有非负值的 BIT(Fenwick Tree)，我想在 O(logN) 中找到给定累积频率的最小索引。

现在，我可以这样做 O(log^2(N)) 像这样。

int l = 0, r = n;
while(l < r) {
    int midd = l + (r-l)/2;
    if (get_sum(BIT, midd+1) < given_sum)
        l = midd+1;
    else
        r = midd;
}
return midd + 1;

我知道我们可以在 O(logN) 中找到任何索引或最大索引，如此处所述，因此也希望找到具有相同时间复杂度的最低索引。树的实现方式是一种常见的方式。

vector<int> BIT(n+1);
void update(vector<int> &BIT, int idx, int delta){
    for(int i = idx; i < BIT.size(); i +=(i&-i))
        BIT[i] += delta;
}
int get_sum(vector<int>& BIT, int idx){
    int sum = 0;
    for(int i = idx; i > 0; i-=(i&-i))
        sum += BIT[i];
    return sum;
}

希望得到您的帮助：）

4

1 回答 1

1

这是我对lower_bound具有基于 0 的索引的 Fenwick 树的 -like 函数的实现：

std::size_t lower_bound(int value) const
{
    std::size_t index = 0;
    for (auto mask = msb_size_mask(); mask != 0; mask >>= 1)
        if (const auto k = mask + index - 1; k < data.size() && data[k] < value)
        {
            value -= data[k];
            index += mask;
        }

    return index;
}

data是底层std::vector<int>。辅助函数msb_size_mask()返回 Fenwick 树的最小大小，使得底层二叉树是完美的，即它返回2^kif data.size()is in the range (2^{k-1}, 2^k]。在 C++20 中，这正是std::bit_ceil()它所做的。

这是更新功能：

void add(std::size_t index, int value)
{
    for (; index < data.size(); index |= index + 1)
        data[index] += value;
}

完整的代码可以在这里找到。

于 2020-07-15T09:17:22.590 回答