Fenwick trees (Binary Indexed Trees) in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Fenwick tree (Binary Indexed Tree)?

A Fenwick tree is a data structure that helps efficiently compute prefix sums and update elements in a list of numbers. It uses a tree-like structure stored in an array to perform these operations quickly.

beginner

What operations does a Fenwick tree support efficiently?

It supports two main operations efficiently: 1) Updating the value of an element, and 2) Calculating the sum of elements from the start up to a given position (prefix sum). Both operations run in about O(log n) time.

intermediate

How does a Fenwick tree store data internally?

A Fenwick tree stores cumulative frequency information in an array. Each position in the array represents a range of elements, and the tree structure is implicit in the way indices are updated and queried using bit manipulation.

intermediate

Why is bit manipulation important in Fenwick trees?

Bit manipulation helps quickly find the parent or next index to update or query in the Fenwick tree. For example, using the operation 'index & (-index)' isolates the last set bit, which guides how the tree moves through indices.

beginner

In what real-life scenario can Fenwick trees be useful?

Fenwick trees are useful in situations where you need to frequently update values and get running totals, like tracking cumulative sales over time or managing scores in a game leaderboard efficiently.

What is the time complexity of updating an element in a Fenwick tree?

A O(log n)

B O(n)

C O(1)

D O(n log n)

Updating an element in a Fenwick tree takes O(log n) time because it updates a few nodes along the tree path using bit manipulation.

Which operation is NOT efficiently supported by a Fenwick tree?

A Finding the maximum element

B Single element updates

C Prefix sum queries

D Range sum queries without modification

Fenwick trees do not efficiently support finding the maximum element; they are designed for prefix sums and updates.

What does the expression 'index & (-index)' do in Fenwick trees?

A Calculates the sum of elements

B Finds the last set bit of index

C Updates the entire tree

D Finds the maximum value

The expression isolates the last set bit of the index, which helps navigate the Fenwick tree structure.

Fenwick trees are mainly used to efficiently compute:

A Finding shortest paths

B Sorting arrays

C Prefix sums and updates

D Matrix multiplication

Fenwick trees are designed to quickly compute prefix sums and update values.

Which data structure is Fenwick tree often compared to for similar tasks?

A Linked list

B Queue

C Stack

D Segment tree

Fenwick trees and segment trees both support range queries and updates, but Fenwick trees are simpler and use less memory.

Explain how a Fenwick tree helps in calculating prefix sums efficiently.

Think about how the tree breaks down the sum into smaller parts.

Describe a real-world example where Fenwick trees can improve performance.

Consider situations where you add new data often and want quick totals.

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