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
jareehd:
20191001 08:25:48
learn new concept


sapient:
20190826 14:57:37
How can this be solved using binary search ? 

aroder:
20190129 16:55:46
simple bit tree implementation... AC in one go!!


phoemur:
20181012 20:42:45
segTree works fine... 

madhur4127:
20180723 06:14:13
@spojabhi, spoj uses 4 bytes of int, and it suffices for this problem, no long long int required. 

rajcoolaryan:
20180620 18:05:59
square root decoposition rocks ..


anirudnits:
20180614 18:54:06
segTree > TLE


a_98:
20180425 21:49:04
Good Implementation of Fenwich Trees 

draco_malfoy:
20171230 07:55:33
AC in one go :)


spojabhi:
20171219 11:38:54
use long long int .

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 