PSEGTREE - Make Versions in Segment Tree

no tags 

You have an array of N integers, named Version-0 array.
You need to do Q queries. There are 2 type of queries.

  1. idx pos v: Take Version-idx array and copy it into another array. Name the new array Version-K array where K = (number of queries of 1st type before this query + 1). Then add v the element at index pos in Version-K array.
  2. idx l r: In Version-idx 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 Version-0 array. Each element is non-negative 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 Version-idx 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: 2020-06-04 17:44:56

Thanks @Arefin.Implemented basic persistent seg-tree successfully!

mahbubkuet08: 2019-03-20 07:59:14

Problem statement didn't mention maximum number of queries. max value of Q.

malviyanshiv: 2018-12-22 12:55:31

The query is to add the new value, not just replace it with the new value.

shaktisingh: 2018-01-19 18:09:53

@forhad__sidhu apparently, updating by v means adding v to the element.

sharif ullah: 2017-09-23 04:55:37

i think ,,,,,out[ut of query(2,3,2,3) is wrong ,isn't it is 20 ??

Last edit: 2017-09-23 04:56:12

Added by:Rezwan
Date:2017-08-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All