anotherandres
BAN USER- -6of 10 votes
AnswersSuppose we have array of N numbers. We will define N functions on this array. Each function will return the sum of all numbers in the array from Li to Ri ( Li is left index, Ri is right index). Now we have 2 types of queries:
- anotherandres in United States
Type1: 1 x y Change the xth element of the array to y
Type2: 2 l r Return the sum of all functions from m to n.
Input type:
First Line is the size of the array i.e. N
Next Line contains N space separated numbers Ai denoting the array
Next N line follows denoting Li and Ri for each functions.
Next Line contains an integer Q , number of queries to follow.
Next Q line follows , each line containing a query of Type 1 or Type 2
Here is an example:
Input:
5
1 2 3 4 5
1 2
3 4
1 4
1 5
3 5
5
1 1 5
2 2 4
2 1 3
1 4 5
2 1 5
Output:
40
28
63
Explanation:
Function 1 is sum of values from index 1 to index 2 = 1+2=3
So , F1=3
Similarly, F2=3+4=7
F3=1+2+3+4=10
F4=15
F5=12
Now when I query 1 1 5
means it is type 1 query, so we replace value at index 1 by 5.
So our new array is,
5 2 3 4 5
and
F1=7
F2=7(unchanged)
F3=14
F4=19
F5=12(unchanged)
Then next query is 2 2 4
means give sum of all functions from index 2 to 4.
So, ans= 7+14+19 =40 (output 1)
Similarly are other 2 outputs.
Index are 1 based in example.
Comment me if you are not clear with question.
Edit: I know one can do it with naive approach or using segment tree. But they wanted more faster way to do it.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm
I have explained in the question.
- anotherandres November 12, 2014