Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

BIT:Using a binary indexed tree? [closed]

A binary indexed tree has very few or relatively no theory to study as compared to other data structures. The only place where it is taught succinctly is the topcoder tutorial. Although the tutorial is complete in all the explanations, I cannot understand that what is the intuition behind such a tree? And how to prove it's correctness?

I presume that the proof is to complex to explain. So when using BIT, what approach do you follow?

like image 608
Nikunj Banka Avatar asked Mar 15 '13 18:03

Nikunj Banka


People also ask

How do you use a binary indexed tree?

Let us consider the following problem to understand Binary Indexed Tree. 1 Compute the sum of the first i elements. 2 Modify the value of a specified element of the array arr[i] = x where 0 <= i <= n-1. A simple solution is to run a loop from 0 to i-1 and calculate the sum of the elements.

Where can you use Fenwick trees?

The Fenwick Tree, also called Binary Indexed Tree, is a data structure used to update elements and evaluate range queries in arrays. It differs from other similar data structures by using a method to arrange binary numbers in two dimensions.

Is binary indexed tree and Fenwick Tree same?

A Fenwick tree, also called a binary indexed tree (BIT), is a data structure that can efficiently update elements and calculate range sums on a list of numbers. This tutorial will show how to construct a Fenwick tree to solve a mutable range sum query problem.

Why are Fenwick trees?

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. This structure was proposed by Boris Ryabko in 1989 with a further modification published in 1992.

What is the size of the binary indexed tree?

Each node of the Binary Indexed Tree stores the sum of some elements of the input array. The size of the Binary Indexed Tree is equal to the size of the input array, denoted as n. In the code below, we use a size of n+1 for ease of implementation. We initialize all the values in BITree[] as 0.

How do you update a binary indexed tree in SQL?

update (x, val): Updates the Binary Indexed Tree (BIT) by performing arr += val // Note that the update (x, val) operation will not change arr. It only makes changes to BITree 1) Initialize the current index as x+1. 2) Do the following while the current index is smaller than or equal to n. …a) Add the val to BITree …b) Go to next element of BITree.

What is the difference between RMQ and binary indexed tree?

Another approach is to use the Binary Indexed Tree data structure, also with the worst time complexity O (m log n) — but Binary Indexed Trees are easier to code and require less memory space than RMQ. Before we proceed with defining the structure and stating the algorithms, we introduce some notations: f [i] - frequency at index i, i = 1 … MaxIdx

What is the last bit of 13 in binary?

In binary notation, 13 is equal to 1101. Interestingly, in this example it holds c [1101] = tree [1101] + tree [1100] + tree [1000] (we will reveal this connection in more detail later). NOTE: For the sake of brevity, we will use “the last bit” to refer to the least significant non-zero bit of the corresponding integer.


1 Answers

I found this answer by @templatetypedef very clearly explain about the intuition and proof of a binary indexed tree: The answer....

Intuitively, you can think of a binary indexed tree as a compressed representation of a binary tree that is itself an optimization of a standard array representation. This answer goes into one possible derivation.

Let's suppose, for example, that you want to store cumulative frequencies for a total of 7 different elements. You could start off by writing out seven buckets into which the numbers will be distributed:

[   ] [   ] [   ] [   ] [   ] [   ] [   ]   1     2     3     4     5     6     7 

Now, let's suppose that the cumulative frequencies look something like this:

[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]   1     2     3     4     5     6     7 

Using this version of the array, you can increment the cumulative frequency of any element by increasing the value of the number stored at that spot, then incrementing the frequencies of everything that come afterwards. For example, to increase the cumulative frequency of 3 by 7, we could add 7 to each element in the array at or after position 3, as shown here:

[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]   1     2     3     4     5     6     7 

The problem with this is that it takes O(n) time to do this, which is pretty slow if n is large.

One way that we can think about improving this operation would be to change what we store in the buckets. Rather than storing the cumulative frequency up to the given point, you can instead think of just storing the amount that the current frequency has increased relative to the previous bucket. For example, in our case, we would rewrite the above buckets as follows:

Before: [ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]   1     2     3     4     5     6     7  After: [ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]   1     2     3     4     5     6     7 

Now, we can increment the frequency within a bucket in time O(1) by just adding the appropriate amount to that bucket. However, the total cost of doing a lookup now becomes O(n), since we have to recompute the total in the bucket by summing up the values in all smaller buckets.

The first major insight we need to get from here to a binary indexed tree is the following: rather than continuously recomputing the sum of the array elements that precede a particular element, what if we were to precompute the total sum of all the elements before specific points in the sequence? If we could do that, then we could figure out the cumulative sum at a point by just summing up the right combination of these precomputed sums.

One way to do this is to change the representation from being an array of buckets to being a binary tree of nodes. Each node will be annotated with a value that represents the cumulative sum of all the nodes to the left of that given node. For example, suppose we construct the following binary tree from these nodes:

             4           /     \          2       6         / \     / \        1   3   5   7 

Now, we can augment each node by storing the cumulative sum of all the values including that node and its left subtree. For example, given our values, we would store the following:

Before: [ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]   1     2     3     4     5     6     7  After:                  4                [+32]               /     \            2           6          [ +6]       [+80]          /   \       /   \         1     3     5     7       [ +5] [+15] [+52] [ +0] 

