Fenwick trees (Binary Indexed Trees) in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize a Fenwick tree array of size n+1.

Data Structures Theory

fenwicks = [0] * [1]

Drag options to blanks, or click blank then click option'

An+1

Bn-1

Cn

D2*n

Attempts:

3 left

💡 Hint

Common Mistakes

Using size n causes index errors because index 0 is unused.

Using size n-1 is too small and misses elements.

The Fenwick tree uses 1-based indexing, so the array size is n+1 to include index n.

2fill in blank

medium

Complete the code to get the least significant bit (LSB) of an integer x.

Data Structures Theory

lsb = x & [1]

Drag options to blanks, or click blank then click option'

A-x

B1

Cx

D~x

Attempts:

3 left

💡 Hint

Common Mistakes

Using x & x returns x itself, not the LSB.

Using x & 1 only checks the last bit, not the full LSB.

The expression x & (-x) isolates the least significant bit set to 1 in x.

3fill in blank

hard

Fix the error in the Fenwick tree update function to correctly move to the next index.

Data Structures Theory

def update(i, delta):
    while i < len(fenwicks):
        fenwicks[i] += delta
        i += [1]

Drag options to blanks, or click blank then click option'

Ai | (-i)

Bi + 1

Ci & i

Di & (-i)

Attempts:

3 left

💡 Hint

Common Mistakes

Adding 1 instead of the LSB causes incorrect updates.

Using bitwise OR or AND with wrong operands breaks the logic.

To move to the next index in Fenwick tree update, add the least significant bit (i & -i) to i.

4fill in blank

hard

Fill both blanks to compute the prefix sum up to index i in a Fenwick tree.

Data Structures Theory

def prefix_sum(i):
    result = 0
    while i > 0:
        result += fenwicks[[1]]
        i -= [2]
    return result

Drag options to blanks, or click blank then click option'

Ai

Bi & (-i)

Ci + 1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using i + 1 as index causes out-of-range errors.

Adding or subtracting wrong values breaks the prefix sum logic.

To get the prefix sum, add fenwicks[i] and then move to the parent by subtracting the LSB (i & -i).

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps each index to its Fenwick tree prefix sum if the sum is positive.

Data Structures Theory

result = [1]: prefix_sum([2]) for [3] in range(1, n+1) if prefix_sum([2]) > 0}

Drag options to blanks, or click blank then click option'

Ai

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names causes NameError.

Using index instead of i breaks the comprehension.

The comprehension uses i as the key and argument to prefix_sum, iterating i from 1 to n.

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