PSEGTREE  Make Versions in Segment Tree
You have an array of N integers, named Version0 array.
You need to do Q queries. There are 2 type of queries.
 idx pos v: Take Versionidx array and copy it into another array. Name the new array VersionK array where K = (number of queries of 1st type before this query + 1). Then add v the element at index pos in VersionK array.
 idx l r: In Versionidx array, sum the elements from index l to r. Print the sum of the range
Input
First line there will be an integer N (1 <= N <= 100000), the length of the array. The following line wil contain N integers, the elements of Version0 array. Each element is nonnegative and at most 100.
The next line will contain an integer Q (1 <= Q <= 100000), the number of queries. Next Q lines will contain the queries. All queries in form
a b c d
If a = 1, then you have first kind of query and idx = b, pos = c, v = d.
If a = 2, then you have second kind of query and idx = b, l = c, r = d.
For all queries, it is guaranteed that Versionidx array exists. And
1 <= pos <= N
1 <= l <= r <= N
1 <= v <= 100
Output
If you incounter an query of second type, you need to print the required sum in a seperate line. These should be printed in the order they appears in the input.
Example
Input: 10
1 2 3 4 5 6 7 8 9 10
5
2 0 1 6
1 0 10 30
1 1 2 10
1 2 3 10
2 3 2 3 Output: 21
25
hide comments
zakir068:
20200604 17:44:56
Thanks @Arefin.Implemented basic persistent segtree successfully! 

mahbubkuet08:
20190320 07:59:14
Problem statement didn't mention maximum number of queries. max value of Q. 

malviyanshiv:
20181222 12:55:31
The query is to add the new value, not just replace it with the new value.


shaktisingh:
20180119 18:09:53
@forhad__sidhu apparently, updating by v means adding v to the element. 

sharif ullah:
20170923 04:55:37
i think ,,,,,out[ut of query(2,3,2,3) is wrong ,isn't it is 20 ?? Last edit: 20170923 04:56:12 
Added by:  Rezwan 
Date:  20170828 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 