芬威克树（BIT）。在 O(logN) 中找到具有给定累积频率的最小索引

Question

假设我有一个非负值的 BIT（Fenwick 树），我想在 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;

我知道我们可以按照 here 的描述在 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;
}

希望得到您的帮助:)

Answer 1

这是我为具有基于 0 的索引的 Fenwick 树实现的类似 lower_bound 的函数：

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

data 是基础 std::vector<int>。辅助函数 msb_size_mask() returns Fenwick 树的最小大小使得底层二叉树是完美的，即它 returns 2^k 如果 data.size() 在范围 (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;
}

完整代码可见here.

芬威克树（BIT）。在 O(logN) 中找到具有给定累积频率的最小索引

Fenwick tree(BIT). Find the smallest index with given cumulative frequency in O(logN)

c++

algorithm

binary-search

fenwick-tree

binary-indexed-tree