1. Introduction

A Fenwick tree, also called a binary indexed tree (BIT), is a data structure that can efficiently update elements and calculate range sums on a list of numbers. This tutorial will show how to construct a Fenwick tree to solve a mutable range sum query problem.

2. Problem Description

Let’s start with a mutable range sum query problem. Given an array of numbers A = \{A_1, A_2, ..., A_n\} with starting index of 1, we have two operations: update and sum. For an update operation, update(i , value), we change the value of the element at the index i to be value. For a sum operation, sum(left , right), we calculate the sum of numbers between positions left and right inclusive. Our goal is to implement these two operations efficiently.

3. Brute Force Solution

For the update operation, we can directly update the array element at the specified location. For the sum operation, we can iterate the array from index left to right and sum each element:

// In both functions:
//    A = a number array with size n
 
function Update(i, value):
    // INPUT
    //    i = index in array A where update occurs
    //    value = the new value to update at index i
    // OUTPUT
    //    Updates array A
     
    A[i] <- value

function Sum(left, right):
    // INPUT
    //    left = the left index of the range to sum
    //    right = the right index of the range to sum
    // OUTPUT
    //    The sum of elements between left and right in the array A 
     
    result <- 0
    for i <- left to right:
        result <- result + A[i]
    return result

In this solution, the update operation takes O(1) time and sum operation takes O(n) time. The space requirement is O(1).

4. Prefix Sum Solution

In order to have a faster sum operation, we can use the prefix sum approach. For the input array of numbers A = \{A_1, A_2, ..., A_n\}, the prefix sum at index i is the sum of the prefix numbers ending at i:

Rendered by QuickLaTeX.com

Based on the prefix sum definition, we can calculate a range sum with two prefix sums:

Rendered by QuickLaTeX.com

Given an array of numbers A = \{A_1, A_2, ..., A_n\}, let’s first construct a prefix sum array from A:

algorithm PrefixSum(A, n):
    // INPUT
    //    A = a number array with size n
    // OUTPUT
    //    the prefix sum array of A

    prefix[0] <- 0

    for k <- 1 to n:
        prefix[k] <- prefix[k - 1] + A[k]

    return prefix

For the sum operation, we can directly answer the query with two prefix sum values. However, we need to update the prefix sum array for the update operation:

// In both functions:
//    A = a number array with size n

function update(i, value):
    // INPUT
    //    left = the left index of the range to sum
    //    right = the right index of the range to sum
    // OUTPUT
    //    The sum of elements between left and right in the array A using prefix sum

    delta <- value - A[i]
    for k <- i to n:
        prefix[k] <- prefix[k] + delta
    A[i] <- value

function sum(left, right):
    // INPUT
    //    left = the left index of the range to sum
    //    right = the right index of the range to sum
    // OUTPUT
    //    The sum of elements between left and right in the array A using prefix array
    return prefix[right] - prefix[left - 1]

In this solution, the update operation takes O(n) time and sum operation takes O(1) time. The space requirement is O(n) as we need an array to store prefix sums.

5. Fenwick Tree Solution

For the brute force and prefix sum solutions, either update or sum operation takes O(n) time. If there are multiple update and sum operations, these two solutions will take a lot of time. For example, if we have O(n) numbers of update and sum operations, the overall time complexity will be O(n^2) for both solutions.

We can use a Fenwick tree to solve this problem more efficiently, as it only takes O(logn) time for both update and sum operations. Therefore, if we have O(n) numbers of update and sum operations, the overall time complexity will be O(nlogn).

5.1. Range of Responsibility

When we make an update operation, we have an input index parameter, i, to indicate the update element location. Similarly, when we make a prefixSum operation, we have an input index parameter, i, to indicate the sum of the prefix numbers ending at i. In the Fenwick tree solution, we do both operations based on the binary form of the input index i. That’s the reason why we also call it a binary index tree.

In a Fenwick tree, each index has a range of responsibilities. We calculate the range of responsibility value based on the position of the rightmost set bit (RSB) in the binary representation of the index. For example, the binary representation of 11 is (1011)_2. The range of responsibility of 11 is then 1 as its RSB gives value (1)_2 = 1. Another example of a range of responsibilities is for the number 12 =(1100)_2. The range of responsibility of 12 is 4 as its RSB gives value (100)_2 = 4.

