Problem

Submissions

Hints & solutions

Discuss

Fenwick Tree

Moderate

0/80

Average time to solve is 15m

Contributed by

2 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

Sample Output 1 :

11
8
14

Explanation of The Sample Input 1:

The first line has a single integer which means it's a single test case.
The next line has an integer 5 denoting that there are 5 integers in the array.
Then the 5 space-separated integers in the third line represent the elements in the array.
Then the fourth line has ‘Q’ which is the number of queries. In this case, we have 5 queries.
Then the 5 queries follow:

We can see that the first query is of type 1 i.e a range sum query. From the second and third integer we get we need to find the sum of the elements at index 0 1 and 2 i.e the first 3 elements. We can see that the sum will be 5+4+2=11 and hence we print 11.

The next query is of type 2 so we need to update the element at index 1 to 1. So the array after updating will be {5 1 2 3 5}. Note that we do not print anything.

The next query is of type 1 from index 0 to 2. Now the sum will be 5+1+2=8 hence we print 8 in a new line.

The next query is of type 2 in which the element at index 3 is updated to 1. After updating, the array is: {5 1 2 1 5}.

The last query is of type 1 and we need to find the sum of all 5 elements which will be: 5+1+2+1+5=14. Hence we print 14 in a new line.

Sample Input 2 :

2
9
12 20 10 15 16 11 19 10 10 
6
1 3 5
1 7 7
1 4 5
2 1 27
2 7 23
2 5 12
9
18 19 19 10 17 18 19 10 14 
7
2 4 25
1 4 8
1 7 7
2 5 15
2 8 14
1 4 5
2 0 4

Sample Output 2 :

Hint 1

Hint 2

Try to iterate the array and perform the operations directly.

Approaches (2)

Approach 1

Approach 2

Brute Force 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.

Time Complexity

O(Q * N), Where ‘N’ denotes the number of elements in the given sequence and ‘Q’ denotes the number of queries.

In the worst case if all are sum queries spanning the whole array, it will take time of order of Q * N.

Space Complexity

O(1), we are using constant space.

(100% EXP penalty)

Fenwick Tree

Console