Consider the following problem: we are given an array of integer values and asked to find the range sum between index [i, j]. Note that one-based indexing is used here. This can be done easily in O(j — i) time or O(n) time in the worst case using a single loop.

But now, suppose we have to find the range sum between any two indices multiple times. Then one basic idea would be to repeat the above process every time. If there are m range sum queries, then the worst time complexity would be m*O(n), which is O(mn). This is a brute force approach! Now the critical question is: can we think of some other efficient strategy to improve the time complexity further? Think!

If we know the prefix sum of the array till index 0 to i — 1 and index 0 to j, then we can easily calculate the sum between index [i, j]. How? Here is an idea: Sum[i, j] = PrefixSum[0, j] — PrefixSum[0, i — 1]. This calculation will take O(1) time if we know both values of the prefix sum. But the critical question is: how do we handle the situation of multiple range sum queries? Do we need to calculate the prefix sum every time? The answer is no! Here is a simple idea:

- We take an extra array PrefixSum[n] and do simple preprocessing to store the prefix sum of all indexes. We can easily construct the prefix sum array using a single loop in O(n) time.
- Now to find the sum between index [i, j] we can find PrefixSum[j] — PrefixSum[i — 1] and answer any query in O(1) time.

But here is another problem: suppose we want to change the value of some element in the original array. We can do this in O(1) time. But we will now need to reconstruct the prefix sum array again, which will take O(n) time.

```
function construct_prefix_sum(array):
// O(n) time needed to construct prefix sum array
prefix_sum = [0]*(array.length + 1)
i = 1
while i <= array.length:
prefix_sum[i] = prefix_sum[i - 1] + array[i]
function range_query(i, j):
// O(1) time needed for query
return prefix_sum[j] - prefix_sum [i - 1]
function update (i, val):
//if we update index i with val, we need to construct prefix
//sum arry again. So O(n) time needed for update
array[i] = val
construct_prefix_sum(array)
```

Suppose, if there are **m** update queries and **m** range sum queries.

- The time complexity of update queries = m * time complexity of constructing prefix array = m * O(n) = O(mn).
- The time complexity of range sum queries = m * O(1) = O(m)

As we can see, there is a clear gap in the time complexity of both queries. If there are frequent update queries, this solution will take a lot of time. Now the critical question is: how do we handle this scenario and improve the time complexity of the update queries?

One solution to this problem is the idea of **Fenwick Trees,** which takes O(logn) time for both update and finding range sum. Definitely, this looks like a good tradeoff:

**Prefix array solution:**Update query time complexity = O(n), Finding range sum time complexity = O(1)**Fenwick tree solution:**Update query time complexity = O(logn), Finding range sum time complexity = O(logn)

Let’s understand the idea and solution of the problem using the Fenwick tree. Fenwick tree was first described in the paper titled “A new data structure for cumulative frequency tables” (Peter M. Fenwick, 1994). Fenwick tree is also called **Binary Indexed Tree(BIT).**

Let **arr[]** be an array of integers of length n and **f** is a sum function for finding the range sum between any two indexes l and r.

**f(arr, l, r) = arr[l] + arr[l+1] + …… + arr[r].**

Following are the specifications of the Fenwick tree data structure:

- Calculate the value of function f in the range [l, r] in O(logn) time.
- Updates the value of an element of arr in O(logn) time.
- Space complexity is O(n).

The following image represents the Fenwick tree.

A particular cell is also responsible for other cells in a Fenwick tree. The position of the first non-zero bit from right in the binary representation of the index of the cell determines the range of responsibility of that cell below itself. Let’s call this position RSB(rightmost set bit). Also, note that the positions from the right are one-based. The range of responsibility is 2^(RSB — 1).

This data structure is called a tree even though we store the data in an array as a single cell is responsible for the sum of multiple cells. The cell at index i is responsible for storing the sum of elements from (g(i), i).

- fTree[i] = sum(array[j]), where j is from g(i) to i.
- g(i) = 2^(RSB -1).

We can see that as the height of the tree is log(n), the update and query operations take log(n) time at max.

For example, the binary representation of 5 is 00101. So the range of responsibility will be 2^(1–1) = 1. For 12, the binary representation is 01100. So the range of responsibility will be 2^(3–1) = 4. The following table represents the range of responsibility for numbers from 1 to 16.

