芬威克树(BIT).找到具有给定累积频率的最小索引，单位为 O(logN)

Question

假设我有一个非负值的BIT(芬威克树)，我想找到其中给定累积频率的最小索引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;
}

希望得到您的帮助：)

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()返回泛威树的最小大小，以便底层二叉树是完美的，即如果data.size()在(2^{k-1}, 2^k]范围内，它返回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;
}

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