Fenwick Tree - Detailed

Welcome to the in-depth guide on Fenwick Trees! In this lesson, we'll explore what Fenwick Trees are, why they're important, and how to use them. Let's dive right in!

What is a Fenwick Tree? 🎯

A Fenwick Tree, also known as a Binary Indexed Tree, is a data structure used for efficient range queries and updates on a sequence of numbers. Fenwick Trees can help us quickly answer questions like "What is the sum of all elements from index i to j?" or "Update the value at index i."

Why use a Fenwick Tree? 💡

Fenwick Trees offer several advantages:

Efficient Range Queries: Calculating the sum of elements in a range is a common operation in many problems, and Fenwick Trees allow us to do this in O(log n) time.
Efficient Updates: Updating a single element also takes O(log n) time, making Fenwick Trees efficient for updating large datasets.
Space Efficient: Fenwick Trees use only 2n space, where n is the size of the input array, making them space-efficient compared to other solutions.

How does a Fenwick Tree work? 📝

A Fenwick Tree is built upon an array, where each index i represents a range ending at i. The value at index i stores the sum of elements from 0 to i.

markdown

Fenwick Tree: [3, 5, 7, 8, 10, 12, 15]
Array representation: [0, 3, 8, 15, 23, 35, 47]

In the above example, the Fenwick Tree array represents the following:

The sum of elements from 0 to 0 (index 0) is 0.
The sum of elements from 0 to 3 (index 3) is 3 (3 + 0).
The sum of elements from 0 to 4 (index 4) is 8 (3 + 5).
And so on...

Building a Fenwick Tree 📝

Building a Fenwick Tree involves building the corresponding array and then populating it using the following formula:

markdown

array[i] = array[i] + array[(i + mask)]

Here, mask is (i - 1) shifted to the right by 1. For example, if i is 3, then mask is (3 - 1) = 2, and (i + mask) is (3 + 2) = 5.

Updating a Fenwick Tree 💡

To update a value at index i, we first update the value at index i and then propagate the update to its ancestors using the same formula as above.

Range Queries 💡

To find the sum of elements in a range [i, j], we simply find the sum of elements at index i, j, and all the intermediate indices (i + mask) where mask is (2^k - 1).

Real-world Applications 🎯

Fenwick Trees find applications in problems involving dynamic range sum queries and updates, such as:

Lazy Propagation: Used in dynamic programming for solving problems with overlapping sub-problems, such as Matrix Chain Multiplication, All Pairs Shortest Paths, etc.
Frequency Queries: Used in data structures like LFU Cache, where we need to find the least frequently used items.

Code Examples 📝

C++ Fenwick Tree

cpp

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int arr[N];
int ft[N];

void buildFenwickTree(int n) {
    for (int i = 1; i <= n; i++) {
        ft[i] = arr[i];
        for (int j = i + (-i & i); j <= n; j += (j & -j)) {
            ft[j] += arr[i];
        }
    }
}

int sumRange(int i, int j) {
    int sum = 0;
    for (int i_ = i; i_ <= j; i_ += (i_ & -i_)) {
        sum += ft[i_];
    }
    return sum;
}

void update(int i, int val) {
    for (int i_ = i; i <= N; i += (i & -i)) {
        ft[i] += val - arr[i];
        arr[i] = val;
    }
}

Python Fenwick Tree

python

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

def sum_range(ft, i, j):
    return sum(ft[x] for x in range(i, j + 1))

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