The construction of the Fenwick tree is explained later. For now, suppose we have our Fenwick tree ready.

We will first look at how to compute prefix sum up to a specific index which will eventually help us find range sum. Suppose you want to find prefix sum from 1 to i. Then you should start at index i and go downwards until you reach 0, adding the value at each index you land.

Now you want to find prefix sum up to index 5. Initialize answer with a tree[5] and i with 5. Now subtract the current range of responsibility from i, which is 1. Therefore i = i -1 i.e. i = 4 now. Again add tree[4] to the answer and subtract the current range of responsibility from i, which is 4. The index i becomes 0. So we have got prefix sum from [1,5] as our answer, which is a tree[5] + tree[4] in this case.

Similarly, do the same thing for finding prefix sum of [1, 15]. See the following table to understand how prefix sum up to 15 is calculated. The green regions are the ones that are used to find the answer.

Therefore prefixSum(15) = tree[15] + tree[14] + tree[12] + tree[8].

We need a maximum log2(n)(as the maximum number of set bits can be log2(n)) operations to find the prefix sum. Thus the time complexity of range sum is O(logn). Now you can find range sum from index [i, j] by using rangeSum[i, j] = prefixSum[j] — prefixSum[i-1].

```
function prefix_sum(i):
sum = 0
while i > 0:
sum = sum + tree[i]
i = i - RSB(i)
return sum
function range_query(i, j):
return prefix_sum(j) - prefix_sum(i - 1)
```

Where RSB(i) returns the range of responsibility of i, RSB is implemented later.

Point updates are the opposite of range queries. We will have to add the RSB to propagate the value upwards to the cells responsible for the current cell.

As you can see from the above image, if we want to update the value at index 9 by increasing the value in the original array at index 9 by x, we would have to propagate upwards from 9 to 10, 10 to 12, and 12 to 16.

So the required updates are: tree[9] += x, tree[10] += x, tree[12] += x, tree[16] += x

```
function update (i, x):
array[i] = array[i] + x
while i < n:
tree[i] = tree[i] + x
i = i + RSB(i)
```

This is the first step that you have to do before answering any range sum or point update queries. You can create a tree with all values 0 initially and then do point updates for each index which will take O(nlogn) time, but we can do better.

We can construct the tree in linear time. The idea is to add the value in the current cell to the next immediate cell that is responsible for the current cell. It resembles the method for point updates but one cell at a time. This creates a cascading effect by propagating the value in each cell throughout the tree.

Let our current position be i. The immediate position responsible for i is i + RSB(i). We can consider cell i + RSB(i) as the parent of cell i. We must ignore this update if the parent cell is out of bounds.

```
function build (array):
n = len(array)
tree = array.copy()
for i = 1 to n:
j = i + RSB(i)
if j < n:
tree[j] = tree[j] + tree[i]
return tree
```

RSB of i is i & -i. It works because the negative of a number is produced by inverting the number, then adding 1 (that’s the definition of two’s complement). When you add 1, every bit starting at the bottom will overflow into the next higher bit; this stops once you reach zero. Those overflowed bits will all be zero, and the bits above the last one affected will be the inverse of each other, so the only bit left is the one that stopped the cascade — the one that started as 1 and was inverted to 0.

The above explanation was for range queries and point updates. We can also use the Fenwick tree for range updates and point queries and range updates and range queries. I will briefly explain the modifications we need to do for each of these cases.

The Fenwick tree is initialized with zeros. Suppose we want to increment the interval [l,r] by x. We need to make 2 point update operations on the Fenwick tree: **add(l, x)** and **add(r+1, -x)**.

After these operations, the values from 0 to i < l have no effect. The values from l <= i <= r are incremented by x. And if i > r, then the second update operation will cancel the effect of the first one.

Thus, to get the value of arr[i], we take the prefix sum using the range sum method.

To handle both range updates and range queries, we require 2 Fenwick Trees, fTree1 and fTree2, initialized with zeros.

After a range update query, range_increment(l, r, delta), we would want the prefixSum(i) to have the following values depending on i:

- i < l : prefixSum(i) = 0
- l <= i <= r : prefixSum(i) = delta * (i-(l-1))
- i > r : prefixSum(i) = delta * (r-(l+1))

