Fenwick Tree/ Binary Index Tree Interval location

I have an array of positive numbers, and when calculating the cumulative sum of this array, want to know which interval a given point will lie in.

I have done this by searching linearly through an array, but want to use Fenwick trees in the hopes the speed up will be noticeable. I've followed tutorials online, and have now implemented construct, update and getsum functions. I'm not sure how to go about determining which interval a point will lie in though (while taking advantage of the data structure).

So for example, if I had the array [1,2,2,1,4,6,7,3], then I could calculate the cumulative sum as [1,3,5,6,10,16,23,26]. If I the had the number 17, I'd want to know what interval this lies in. So starting indexing at 0, this would be in the interval between the 5th and 6th elements of the array.

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] < 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] < 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]
        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.

StackExchange Computer Science Q#105187, answer score: 2