5.2. Range of Responsibility Calculation

In computer science, we use the two’s complement method to produce a negative number from a positive number. Firstly, we reverse the ones and zeros of the binary representation of the positive number. Then we add one. Therefore, we can calculate the range of responsibility value of an index \textbf{i} with the bit operation: \textbf{i \& (-i)} .

For example, the binary value of 12 in an 8-bit form is (0000\, 1100)_2. After we reverse each bit, we have (1111\,0011)_2. When we add 1, every bit 1 starting at the right will overflow into the next higher bit until we reach a 0 bit, which is the RSB of the original positive number. Therefore, we can have -12 = (1111\, 0100)_2.

When we do bitwise AND operation on the two numbers, we can get the range of responsibility value: 12 \,\& \,(-12) = (0000\, 1100)_2 \,\& \,(1111\, 0100)_2 = (0000 \,0100)_2 = 4.

Let’s define the range of responsibility calculation, RSB, for an index i:

algorithm RSB(i):
    // INPUT
    //    i = an index number
    // OUTPUT
    //    Range of responsibility of i

    return i & (-i)

5.3. Fenwick Tree Structure

The basic idea of the Fenwick tree solution is to precompute the responsibility range sum for each index. Then, we can calculate the prefix sum of an index i based on the precomputed Fenwick values. Also, when we update the element at an index i, we can only update those precomputed Fenwick values that cover the index i.

Let Fenwick[i] denote the responsibility range sum for each index i. For the array A = \{A_1, A_2, ..., A_n\}, we can have have an array Fenwick where

Rendered by QuickLaTeX.com

The following table shows the Fenwick values for numbers from 1 to 16:

Number

Binary Representation

RSB

Fenwick

1

(0000\,0001)_2

(1)_2= 1

sum(A_1)

2

(0000\,0010)_2

(10)_2= 2

sum(A_1, A_2)

3

(0000\,0011)_2

(1)_2= 1

sum(A_3)

4

(0000\,0100)_2

(100)_2= 4

sum(A_1, A_2, A_3, A_4)

5

(0000\,0101)_2

(1)_2= 1

sum(A_5)

6

(0000\,0110)_2

(10)_2= 2

sum(A_5, A_6)

7

(0000\,0111)_2

(1)_2= 1

sum(A_7)

8

(0000\,1000)_2

(1000)_2= 8

sum(A_1,A_2,...,A_8)

9

(0000\,1001)_2

(1)_2= 1

sum(A_9)

10

(0000\,1010)_2

(10)_2= 2

sum(A_9, A_10)

11

(0000\,1011)_2

(1)_2= 1

sum(A_11)

12

(0000\,1100)_2

(100)_2= 4

sum(A_9, A_10, A_11, A_12)

13

(0000\,1101)_2

(1)_2= 1

sum(A_13)

14

(0000\,1110)_2

(10)_2= 2

sum(A_13, A_14)

15

(0000\,1111)_2

(1)_2= 1

sum(A_15)

16

(0001\,0000)_2

(1\,0000)_2= 16

sum(A_1,A_2,...,A_16)

Based on the Fenwick value definition, we can see that one Fenwick value can cover several Fenwick values. For example, Fenwick[8] = sum(A_1,A_2,...,A_8) covers Fenwick[4]=sum(A_1, A_2, A_3, A_4), Fenwick[6] = sum(A_5, A_6) and Fenwick[7] = sum(A_7). We can use a tree structure to represent the coverage relationships:

Rendered by QuickLaTeX.com

In this Fenwick tree structure, leaf nodes are the index numbers. Each internal node represents a Fenwick value that can be constructed from its children Fenwick values and its own index array number. For example:

    [Fenwick[16] =Fenwick[8]+Fenwick[12]+Fenwick[14]+Fenwick[15]+A_{16}]

5.4. Fenwick Tree Construction

To construct a Fenwick tree, we can use a dynamic programming approach by propagating the smaller Fenwick values to the big Fenwick values:

