0
$\begingroup$

Can someone explain me how do I execute sum query from Index 0 to Index I given the binary value of that Index I. There are some trivial question that I want to know :

  1. Do we have to remove last set bit and all the bits following it.

  2. How many times do I have to access the temporary array made for the data structure i.e Fenwicktree[ ] array. I have been trying to think about these from the binary index of the Index I.

For eg I have the binary

001100100100100011

I removed the last set bit. I took 0 as left and 1 as right and traverse it . Whenever I take a right , I access the tree elements and accessing the array finally when I reach the node.So the count comes around around 6 times. But when I did the same with

1000110111011101100

The answer comes out to be 10 but the the number of times I access the array is 12. How do I get to this ? What am I missing out ? Is there a general way to calculate the number of times just looking at the binary value of Index ? Please help me out.

$\endgroup$
2
$\begingroup$

Answering Question 2:

Simply count the number of 1's in the binary value.

This is part of the beauty of Fenwick trees, they're very simple to implement. The whole algorithm for finding the sum up to some index i is:

sum = 0
while i > 0:
    sum = sum + f_tree[i]
    i = i - (last set bit of i) // remove last set bit
return sum

At each step, we remove the last set bit from the index. Intuitively, the total amount of iterations is equal to however many set bits there are. You can find this in $O(\log i)$.

Answering Question 1:

Yes you do need to remove the last set bit. That is implicit on the structure of the tree.

Let's say the last set bit of some index $i$ is bit $r$ (e.g. if $r = 0$ it is the least significant bit). The value in the Fenwick Tree at index $i$ is "responsible" for the sum of all values $[(i - 2^r + 1) \dots i]$.

Now let's say index $i$ has set bits $\{r_0, r_1, \dots r_k\}$, that is, $i = \sum_{j = 0}^k 2^{r_j}$. We can then get the sum up to index $i$ in segments (iterations of the sum algorithm). Let $S_n$ denote the range that the accumulating some covers after the $n$th iteration.

$$\begin{align} S_0 & = [(i - 2^{r_0} + 1) \dots i]\\ S_1 & = [(i - 2^{r_0} - 2^{r_1} + 1) \dots (i - 2^{r_0})] + [(i - 2^{r_0} + 1) \dots i]\\ & \vdots\\ S_k & = [1 \dots 2^k] + \dots + [(i - 2^{r_0} - 2^{r_1} + 1) \dots (i - 2^{r_0})] + [(i - 2^{r_0} + 1) \dots i] \\ S_k & = [1 \dots i] \end{align}$$

Example

This may be easier to visualize with an example. Take your first one for instance:

001100100100100011$_2$ = 51491$_{10}$

I'm not going to go through all the math, I encourage you to do that. This is, in short, how it would work out with a total of 7 iterations.

$$\begin{align} S_0 & = [51491 \dots 51491]\\ S_1 & = [51489 \dots 51490] + [51491 \dots 51491]\\ & \vdots \\ S_6 & = [1 \dots 32768] + \dots + [51489 \dots 51490] + [51491 \dots 51491]\\ S_6 & = [1 \dots 51491] \end{align}$$


A lot of this information came from this Topcoder Article on Binary Indexed Trees. I would highly recommend reading it if you have confusion with Fenwick Trees.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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