Fenwick Tree (Binary Indexed Tree) šŸŽÆ

beginner
6 min

Fenwick Tree (Binary Indexed Tree) šŸŽÆ

Welcome to our comprehensive guide on Fenwick Trees (also known as Binary Indexed Ttrees)! This lesson is designed for both beginners and intermediates, covering the concepts from the ground up.

What is a Fenwick Tree? šŸ“

A Fenwick Tree (FT) is a data structure used for efficient range queries and updates on a sequence of numbers. It's particularly useful in algorithms that require frequent queries and updates on a large dataset.

Why use a Fenwick Tree? šŸ’”

Fenwick Trees offer several advantages:

  1. Efficient Range Sum Queries: Calculating the sum of elements in a range can be done in O(log n) time, which is much faster than a linear scan for large datasets.

  2. Efficient Updates: Updating an element's value can also be done in O(log n) time.

  3. Space Efficiency: Fenwick Tree requires only 2n space, where n is the size of the array.

Building a Fenwick Tree šŸ’”

Let's create a Fenwick Tree for the following array:

[3, 5, 6, 1, 4, 1, 5, 9, 2, 6, 5, 3]

Initialization šŸ“

First, we create an empty Fenwick Tree of the same size as the array. Each node initially holds a value of 0.

python
def buildFenwickTree(arr): ft = [0] * (len(arr) + 1) for i in range(1, len(arr) + 1): ft[i] = arr[i - 1] for j in range(i + 1, len(ft)): ft[j] += ft[j - (j % i)]

Range Sum Query šŸ’”

To find the sum of elements in a range [L, R], we follow these steps:

  1. Calculate ft[R+1], which includes the sum of elements up to (and not including) R+1.
  2. If L has a power of i (i.e., L = ki for some k), subtract the sum of elements up to L (ft[L]).
  3. Otherwise, find the smallest power of i greater than L (let's call it L'), subtract the sum of elements up to L' - 1 (ft[L' - 1]), and subtract the sum of elements from L' to i - 1 (ft[i - 1] - ft[L' - i]).
python
def rangeSum(ft, L, R): if L == 0: return ft[R+1] L -= 1 S = 0 while L > 0: S += ft[L] L = L - (L & -L) if R != 0: S += ft[R+1] - ft[L] return S

Updating Elements šŸ’”

To update an element at position i with a new value val, we update the node at i and all its ancestors with the delta val - old_val.

python
def update(ft, i, val): for j in range(i, len(ft)): ft[j] += val - ft[j]

Practical Application šŸ’”

Fenwick Trees can be used in various problems related to range queries and updates, such as finding the number of set bits in an integer, finding the k-th smallest element, etc.

Quiz šŸ“