Fenwick Tree Problem Statement

You are provided with an array/list ARR consisting of 'N' integers, along with 'Q' queries. Each query can be of one of the following two types:

  • Type 1 (Range Sum): Given two integers 'L' and 'R' (0 ≤ L ≤ R < N), compute the sum of all elements in the array with indices in the range ['L', 'R'] inclusive.
  • Type 2 (Point Update): Given an index 'i' and a value 'X', update the value of ARR[i] to 'X'.

Your task is to execute these queries on the given array and return the required outputs for each query.

Input:

The first line contains an integer 'T', representing the number of test cases.
The first line of each test case contains a single integer 'N', indicating the number of elements in the array.
The second line of each test case contains 'N' space-separated integers representing 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 three space-separated integers, which are:
1. The first integer indicating the type of query, either '1' for a range sum query or '2' for an update query.
2. For query type '1', the second and third integers are 'L' and 'R', representing the range for the sum calculation.
3. For query type '2', the second integer is 'i', the index to update, and the third integer is 'X', the new value at index 'i'.

Output:

For each query of type 1, output the sum of the array values with indices in the range 'L' and 'R'.
Do not output anything for query type 2; simply perform the update on the array.

Example:

Input:
1
5
3 2 1 4 5
3
1 1 3
2 2 6
1 1 3
Output:
7
9

Constraints:

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 105
  • 1 ≤ Q ≤ 105
  • -109 ≤ ARR[i] ≤ 109

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

UREVENUKA SHIVAJI
6mo
-1
Vignesh N
2y

I want this answer immediately

Help your peers!
Add answer anonymously...
Amazon Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
Awards 2025
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits
Stay ahead in your career with AmbitionBox app