You are given an array(of integers) of length n. You are required to answer q queries. Queries can be of two types 0. 0 pos val : In this you have to update arr[pos] to val. 1. 1 l r: In this query u have to find the sum of all elements in this interval. Sum of elements in interval [l, r] means sum of all arr[i] for which i is in range [l, r]. To do the above task u have to create a datastructure as follows :- Implement the SegmentTree class: 1. SegmentTree(int arr[]): Initializes the SegmentTree object with an array, 2. void update(int pos, int val): updates the arr[pos] to val, 3. int query(int l, int r): return sum of all element's in interval [l, r].
Input Format
A number n n1 n2 .. n number of elements A number q following q lines contains queries of format either of two 0 pos val, 1 l r
Output Format
for each query print a single integer in seperate line
Constraints
1. 1 <= n, q <= 10^5 2. 0 <= l <= r < n 3. 10^4 <= arr[i] <= 10^4.
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
4 1 2 3 4 9 1 0 3 0 1 3 1 0 3 1 1 2 0 2 5 1 2 3 1 0 1 1 0 2 1 1 3
Output
10 11 6 9 4 9 12