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

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

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

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

Hint

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

Practice

1. What is the primary purpose of a Fenwick tree (Binary Indexed Tree)?

easy

A. To find the maximum element in a list

B. To quickly update elements and calculate prefix sums in a list

C. To sort elements in ascending order

D. To store elements in a balanced binary search tree

Solution

1. Step 1: Understand Fenwick tree functionality

   Fenwick trees are designed to efficiently update values and compute prefix sums in a list.

2. Step 2: Compare with other data structures

   Unlike sorting or maximum finding, Fenwick trees focus on cumulative sums and updates.

3. Final Answer:

   To quickly update elements and calculate prefix sums in a list -> Option B

4. Quick Check:

   Fenwick tree = fast updates + prefix sums [OK]

Hint: Fenwick trees = fast prefix sums and updates [OK]

Common Mistakes:

• Confusing Fenwick trees with sorting algorithms
• Thinking Fenwick trees find max/min values
• Assuming Fenwick trees store elements in sorted order

2. Which of the following is the correct way to update a Fenwick tree at index i with value val in pseudocode?

easy

A. for i in range(i, n): tree[i] += val

B. for i in range(n): tree[i] += val

C. while i <= n: tree[i] += val; i += i & (-i)

D. while i <= n: tree[i] = val; i *= 2

Solution

1. Step 1: Recall Fenwick tree update logic

   Updating involves adding val to tree[i] and moving to the next index using i += i & (-i).

2. Step 2: Check each option

   while i <= n: tree[i] += val; i += i & (-i) matches the correct loop and update pattern; others either use wrong loops or incorrect index updates.

3. Final Answer:

   while i <= n: tree[i] += val; i += i & (-i) -> Option C

4. Quick Check:

   Update uses i += i & (-i) [OK]

Hint: Update index by adding last set bit (i & -i) [OK]

Common Mistakes:

• Using a for loop instead of while
• Assigning value instead of adding
• Incorrect index increment like i *= 2

3. Given a Fenwick tree built for array [1, 2, 3, 4, 5], what is the prefix sum returned by querying index 3?

medium

A. 6

B. 9

C. 10

D. 5

Solution

1. Step 1: Calculate prefix sum up to index 3

   Sum of elements at indices 1, 2, and 3 is 1 + 2 + 3 = 6.

2. Step 2: Confirm Fenwick tree query result

   Fenwick tree query returns the sum of elements from start to index 3, which is 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Sum(1 to 3) = 6 [OK]

Hint: Sum up to index 3 = 1+2+3 = 6 [OK]

Common Mistakes:

• Adding extra elements beyond index 3
• Confusing prefix sum with total sum
• Using zero-based indexing incorrectly

4. Identify the error in this Fenwick tree update pseudocode snippet:

function update(i, val):
  while i < n:
    tree[i] += val
    i += i & (-i)

medium

A. The tree array should be zero-indexed

B. The update should subtract val, not add

C. The index increment should be i -= i & (-i)

D. The loop condition should be while i <= n, not < n

Solution

1. Step 1: Check loop boundary condition

   The Fenwick tree size is n, so updates must include index n, requiring <= instead of <.

2. Step 2: Verify update logic

   Adding val and incrementing index by i & (-i) is correct; no subtraction or decrement needed.

3. Final Answer:

   The loop condition should be while i <= n, not < n -> Option D

4. Quick Check:

   Update loop uses i <= n [OK]

Hint: Use <= n in update loop to include last index [OK]

Common Mistakes:

• Using < instead of <= in loop condition
• Decrementing index instead of incrementing
• Confusing add with subtract in update

5. You have a Fenwick tree for an array of size 8. After updating index 4 by +3, which indices in the Fenwick tree are guaranteed to be updated?

hard

A. 4, 8

B. 4, 5, 6, 7, 8

C. 1, 2, 4

D. Only index 4

Solution

1. Step 1: Understand Fenwick tree update jumps

   Starting at index 4, the next index updated is 4 + (4 & -4) = 4 + 4 = 8.

2. Step 2: List updated indices

   Indices 4 and 8 are updated; no other indices between 4 and 8 are updated in this step.

3. Final Answer:

   4, 8 -> Option A

4. Quick Check:

   Update jumps: i, i + (i & -i) [OK]

Hint: Update indices jump by last set bit (4 to 8) [OK]

Common Mistakes:

• Assuming all indices after 4 update
• Confusing update with query indices
• Forgetting Fenwick tree uses bitwise jumps