algorithm ConstructFenwick(A, n):
    // INPUT
    //    A = a number array with size n
    // OUTPUT
    //    fenwick = the Fenwick array of A

    fenwick <- A

    for i <- 1 to n:
        parent <- i + RSB(i)
        if parent <= n:
            fenwick[parent] <- fenwick[parent] + fenwick[i]

    return fenwick

In this algorithm, we first initialize the Fenwick array with the input array A. Then, we use a loop to propagate the smaller Fenwick values to their parent Fenwick values. The time complexity is O(n).

We only need to construct the Fenwick array once at the beginning. In the future, we only need to update at most O(logn) Fenwick values in an update operation.

5.5. Prefix Sum Calculation

When we compute the prefix sum of index i, we can start from index i and go downwards until we reach 0:

algorithm PrefixSum(i):
    // INPUT
    //    i = an index
    //    fenwick = the Fenwick tree of array A
    // OUTPUT
    //    The prefix sum of A ending at index i

    result <- 0
    
    while i > 0:
        result <- result + fenwick[i]
        i <- i - RSB(i)
    
    return result

In this algorithm, we start from the input index i and add its Fenwick value to the result. Then, we remove the RSB of i and add the new Fenwick value into the result. We keep doing this process until we reach index 0.

Suppose we want to find the prefix sum for index 11 = (1011)_2. Firstly, we add Fenwick[11] into our result. Then, we subtract the RSB value of 11, which is 1, and reach a new index 10=(1010)_2. Therefore, we add Fenwick[10] into our result. Again, we subtract RSB(10) = 2 from 10 and get a new index 8=(1000)_2. Similarly, we add Fenwick[8] into our result. Finally, we subtract RSB(8)=8 from the current index 8 and stop the loop as we reach the index 0.

In the end, we can have prefixSum(11) = Fenwick[11] + Fenwick[10] + Fenwick[8].

The time complexity of this algorithm is O(logn) as we remove one set bit of the original index i in each iteration until we reach 0.

5.6. Fenwick Tree Update

The update operation is the opposite of prefixSum operation. We start from the input index i and go upwards along the tree path to propagate the update operation.

Suppose we want to add a delta value at the location 3. We can first add delta to fenwick[3]. Then, we get its parent based on the RSB(3) and reach the index 4. Therefore we also add delta to fenwick[4]. Similarly, we continue to update the parent Fenwick values like Fenwick[8] and Fenwick[16] until we reach the array size boundary n:

algorithm UpdateFenwickTree(i, delta):
    // INPUT
    //    i = an index to update
    //    fenwick = the Fenwick tree of array A
    //    delta = the value to add
    // OUTPUT
    //    Fenwick tree is updated with the delta value at index i

    while i <= n:
        fenwick[i] <- fenwick[i] + delta
        i <- i + RSB(i)

Similar to the prefixSum, the time complexity of add is O(logn).

5.7. Fenwick Tree Solution

We can combine the above functions to solve the mutable range sum query problem:

// In both functions:
//    A = a number array with size n

function update(i, value):
    // INPUT
    //    i = index in array A where update occurs
    //    value = the new value to update at index i
    // OUTPUT
    //    Updates the Fenwick tree and array A
    delta <- value - A[i]
    add(i, delta)
    A[i] <- value

function sum(left, right):
    // INPUT
    //    left = the left index of the range to sum
    //    right = the right index of the range to sum
    // OUTPUT
    //    The sum of elements between left and right in the array A using Fenwick Tree
    return prefixSum(right) - prefixSum(left - 1)

In the update function, we first calculate the delta of the updated value, Then, we call the add function to update the Fenwick tree. The time complexity is O(logn) as we only call the add function once.

In the sum function, we call prefixSum function twice to get the sum between left and right. The overall time complexity is still O(logn).

The space complexity of the Fenwick solution is O(n) as we need to store the Fenwick values for all the indexes.

6. Conclusion

In this article, we showed how to use a Fenwick tree to solve the mutable range sum problem. With the Fenwick tree, we can achieve O(logn) time for both update and sum operations.