Chef and Churu

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef has recently learnt Function and Addition. He is too exited to teach this to his friend Churu. Chef and Churu are very fast friends, they share their knowledge whenever they meet. Chef use to give a lot of exercises after he teaches some concept to Churu.
Chef has an array of N numbers. He also has N functions. Each function will return the sum of all numbers in the array from L_{i} to R_{i}. So Chef asks churu a lot of queries which are of two types.Now Churu has started to solve, but Chef realize that it is tough for him to decide whether Churu is correct or not. So he needs your help , will you help him out ?
Input Format
First Line is the size of the array i.e. NNext Line contains N space separated numbers A_{i} denoting the array
Next N line follows denoting L_{i} and R_{i} 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.
1 x y : denotes a type 1 query,where x and y are integers
2 m n : denotes a type 2 query where m and n are integers
Output Format
For each query of type 2 , output as asked above.Constraints
1 ≤ N ≤ 10^{5}1 ≤ A_{i} ≤ 10^{9}
1 ≤ L_{i} ≤ N
L_{i} ≤ R_{i} ≤ N
1 ≤ Q ≤ 10^{5}
1 ≤ x ≤ N
1 ≤ y ≤ 10^{9}
1 ≤ m ≤ N
m ≤ n ≤ N
Subtask
 Subtask 1: N ≤ 1000 , Q ≤ 1000 , 10 points
 Subtask 2: RL ≤ 10 , all x will be distinct ,10 points
 Subtask 3: Refer to constraints above , 80 points
Sample Input
51 2 3 4 5
1 3
2 5
4 5
3 5
1 2
4
2 1 4
1 3 7
2 1 4
2 3 5
Sample Output
4153
28
Explanation
Functions values initially :F[1] = 1+ 2 + 3 = 6
F[2] = 2 + 3 + 4 + 5 = 14
F[3] = 4+5 = 9
F[4] = 3+4+5 = 12
F[5] = 1+2 = 3
Query 1: F[1] + F[2] + F[3] + F[4] = 41
After Update , the Functions are :
F[1] = 10 , F[2] = 18 , F[3] = 9 , F[4] = 16 , F[5] = 3
Query 3: F[1] + F[2] + F[3] + F[4] = 53
Query 4: F[3]+F[4]+F[5] = 28
Author:  devuy11 
Editorial  http://discuss.codechef.com/problems/FNCS 
Tags  datastructure, devuy11, fenwick, mediumhard, nov14, segmenttree, sqrtdecomp 
Date Added:  6102014 
Time Limit:  2.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 