3
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ What intervals are you talking about? And what does it mean that a point lies inside an interval? $\endgroup$
    – Jakube
    Commented Mar 5, 2019 at 18:01
  • $\begingroup$ @Jakube I've added a bit more to my original post. $\endgroup$
    – user112495
    Commented Mar 5, 2019 at 18:04
  • $\begingroup$ Wouldn't a simple binary search work? Why do you need Fenwick tree? $\endgroup$
    – John L.
    Commented Mar 5, 2019 at 18:18
  • $\begingroup$ @Apass.Jack It would, but I think that would take log^2(N) time, rather than just log(N). $\endgroup$
    – user112495
    Commented Mar 5, 2019 at 18:19
  • $\begingroup$ Assume $N$ is the length of the array. A binary search search for the first cumulative sum that is no less than a given number takes $\log(N)$ time. The interval is then [that sum, the next sum], except a couple of boundary cases. $\endgroup$
    – John L.
    Commented Mar 5, 2019 at 18:21

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Ah, that makes sense. It seems to be working! And yeah, I think taking the ceiling of log(N) is enough to have it work for non-powers of 2! $\endgroup$
    – user112495
    Commented Mar 6, 2019 at 18:55
  • $\begingroup$ What's the best way to avoid i getting too high that you get out of bounds errors? If the number I'm looking for is close to the end of my interval, I'm finding that as I go along changing 0's to 1's and vice versa, I sometimes get a number that's larger than the size of my array (this is in the case where my number is not a power of 2). What would be the best way to stop this? Is there a better/ smarter way than just checking if i is larger than the size of your array at each time step (and clearing the bit if it is)? $\endgroup$
    – user112495
    Commented Mar 6, 2019 at 19:50
  • 1
    $\begingroup$ @user112495 Oh right, that can happen. The method you described (clear bit if it is bigger) will work, and is probably the best thing. I don't think you can avoid doing that, other than filling the array with 0s. $\endgroup$
    – Jakube
    Commented Mar 6, 2019 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.