# Binary Indexed Tree

• Able to
• Answer sum query within interval.
• Update within fixed-size array.
• Variant
• Answer prefix query of min/max.
• Code

## Example

   _____ 0 _________________________
/   |     |       \               \
1    2     4        8         ____ 16 ____               (1 bit)
|    / \     / | \      /   |     |   \
3   5   6   9  10 12   17   18    20   24           (2 bits)
|      |  | \       |     | \
7     11  13 14     19    21 22             (3 bits)
|               |
15              23             (4 bits)


## Tree structure

• Each node takes index as key.
• ith level contains indices with i bits, e.g.
• First layer has 1(1), 2(10), 4(100), 8(1000).
• Second layer has 3(11), 5(101), 6(110), 9(1001), 10(1010).
• Third layer has 7(111), 11(1011).
• Partial prefix sums are computed and stored in nodes.

## Range of node

• Prefix sums does NOT all start from i=0
• For a current node c and its parent p, it computes sum within [p, c)
• For example, 6 has parent 4, so this node stores sum within [4, 6)

## Compute prefix sum

• Find the leaf node and sum up till root
• e.g. To compute [0, 7)
• Sum up node 7, 6, 4.
• Rationale is that [0, 7) = [000, 100) + [100, 110) + [110, 111)

## Find parent

• Easy way to tell parent is to flip the right most 1, e.g.
• 11 = (1011)_2 --> (1010)_2 = 10
• 10 = (1010)_2 --> (1000)_2 = 8
• Here’s a quicker way to find parent
• x - (x & -x)
• As we know -x is ~x+1
• &ing that with original will only remain the rightmost 1.

## Update value

• When value of some index is updated, multiple nodes need to be updated.
• Find the leaf interval and the other intervals that contains this interval.
• Only two levels are affected.
• One is the current level, all the right siblings are affected.
• The other one is the first level, all the stems on the right are affected.
• e.g. When 8 is updated,
• The leaf interval is like [?, 1001), so node 9 is first found.
• It’s right sibling includes 1010 [8, 10), 1100 [8, 12).
• It’s right ancestors includes 10000 [0, 16), 100000 [0, 32), …

## Find next

• Easy way to find next is to add the right most 1, e.g.
• 1001 + 0001 = 1010 (next sibling)
• 1010 + 0010 = 1100 (next sibling)
• 1100 + 0100 = 10000 (next ancestor)

## Initialize

• Init the array of the same size with all 0’s, whose BIT is also all zeros.
• Update values one by one.
Written on August 16, 2016