How Fenwick Trees Use the LSB for Prefix Sums

A Fenwick tree, also known as a Binary Indexed Tree (BIT), is a data structure that calculates prefix sums and updates elements in an array in \(O(\log n)\) time. It achieves this efficiency by exploiting the binary representation of array indices—specifically the Least Significant Bit (LSB). This article explains how the LSB determines the range of elements each tree node stores, and how bitwise manipulation enables rapid prefix sum queries and point updates.

Isolating the Least Significant Bit

The Least Significant Bit of an integer is the lowest set bit (value of 1) in its binary representation. In two’s complement binary arithmetic, a positive integer \(i\) and its negation \(-i\) share only one set bit: the lowest one.

You can isolate the LSB using the bitwise AND operator:

\[\text{LSB}(i) = i \ \& \ (-i)\]

Examples:

• \(i = 6\) (Binary: 0110): \(-6\) is ...11111010. 6 & -6 yields 0010 (\(2\)).
• \(i = 8\) (Binary: 1000): \(-8\) is ...11111000. 8 & -8 yields 1000 (\(8\)).
• \(i = 7\) (Binary: 0111): \(-7\) is ...11111001. 7 & -7 yields 0001 (\(1\)).

Range of Responsibility

In a 1-indexed Fenwick tree array BIT[], each index \(i\) does not store a single element; instead, it stores the sum of a contiguous sub-array of the original array \(A[]\).

The length of this sub-array is equal to \(\text{LSB}(i)\), covering the index range:

\[(i - \text{LSB}(i), i] \quad \text{or} \quad [i - \text{LSB}(i) + 1, i]\]

• \(\text{BIT}[1]\) (\(\text{LSB} = 1\)): Stores sum of \(A[1 \dots 1]\)
• \(\text{BIT}[2]\) (\(\text{LSB} = 2\)): Stores sum of \(A[1 \dots 2]\)
• \(\text{BIT}[3]\) (\(\text{LSB} = 1\)): Stores sum of \(A[3 \dots 3]\)
• \(\text{BIT}[4]\) (\(\text{LSB} = 4\)): Stores sum of \(A[1 \dots 4]\)
• \(\text{BIT}[6]\) (\(\text{LSB} = 2\)): Stores sum of \(A[5 \dots 6]\)
• \(\text{BIT}[8]\) (\(\text{LSB} = 8\)): Stores sum of \(A[1 \dots 8]\)

Odd indices have an LSB of \(1\), so they store only their own single value. Powers of two (\(2, 4, 8, \dots\)) store the complete prefix sum from index \(1\) up to that power of two.

Querying Prefix Sums: Subtracting the LSB

Any integer \(k\) can be uniquely represented as a sum of powers of two. To calculate the prefix sum from \(1\) to \(k\), the range \([1, k]\) is decomposed into at most \(\log_2(k)\) disjoint intervals.

To retrieve the prefix sum: 1. Add the value at \(\text{BIT}[k]\) to the total sum. 2. Remove the lowest set bit: \(k \leftarrow k - (k \ \& \ -k)\). 3. Repeat until \(k = 0\).

Example: Querying the Prefix Sum up to Index 7

• Start at \(k = 7\) (0111): Add \(\text{BIT}[7]\) (covers range \([7, 7]\)).
  • \(k = 7 - (7 \ \& \ -7) = 7 - 1 = 6\) (0110).
• Next, \(k = 6\) (0110): Add \(\text{BIT}[6]\) (covers range \([5, 6]\)).
  • \(k = 6 - (6 \ \& \ -6) = 6 - 2 = 4\) (0100).
• Next, \(k = 4\) (0100): Add \(\text{BIT}[4]\) (covers range \([1, 4]\)).
  • \(k = 4 - (4 \ \& \ -4) = 4 - 4 = 0\).
• Result: \(\text{BIT}[7] + \text{BIT}[6] + \text{BIT}[4] = A[7] + (A[5] + A[6]) + (A[1] + A[2] + A[3] + A[4]) = \sum_{j=1}^{7} A[j]\).

Updating Elements: Adding the LSB

When an element at index \(k\) in the original array is modified by adding a value val, every interval in the Fenwick tree that encompasses index \(k\) must be updated.

To propagate the update: 1. Add val to \(\text{BIT}[k]\). 2. Move to the next encompassing range by adding the lowest set bit: \(k \leftarrow k + (k \ \& \ -k)\). 3. Repeat while \(k \le n\) (where \(n\) is the array size).

Example: Updating Index 3

• Start at \(k = 3\) (0011): Update \(\text{BIT}[3]\).
  • \(k = 3 + (3 \ \& \ -3) = 3 + 1 = 4\) (0100).
• Next, \(k = 4\) (0100): Update \(\text{BIT}[4]\).
  • \(k = 4 + (4 \ \& \ -4) = 4 + 4 = 8\) (1000).
• Next, \(k = 8\) (1000): Update \(\text{BIT}[8]\).
• This process continues doubling the step size until \(k > n\), updating all ancestor intervals covering index \(3\).

Summary of Operations