Fenwick trees (Binary Indexed Trees) in Data Structures Theory - Step-by-Step Execution

Concept Flow - Fenwick trees (Binary Indexed Trees)

Start with array

↓

Build Fenwick Tree

↓

Query prefix sum

↓

Update element

↓

Repeat queries/updates

↓

End

Fenwick tree starts by building from an array, then supports fast prefix sum queries and updates by moving through tree nodes using bit operations.

Execution Sample

Data Structures Theory

arr = [1,2,3,4,5]
fenw = [0]*6

def update(i, val):
    while i < len(fenw):
        fenw[i] += val
        i += i & (-i)

def query(i):
    s = 0
    while i > 0:
        s += fenw[i]
        i -= i & (-i)
    return s

# Build fenw
for i in range(1,6):
  update(i, arr[i-1])

# Query sum(1..3)
print(query(3))

Build Fenwick tree from array and query sum of first 3 elements.

Analysis Table

Step	i	Action	Fenw array state	Output
1	1	update(1,1)	[0,1,1,0,1,0]
2	2	update(2,2)	[0,1,3,0,3,0]
3	3	update(3,3)	[0,1,3,3,6,0]
4	4	update(4,4)	[0,1,3,3,10,0]
5	5	update(5,5)	[0,1,3,3,10,5]
6	3	query sum(3)	[0,1,3,3,10,5]	6
7	4	query sum(4)	[0,1,3,3,10,5]	10
8	5	query sum(5)	[0,1,3,3,10,5]	15
9	-	update(3,2) (add 2 to index 3)	[0,1,3,5,12,5]
10	5	query sum(5)	[0,1,3,5,12,5]	17
11	-	End	[0,1,3,5,12,5]

💡 Finished building Fenwick tree and performing queries and updates.

State Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 9	Final
fenw	[0,0,0,0,0,0]	[0,1,1,0,1,0]	[0,1,3,0,3,0]	[0,1,3,3,6,0]	[0,1,3,3,10,0]	[0,1,3,3,10,5]	[0,1,3,3,10,5]	[0,1,3,5,12,5]	[0,1,3,5,12,5]
output							6		17

Key Insights - 3 Insights

Why does the Fenwick tree array have one extra element compared to the input array?

Fenwick tree uses 1-based indexing internally for easier bit manipulation, so fenw array size is input size + 1 (see rows 1-5 in execution_table).

How does the update function affect multiple positions in the Fenwick tree?

Update adds the value to fenw[i] and then moves to next index by adding the last set bit of i, updating all relevant nodes (see steps 1-5 and 9).

Why does the query sum(3) return 6 in step 6?

Query sums fenw[3] + fenw[2] = 3 + 3 = 6, combining partial sums stored in Fenwick tree nodes (step 6 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 6. What is the prefix sum output for sum(3)?

A 9

B 5

C 6

D 3

💡 Hint

Check the Output column at step 6 in execution_table.

At which step does the Fenwick tree get updated to include an additional +2 at index 3?

A Step 5

B Step 9

C Step 3

D Step 7

💡 Hint

Look for update actions with value 2 in the Action column.

If the initial array had 6 elements instead of 5, how would the fenw array size change?

A Size would be 7

B Size would be 6

C Size would be 5

D Size would be 8

💡 Hint

Fenwick tree uses 1-based indexing, so fenw size = input size + 1.

Concept Snapshot

Fenwick trees store cumulative frequencies for fast prefix sums.
Use 1-based indexing array fenw.
Update adds value at index and moves up using i += i & (-i).
Query sums prefix by moving down using i -= i & (-i).
Both operations run in O(log n) time.

Full Transcript

Fenwick trees, also called Binary Indexed Trees, help quickly find sums of elements from the start of an array up to any position. We build a fenw array one element larger than the input to use 1-based indexing. To update, we add a value at an index and then move to the next relevant node by adding the last set bit of the index. To query a prefix sum, we add fenw values moving down by subtracting the last set bit until we reach zero. This process is efficient and runs in logarithmic time. The execution table shows building fenw from an array, querying sums, and updating values step-by-step.

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