Binary Indexed Tree/Fenwick Tree: Range Sum Query

Binary Indexed Tree(BIT) is a data structure that stores the sum of a range of elements of a given array. It can be represented as an 1-based indexing array. BIT allows us to update elements and query range sums in O(log n) time. Use index + index & (-index) and index - index & (-index) expression to find the next index in the BIT to update elements and query range sums respectively.

Binary Index Tree

Table of Contents

· Extract the Rightmost Set Bit(RSB)
· Clear the Rightmost Set Bit(RSB)
· Add 1 to the Rightmost Set Bit(RSB)
· Binary Indexed Tree(BIT)/Fenwick Tree
  ∘ Construct Binary Indexed Tree
  ∘ Range Size for Each Index
  ∘ Find Next Index(Parent Node)
  ∘ Compute Range Sums
· Query Range Sum
· Update Elements
· LeetCode 307- Range Sum Query - Mutable
  ∘ Graphical Explanation
  ∘ Code Implementation

Extract the Rightmost Set Bit(RSB)

Use bit operation n & (-n) to get the rightmost set bit.

n: integer
RSB = n & (-n)

extract the rightmost set bit

Clear the Rightmost Set Bit(RSB)

n: integer
n = n - n & (-n) 
  = n - RSB

clear the rightmost set bit

Add 1 to the Rightmost Set Bit(RSB)

n: integer
n = n + n & (-n) 
  = n + RSB

add 1 to the rightmost set bit

Binary Indexed Tree(BIT)/Fenwick Tree

A Binary Indexed Tree(a.k.a Fenwick Tree) is a data structure that can be represented as an array to store the sum of a range of elements of the given array. The beauty of Binary Indexed Tree is to update elements and query partial sums in O(log n) running time.

Range sums stored in the Binary Indexed Tree depends on the position of the rightmost set bit in the corresponding binary index. Therefore, Binary Indexed Tree is 1-indexed because 0 has no least significant bit.

Binary Indexed Tree

Construct Binary Indexed Tree

construct Binary Indexed Tree

Range Size for Each Index

Based on the position of the rightmost set bit(RSB) in the binary representation of the index, the range size is 2 to the power of RSB position. Take index 10 as an example, the the binary number of 10 is 1010. The position of RSB in 1010 is 1, so the range size at index 10 is 2¹ = 2.

calculate range size for each index

Find Next Index(Parent Node)

RSB(index): the rightmost set bit in index
next index = index + index & (-index) 
           = index + RSB(index)

Take index 5 as an example.

example

find next index

Compute Range Sums

Iterate over the given array. For each index, add the current element to the current node and its parent nodes in the BIT.

Query Range Sum

To compute the sum of first n elements in a given array. We start with index n in BIT and add the BIT[n] to sum. Then unset the rightmost set bit of n to find the next index. Repeat above steps if index > 0.

RSB(index): the rightmost set bit in index
next index = index - index & (-index)
           = index - RSB(index)

Consider querying the sum of first 11 elements in an array.

sum(i, j) = rangeSum(j) - rangeSum(i-1)

query range sum

Update Elements

Update elements in the given array, and then update the BIT array.

Add 1 to the rightmost set bit of the current BIT index to find the next index to update.

RSB(index): the rightmost set bit in index
next index = index + index & (-index)
           = index + RSB(index)

LeetCode 307- Range Sum Query — Mutable

Graphical Explanation

• Binary Index Tree

BIT process

• Query Range Sums

query ranage sums process

• Update Element

update element process

Code Implementation

• Golang

• Python

You can access the source code here.

LeetCode Problem

• 307. Range Sum Query — Mutable