Finding First Position

Given a prefix sum value, find the smallest index $i$ such that $\text{prefix}(i) \geq k$.

function findFirst(k):
    pos = 0
    cur_sum = 0
    for i = LOG down to 0:
        if pos + (1 << i) <= n and cur_sum + tree[pos + (1 << i)] < k:
            pos += (1 << i)
            cur_sum += tree[pos]
    return pos + 1

This walks down the BIT structure, jumping to larger indices when the sum is still too small. Time: $O(\log n)$.

Use case: finding the $k$-th positive element in a 0/1 array, implementing an ordered multiset.