Given this tree structure, it's easy to determine the cumulative sum up to a point. The idea is the following: we maintain a counter, initially 0, then do a normal binary search up until we find the node in question. As we do so, we also the following: any time that we move right, we also add in the current value to the counter.

For example, suppose we want to look up the sum for 3. To do so, we do the following:

  • Start at the root (4). Counter is 0.
  • Go left to node (2). Counter is 0.
  • Go right to node (3). Counter is 0 + 6 = 6.
  • Find node (3). Counter is 6 + 15 = 21.

You could imagine also running this process in reverse: starting at a given node, initialize the counter to that node's value, then walk up the tree to the root. Any time you follow a right child link upward, add in the value at the node you arrive at. For example, to find the frequency for 3, we could do the following:

  • Start at node (3). Counter is 15.
  • Go upward to node (2). Counter is 15 + 6 = 21.
  • Go upward to node (1). Counter is 21.

To increment the frequency of a node (and, implicitly, the frequencies of all nodes that come after it), we need to update the set of nodes in the tree that include that node in its left subtree. To do this, we do the following: increment the frequency for that node, then start walking up to the root of the tree. Any time you follow a link that takes you up as a left child, increment the frequency of the node you encounter by adding in the current value.

For example, to increment the frequency of node 1 by five, we would do the following:

                 4                [+32]               /     \            2           6          [ +6]       [+80]          /   \       /   \       > 1     3     5     7       [ +5] [+15] [+52] [ +0] 

Starting at node 1, increment its frequency by 5 to get

                 4                [+32]               /     \            2           6          [ +6]       [+80]          /   \       /   \       > 1     3     5     7       [+10] [+15] [+52] [ +0] 

Now, go to its parent:

                 4                [+32]               /     \          > 2           6          [ +6]       [+80]          /   \       /   \         1     3     5     7       [+10] [+15] [+52] [ +0] 

We followed a left child link upward, so we increment this node's frequency as well:

                 4                [+32]               /     \          > 2           6          [+11]       [+80]          /   \       /   \         1     3     5     7       [+10] [+15] [+52] [ +0] 

We now go to its parent:

               > 4                [+32]               /     \            2           6          [+11]       [+80]          /   \       /   \         1     3     5     7       [+10] [+15] [+52] [ +0] 

That was a left child link, so we increment this node as well:

                 4                [+37]               /     \            2           6          [+11]       [+80]          /   \       /   \         1     3     5     7       [+10] [+15] [+52] [ +0] 

And now we're done!

The final step is to convert from this to a binary indexed tree, and this is where we get to do some fun things with binary numbers. Let's rewrite each bucket index in this tree in binary:

                100                [+37]               /     \           010         110          [+11]       [+80]          /   \       /   \        001   011   101   111       [+10] [+15] [+52] [ +0] 

Here, we can make a very, very cool observation. Take any of these binary numbers and find the very last 1 that was set in the number, then drop that bit off, along with all the bits that come after it. You are now left with the following:

              (empty)                [+37]               /     \            0           1          [+11]       [+80]          /   \       /   \         00   01     10   11       [+10] [+15] [+52] [ +0] 

Here is a really, really cool observation: if you treat 0 to mean "left" and 1 to mean "right," the remaining bits on each number spell out exactly how to start at the root and then walk down to that number. For example, node 5 has binary pattern 101. The last 1 is the final bit, so we drop that to get 10. Indeed, if you start at the root, go right (1), then go left (0), you end up at node 5!

The reason that this is significant is that our lookup and update operations depend on the access path from the node back up to the root and whether we're following left or right child links. For example, during a lookup, we just care about the left links we follow. During an update, we just care about the right links we follow. This binary indexed tree does all of this super efficiently by just using the bits in the index.

The key trick is the following property of this perfect binary tree:

Given node n, the next node on the access path back up to the root in which we go right is given by taking the binary representation of n and removing the last 1.

For example, take a look at the access path for node 7, which is 111. The nodes on the access path to the root that we take that involve following a right pointer upward is

  • Node 7: 111
  • Node 6: 110
  • Node 4: 100

All of these are right links. If we take the access path for node 3, which is 011, and look at the nodes where we go right, we get

  • Node 3: 011
  • Node 2: 010
  • (Node 4: 100, which follows a left link)

This means that we can very, very efficiently compute the cumulative sum up to a node as follows:

  • Write out node n in binary.
  • Set the counter to 0.
  • Repeat the following while n ≠ 0:
    • Add in the value at node n.
    • Remove the leftmost 1 bit from n.

Similarly, let's think about how we would do an update step. To do this, we would want to follow the access path back up to the root, updating all nodes where we followed a left link upward. We can do this by essentially doing the above algorithm, but switching all 1's to 0's and 0's to 1's.

The final step in the binary indexed tree is to note that because of this bitwise trickery, we don't even need to have the tree stored explicitly anymore. We can just store all the nodes in an array of length n, then use the bitwise twiddling techniques to navigate the tree implicitly. In fact, that's exactly what the bitwise indexed tree does - it stores the nodes in an array, then uses these bitwise tricks to efficiently simulate walking upward in this tree.

Hope this helps!

like image 167
Nikunj Banka Avatar answered Sep 20 '22 19:09

Nikunj Banka