Fenwick Tree/ Binary Index Tree Interval location
You can perform binary search on a Fenwick Tree.
The idea is Binary Lifting.

I'm assuming that we use a one-based indexing in the Fenwick tree, and that we have exactly $2^k$ elements in the array $A$. And to formalize the problem: we want to find the biggest $i$, such that $A[1] + A[2] + ... + A[i] &lt; x$ for a given $x$. This means that the prefix sum of the first $i$ element is still too small, but the prefix sum of the first $i + 1$ elements is exactly $x$ or already too big.

The exist multiple different implementations of the Fenwick tree. As I said here I use one-based indexing, since the algorithm is a lot more beautiful this way.
For refreshment, one-based indexing in a Fenwick tree means the following (explained using an example): The sum of the first $13 = 1101_2$ numbers can be computed as $bit[1000_2] + bit[1100_2] + bit[1101_2]$, where $bit$ is the array of the nodes of the Fenwick tree. The first summand $bit[1000_2]$ covers the first $1000_2 = 8$ elements (last set bit), the second summand $bit[1100_2]$ covers the next $100_2 = 4$ elements (last set bit), and $bit[1101_2]$ covers the last $1_2 = 1$ elements (last set bit).

This indexing allows a very cool trick:
We can iterate over the bits, from the highest to the lowest one, and check in $O(1)$ time if we should set it or not.

function find_biggest_smaller_index(x):
    // returns biggest i such that A[1] + A[2] + ... + A[i] &lt; x
    i = 0
    for b = log(n)...0:
        set bit b in i
        if bit[i] &lt; x:
            // yay, gives a better lower bound
            // this handes the last 2^b elements, therefore subtract them
            x -= bit[i]
        else:
            // damn, too big already
            unset bit b in i
    return i




edit: now that I think about it. It should also work if the size of the array $A$ is not a power of 2.