AKVQLD03  How to Handle the Fans
Trey Parker and Matt Stone, the creators of “South Park” are having some problems handling their fans. The number of fans is so huge that can’t even count them properly. So they hired “N” employees for counting the fans. All the “N” employees had their own separate offices and they were located in a straight line with positions numbered as 1, 2, 3 … up to N. Fans can come to the office of any employee at any time and tell them how they feel about the show and if they are lucky enough, they may get to meet Trey Parker and Matt Stone.
All the employees keep on updating Trey and Matt about the number of fans currently in their offices, so at each moment, they will have a list of “N” positions and the number of fans in each of these positions. Trey and Matt suddenly start taking a walk from office at position “A” to position “B” to meet their fans, but before they start walking they want to know the sum of all the fans in the offices from position “A” to “B”. But counting them one by one is taking a lot of time, so now they hired you, an awesome software engineer to do this task. Your task is to find the sum of all the fans present in the offices between positions “A” to “B” ("A" and "B" inclusive). Let’s see if you could do it fast enough.
Input
The first line of Input contains two integers “N” and “Q”. “N” is the no. of employees hired by Trey and Matt. “Q” is the no. of queries to be followed.
Each of the next “Q” lines contain a query. A query can be of two types:
“add P F” – this means that “F” no. of fans came to the office at Position “P”
“find A B” – this means that Trey and Matt wants to know the sum of fans present at offices at positions “A” to “B”
Output
For each query of the type “find A B”, output the sum of fans present at offices at positions “A” to “B” in a different line.
Constraints
1 <= N <= 10^6
1 <= Q <= 10^5
1 <= A < B <= N
1 <= P <=N
1 <= F <= 10^4
Example
Input:
10 10
find 1 5
add 5 8
add 6 2
find 4 5
find 4 6
add 2 4
find 2 6
add 6 7
find 1 6
find 7 10
Output:
0
8
10
14
21
0
hide comments
anubhav1772:
20170721 19:33:56
Yayy!! ac in 1 go :) Last edit: 20170721 19:34:19 

pranav0123:
20170522 21:29:36
Can anyone please find why I am getting runtime error with this segment trees implementation. Submission id: 19459839 

krishna_sai:
20170330 07:27:33
spoj says my program has compilation error while its working fine in ideone and codeblocks? Any thing I am overlooking?


vigneshkv:
20161231 11:06:55
simple Binary Indexed Tree .. you can watch the tutorial on youtube. 

malibarbar:
20160808 09:32:26
easy segment tree but got wa because next line 

xinnix:
20160702 16:06:36
Wow... Easy seg tree.... No need to use bit 

atif_11:
20160508 23:29:37
Good implementation of Binary Index Tree... 

gautam:
20160310 02:22:28
easy ..ac in one go;) 

rahul2907:
20160119 14:24:56
BIT easy one :)


Anubhav Gupta:
20151104 12:24:33
Easy BIT 
Added by:  Ankit Kumar Vats 
Date:  20130724 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Self 