which we can simplify as follows:

- i < l : prefixSum(i) = 0 * i -0
- l <= i <= r : prefixSum(i) = delta * i -delta * (l-1)
- i > r : prefixSum(i) = 0 * i-(delta * (l-1)-delta * r)

Thus if we want to do a range update query, we can do it as follows:

```
function range_update(l, r, delta):
update(fTree1, l , delta)
update(fTree1, r + 1, -delta)
update(fTree2, l , delta*(l - 1))
update(fTree1, r + 1, -delta*r)
```

and, prefixSum(i) = (prefixSum(fTree1, i) * i) - prefixSum(fTree2, i).

https://gist.github.com/PrasannaIITM/53273e2ee6355e83d25ac8022ea9c554

```
class Fenwick
{
private final int n;
private int[] tree;
private int[] array;
//initialise tree
public Fenwick(int n)
{
this.n = n + 1;
this.tree = new int[this.n];
this.array = new int[this.n];
}
public Fenwick(int[] values)
{
this.n = values.length + 1;
this.array = new int[n];
for(int i = 1; i < this.n; i++)
array[i] = values[i-1];
tree = array.clone();
for (int child = 1; child < n; child++)
{
int parent = child + RSB(child);
if (parent < n)
tree[parent] += tree[child];
}
}
//update values of array[index] to val
//delta = newVal - previousVal
// zero based indexing in argument
public void update(int index, int val)
{
index += 1;
int delta = val - array[index];
array[index] = val;
int pos = index;
while(pos < n)
{
tree[pos] += delta;
pos += RSB(pos);
}
}
// increment value of array[index] by delta
// zero based indexing in argument
public void increment(int index, int delta)
{
index += 1;
array[index] += delta;
int pos = index;
while(pos < n)
{
tree[pos] += delta;
pos += RSB(pos);
}
}
// find prefixSum till index
// one based indexing in argument
public int prefixSum(int index)
{
int ans = 0;
while (index != 0)
{
ans += tree[index];
index -= RSB(index);
}
return ans;
}
// returns the rightmost set bit
private static int RSB(int i)
{
return i & -i;
}
}
class FenwickRangeQueryPointUpdate extends Fenwick
{
FenwickRangeQueryPointUpdate(int n)
{
super(n);
}
FenwickRangeQueryPointUpdate(int [] values)
{
super(values);
}
// range query from index l to r
// zero based indexing in argument
public int query(int left, int right)
{
return prefixSum(right + 1) - prefixSum(left);
}
}
class FenwickPointQueryRangeUpdate
{
private Fenwick fTree;
private int length_arr;
//initialise tree
FenwickPointQueryRangeUpdate(int n, int [] array)
{
this.fTree = new Fenwick(n);
this.length_arr = n;
for(int i = 0; i < n; i++)
{
int delta = array[i];
fTree.increment(i, delta);
if(i + 1 < length_arr)
fTree.increment(i + 1, -delta);
}
}
// increment the values from index l to r by delta
// zero based indexing in argument
public void range_update(int left, int right, int delta)
{
fTree.increment(left, delta);
if(right + 1 < length_arr)
fTree.increment(right + 1, -delta);
}
// return value of index
// zero based indexing in argument
public int point_query(int index)
{
return fTree.prefixSum(index + 1);
}
}
class FenwickRangeQueryRangeUpdate
{
private Fenwick fTree1, fTree2;
private int length_arr;
//intialise 2 Fenwick Trees
public FenwickRangeQueryRangeUpdate(int n, int [] array)
{
this.fTree1 = new Fenwick(n);
this.fTree2 = new Fenwick(n);
this.length_arr = n;
for(int i = 0; i < n; i++)
{
int delta = array[i];
fTree1.increment(i, delta);
if(i + 1 < length_arr)
fTree1.increment(i + 1, -delta);
fTree2.increment(i, delta*(i - 1));
if(i + 1 < length_arr)
fTree2.increment(i + 1, -delta*i);
}
}
// increment the values from index l to r by delta
// zero based indexing in argument
public void increment(int left, int right, int delta)
{
fTree1.increment(left, delta);
if(right + 1 < length_arr)
fTree1.increment(right + 1, -delta);
fTree2.increment(left, delta*(left - 1));
if(right + 1 < length_arr)
fTree2.increment(right + 1, -delta*right);
}
// range query from index l to r
// zero based indexing in argument
public int query(int left, int right)
{
return prefixSum(right + 1) - prefixSum(left);
}
// find prefixSum till index
// one based indexing in argument
public int prefixSum(int index)
{
return fTree1.prefixSum(index) * (index - 1) - fTree2.prefixSum(index);
}
}
```

