Last Updated: 7 Jan, 2021

Fenwick Tree

Moderate

Asked in companies

Solve now

Problem statement

You are given an array/list 'ARR' of ‘N’ integers, and ‘Q’ queries. Each query can be of two types:

Given 2 integers ‘L’,’R’ ( L>=0 and R<N ) find the sum of all the elements of the array with the index in the range 'L' and 'R' (inclusive). This is a query of type range sum.

Given an index ‘i’ update the value of ARR[i] to a given integer ‘X’. This is a query of type point update.

Your task is to perform the queries on the given array and return the desired output for each query.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array.

The second line of each test case contains ‘N’ space-separated integers denoting the array ‘ARR’.

The third line of each test case contains an integer ‘Q’ denoting the number of queries.

The next ‘Q’  lines of each test case contain 3 space-separated integers denoting the following:

     1. The first integer denotes the type of query. It can be either a ‘1’ or a ‘2’. 1 denotes range sum type query and 2 denotes update type query.

     2. If the query is of the first type, the second and third integers on the same line denote ‘L’ and ‘R’ respectively which are the range of which we need to calculate its sum.

     3. If the query of the second type, the second integer denotes ‘i’ the index of which the value is to be updated and the third integer denotes ‘X’ the updated value of the ‘i-th’ index.

Output format :

For each query of the first type, print the sum of values with indices in the range of ‘L’ and ‘R’.

For queries of the second type, do not print anything just update the value in the given array.

Note:

You don't need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
1 <= Q <= 10^5
-10^9 <= ARR[i] <= 10^9


Where ‘N’ denotes the length of the array 'ARR', 'Q' denotes the number of queries, and ‘ARR[i]’ is the value of the element at index ‘i’.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The key idea of the approach is to process the queries as asked. i.e If range sum is asked we do a range sum using a loop and update the values in the array if it is an update query.
Update will be a constant time operation but range sum can take time of order of ‘N’ .

We can take the following approach:

For queries of type 1, we take a loop and iterate from ‘L’ to ‘R’ to find the sum and print it.
For queries of type 2, we simply update the value in the array of that index.

Solve now

02 Approach

The idea is to do the given queries efficiently. We can do this in many different ways. One of them is using a Fenwick tree or a binary indexed tree.

The key idea of a Fenwick tree is that any number can be represented as the sum of powers of 2.
We can use this property to find sum of elements in at max of log(n) calculations.
For example, let us assume that we need to find the sum of first 7 elements .

We know that 7=2^2+2^1+2^0. So it to find sum of first 7 elements we can just find sum of first 4 then next 2 then then the last element .

To find sums efficiently, let Let ‘P(K)’ denote the largest power of two that divides ‘K’. We store a binary indexed tree as an array tree such that
‘TREE[K]’ = ‘sum(K − 2^Q + 1, K)’, where ‘sum(L , R)’ represents the sum of elements from index ‘L’ to ‘R’ and ‘Q’ is the position of the least significant bit of ‘K’.
consider index 6, its binary representation would be 110. The least significant set bit is at pos 1. The so ‘TREE[6]’ store the information about the range 6 - 2¹ + 1 = 5 to 6.
For example, consider the following array:

The Fenwick tree for the above array will be:

We can see that the 2nd index stores the sum of the first and second elements. The fourth has the sum of all 4 elements. The 6th element has the sum of the 5th and 6th elements. The following diagram shows this more clearly:

Taking the same example, the sum of first 7 elements will be :
sum(1,7)=sum(1,4)+sum(5,6)+sum(7,7) = 16+7+4 = 27.
The following diagram shows more clearly:

The shaded boxes show the numbers we calculated the sum.
Ok, so some are sorted what about the update?
Well obviously storing the array in the form of a tree won't make the update a constant time operation but it makes it a log(n) operation.
How? Well, we see that every index contributes to log(n) ranges where n is the number of elements and we need to only update only those ranges.
For example, if we want to update index 3 the following ranges need to be updated.

log(8) is 3 and we can clearly see that we need to update 3 ranges.

Keeping in mind the above points we can take the following approach:

Make a class ‘FenwickTree’ which takes care of all the sum and update operations.
The sum operation i.e sum(1, ‘R’) can be simply done by finding the set bits in ‘R’ and adding ‘TREE[R]’ to the sum. This can easily be done using a loop.
For the update operation, we need to find all the ranges which have the index which we are updating.
We do this by simply isolating the last set bit of the number and adding it to the number until our number is less than or equal to the size of the array.
For example, in the case of updating the index 3, we will find the last set bit of 3 (101) which is 1 so we update 3 and add 1 to 3 which will be 4. So we need to update 4 too.
We update 4 and then we take out the last significant bit of 4 (100) which is 4.
4+4=8 so we need to update the 8th index too.
After updating the sum on index 8, we are done with all the updates as the next iteration will be greater than the size of the array.
We process the queries one by one and print the answer.

Solve now