Fenwick trees (Binary Indexed Trees) in Data Structures Theory - Mini Project: Build & Apply

Fenwick trees (Binary Indexed Trees)

📖 Scenario: Imagine you have a list of daily sales numbers for a small shop. You want to quickly find the total sales for any range of days and also update the sales for a specific day when new data arrives.Fenwick trees, also called Binary Indexed Trees, help you do this efficiently.

🎯 Goal: Build a Fenwick tree step-by-step to store sales data, update sales for a day, and calculate the total sales for a range of days.

📋 What You'll Learn

Create a list called sales with exact daily sales values

Create a Fenwick tree list called fenw initialized with zeros

Write a function fenw_update to update the Fenwick tree

Write a function fenw_sum to get prefix sums from the Fenwick tree

💡 Why This Matters

🌍 Real World

Fenwick trees are used in software that needs fast updates and queries on cumulative data, like financial applications, gaming leaderboards, or sensor data analysis.

💼 Career

Understanding Fenwick trees helps in roles involving algorithms, data analysis, and performance optimization in software engineering.

1

Create the sales data list

Create a list called sales with these exact daily sales values: 5, 3, 7, 9, 6, 2, 4, 8.

Data Structures Theory

# Create the sales list with exact values
# Your code here

Need a hint?

Use square brackets and commas to list the sales numbers exactly as given.

2

Initialize the Fenwick tree list

Create a list called fenw with the same length as sales, filled with zeros.

Data Structures Theory

sales = [5, 3, 7, 9, 6, 2, 4, 8]
# Create fenw list with zeros of same length as sales
# Your code here

Need a hint?

Use len(sales) to get the length and multiply a list with zero to create fenw.

3

Write the Fenwick tree update function

Write a function called fenw_update that takes parameters index, value, and updates the fenw list accordingly. Use 1-based indexing inside the function and update all relevant positions by adding value. Use a while loop and the expression index += index & (-index) to move to the next position.

Data Structures Theory

sales = [5, 3, 7, 9, 6, 2, 4, 8]
fenw = [0] * len(sales)
# Define fenw_update function to update fenw list
# Your code here

Need a hint?

Remember Fenwick trees use 1-based indexing internally, so adjust the list index by subtracting 1.

4

Write the Fenwick tree prefix sum function

Write a function called fenw_sum that takes parameter index and returns the sum of sales from day 1 up to index. Use 1-based indexing and a while loop. Inside the loop, add fenw[index - 1] to a total variable, then update index by subtracting index & (-index). Return the total sum at the end.

Data Structures Theory

sales = [5, 3, 7, 9, 6, 2, 4, 8]
fenw = [0] * len(sales)

def fenw_update(index, value):
    while index <= len(fenw):
        fenw[index - 1] += value
        index += index & (-index)

# Define fenw_sum function to get prefix sum
# Your code here

Need a hint?

Use a loop that decreases the index by the last set bit until it reaches zero, accumulating sums.