Consider the challenge of keeping track of a list of integers . Users of the list are interested in performing two types of operations: A A (1) Updating the value of any element in , and A (2) Calculating the sum of some sub-array . A[l..r] The length of list A is , the number of Type 1 queries is , and the number of type 2 queries is . In addition to conducting the procedures correctly, the time spent on each process must be appropriate in order to accommodate all queries. O(N) O(Q_1) O(Q_2) : Consider the following list of integers A = [1, 2, 3, 4, 5]. Example The user requests a type 1 query to increase the 2nd element of A by 3. This results in the updated list A = [1, 5, 3, 4, 5]. The user's next request is for the sum of elements in A[1..3]. This value evaluates to 9. The essence of the challenge is determining the best data structure to accommodate these kinds of needs. One such good option is the Fenwick tree, which takes logarithmic time for each query (both update and range query). The remainder of this article explores the concept behind this intriguing data structure. The first attempt at the solution Let us investigate a few potential solutions to the situation. The very natural solution is to keep only the list of integers in its original form. Any update query can be handled quickly and easily. Since the update query requires changing an element of , the request can be handled in time. The sum query, on the other hand, is dependent on the length of the interval requested. Every time a type 2 query is made, the sum had to be calculated by iterating over the range. In the worst-case scenario, the range sum query can take . When the amount of type 2 queries is small, this strategy will function efficiently. However, as the quantity of type 2 queries increases, the overall time complexity becomes . Which is quadratic in nature and hence not desirable. A A O(1) O(N) O(Q_2.N) When updates are more and range sum queries are less, maintaining only list A solves the problem. But what if is large? We would want to speed up the range sum queries. Simple observation shows that any subarray sum can be denoted as the difference of prefix sums. Here is how it is calculated - Q2 sum(A[l..r]) = sum(A[0..r]) - sum(A[0..l-1]) Thus, if we have the prefix sums pre-calculated, the range sub-query can be handled in time. Building upon this idea, let us maintain a prefix sum array for the array . Now any range query can be answered using the values present in the list . But this makes the update operation costly. Note how any change to the value of will cause us to recalculate entries in for all positions greater or equal to . Thus in the worst case, the update operation may take time. O(1) P A P A[i] P i O(n) When the number of update operations is less compared to the number of range queries, maintaining a prefix array is an efficient solution. What we just saw are two extremes of all the possible solutions. The way the Fenwick tree maintains all this data allows us to answer both types of queries in time. O(logn) Basic Idea of Fenwick Tree The idea of Fenwick Tree is to maintain a list . The length of the list is the same as that of list . Each element of the list, , stores the sum of elements of in the range to . Where falls in the range . Thus there are many choices of the function . Once the list is created, we can handle the query to find the sum of a prefix as the following procedure suggests. T T A T[i] A g(i) i g(i) [0, i] g(.) T A[0..r] def sum(r): # Sum from A[0...r] s = 0 while r >= 0: s = s + T[r] r = g(r) - 1 return s For an update query, the list T needs to be updated to accommodate an increase of in elements at index. Thus an update query will affect those index in whose range contains . The following procedures summarizes the same. delta pos j T pos def update(pos, delta): for all j where g(j) <= pos <= j: T[j] += delta return Choosing a function is the last piece of the puzzle. A smart choice of the same function helps achieve the bounds of Fenwick Tree. g() When , the list boils down to prefix sum. And, when , the list becomes exactly equal to list . g(i)=0 T g(i)=i T A Choice of Function g() in Fenwick Tree The following choice of function is made in Fenwick Tree. It is defined as is the number obtained by flipping all the trailing zeros of the number . In other words, g(i) is obtained by converting all the ones to zero when moving from Least Significant Bit (LSB) to Most Significant Bit (MSB) until a zero is obtained. This function can be written beautifully in terms of bitwise operators as . g() g(i) i g(i) = i & (i + 1) Examples - Bold numbers are in Binary g(8) = g( ) = = 8 1000 1000 g(7) = g( ) = = 0 111 000 g(23) = g( ) = = 16 10111 10000 Thus we have all the details required for handling the sum queries. But there is still a roadblock in implementing the update method. How do we find all those positions in list which are affected by the update operation? It is important to note that following the conversion of trailing ones to zero, any positions of list that become smaller than or equal to the position that is being updated, are bound to be updated too. All these numbers can be generated by replacing the least significant zero with . Continuing this process will result in all those positions which will be affected by the update query. There is a direct function for this too and it can be given as follows - T T pos 1 h(j) = j | (j + 1) Example pos = 5. Thus will be updated. T[5] h(5) = h( ) = = 7. Thus will be updated. 101 111 T[7] h(8) = h( ) = = 15. Thus will be updated. 111 1111 T[15] …. This completes the final piece of the puzzle as well. Both of the queries can now be answered in time. We will next see informal proof of this claim. O(log n) Understanding the time complexity First, let us take the sum method. For any range, we move from to to and so on until we hit . Consider a number whose least significant bit (LSB) is zero. If the number n does not have any 1s in its binary representation, we are done. So assume that number n has a 1 at a bit from left. The number n will be of kind , where is either or . Since there are no trailing ones we will have . Thus we will move from to during the loop. The number will have the following binary representation . Note that will look like . Thus in just 2 steps, the rightmost set bit in number n is unset. And since there can be at most log n set bits in a number, the loop will terminate in logarithmic number of steps. [0, r] r g(r)-1 g(g(r))-1 0 n ith n = b_1 b_2 b_3 … b_(i-1) 1 0 0 0 … 0 b_1, b_2, …, b_(i-1) 0 1 g(n) = n n n-1 n-1 n-1 = b_1 b_2 b_3 … b_(i-1) 0 1 1 1 … 1 g(n-1) g(n-1) = b_1 b_2 b_3 … b_(i-1) 0 0 0 0 … 0 If the number already has trailing zeros, then also each step will unset the rightmost set bit. Thus the entire procedure is bound to stop in logarithmic number of steps. Conclusion Using Fenwick Tree for handling point updates and range sum query is one of the many applications in which this interesting data structure finds its use. Many implementations of Fenwick Tree are available all over the internet. One such can be found . For further reading, readers are encouraged to refer to the following sources that the author has consulted while writing this article. here CP-Algorithms Wikipedia With this interesting data structure, you can solve many interesting problems. Do you know of any other data structure which can also be used to solve this problem? Answers in comments please!