https://gist.github.com/PrasannaIITM/68da5e7a5f879e32f61075e9c94aff6b

```
class Fenwick:
def __init__(self, length, array = []):
"""
initialise tree
"""
self.length = length + 1
self.tree = [0 for pos in range(self.length)]
if array != []:
self.array = [0] + array
#one based indexing
for i in range(1, self.length):
self.tree[i] = self.array[i]
for child in range(1, self.length):
parent = child + self.findRSB(child)
if parent < self.length:
self.tree[parent] += self.tree[child]
else:
self.array = [0 for i in range(self.length)]
def update(self, index, val):
"""
update values of arr[index] to val
delta = newVal - previousVal
(zero based indexing in argument)
"""
index += 1
delta = val - self.array[index]
self.array[index] = val
pos = index
while pos < self.length:
self.tree[pos] += delta
pos += self.findRSB(pos)
def increment(self, index, delta):
"""
increment value of arr[index] by delta
(zero based indexing in argument)
"""
index += 1
self.array[index] += delta
pos = index
while pos < self.length:
self.tree[pos] += delta
pos += self.findRSB(pos)
def prefixSum(self, index):
"""
find prefixSum till index
(one based indexing in argument)
"""
ans = 0
while index != 0:
ans += self.tree[index]
index -= self.findRSB(index)
return ans
def findRSB(self, i):
"""
returns the rightmost set bit
"""
return i & -i
class FenwickRangeQueryPointUpdate(Fenwick):
def query(self, right, left = 0):
"""
range query from index l to r
(zero based indexing in argument)
"""
return self.prefixSum(right + 1) - self.prefixSum(left)
class FenwickPointQueryRangeUpdate:
def __init__(self, length, array = []):
"""
initialise tree
"""
self.fTree = Fenwick(length, [])
self.length_arr = length
for i in range(self.length_arr):
delta = array[i]
self.fTree.increment(i, delta)
if i + 1 < self.length_arr:
self.fTree.increment(i + 1, -delta)
def range_update(self, left, right, delta):
"""
increment the values from index l to r by delta
(zero based indexing in argument)
"""
self.fTree.increment(left, delta)
if right + 1 < self.length_arr:
self.fTree.increment(right + 1, -delta)
def point_query(self, index):
"""
return value of index
(zero based indexing in argument)
"""
return self.fTree.prefixSum(index + 1)
class FenwickRangeQueryRangeUpdate:
def __init__(self, length, array = []):
"""
intialise 2 Fenwick Trees
"""
self.fTree1 = Fenwick(length, [])
self.fTree2 = Fenwick(length, [])
self.length_arr = length
for i in range(self.length_arr):
delta = array[i]
self.fTree1.increment(i, delta)
if i + 1 < self.length_arr:
self.fTree1.increment(i + 1, -delta)
self.fTree2.increment(i, delta*(i - 1))
if i + 1 < self.length_arr:
self.fTree2.increment(i + 1, -delta*i)
def increment(self, left, right, delta):
"""
increment the values from index l to r by delta
(zero based indexing in argument)
"""
self.fTree1.increment(left, delta)
if i + 1 < self.length_arr:
self.fTree1.increment(right + 1, -delta)
self.fTree2.increment(left, delta*(left - 1))
if i + 1 < self.length_arr:
self.fTree2.increment(right + 1, -delta*right)
def query(self, right, left):
"""
range query from index l to r
(zero based indexing in argument)
"""
return self.prefixSum(right + 1) - self.prefixSum(left)
def prefixSum(self, index):
"""
find prefixSum till index
(one based indexing in argument)
"""
return self.fTree1.prefixSum(index) * (index-1) - self.fTree2.prefixSum(index)
```

Please write in the message below if you find anything incorrect, or you want to share more insight. Enjoy learning, Enjoy algorithms!

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.