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 + A + ... + A[i] < 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.
// returns biggest i such that A + A + ... + A[i] < x
i = 0
for b = log(n)...0:
set bit b in i
if bit[i] < x:
// yay, gives a better lower bound
// this handes the last 2^b elements, therefore subtract them
x -= bit[i]
// damn, too big already
unset bit b in 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.