Partial sums P70578


Statement
 

pdf   zip

html

Given an array A[0  ..  n−1] and an index i, the i-th partial sum of A is ∑0≤ j≤ i A[j]. Here, you have to implement a data structure to efficiently compute partial sums. The operations you must consider are the creation of an array with all its values initialized to zero, the modification of a value, and the query of a partial sum.

Input

Input consists of a non-empty sequence of commands. Every command begins with a letter to identify it, followed by one or two integer-number parameters. These are the possible commands:

  • “r n” resets (or creates) an array of n integer numbers to zero. Assume 1 ≤ n ≤ 105.
  • “s i x” sets the possition i to x. Assume 0≤ i< n and −100≤ x≤ 100.
  • “g i” gets (and prints) the i-th partial sum. Assume 0≤ i< n.

In general, there are much more set and get commands than reset commands. The first command is always a reset.

Output

For each get command, print the corresponding partial sum. Print the output corresponding to each reset command on a unique line, separated by spaces.

Public test cases

  • Input

    r 8
s 0 3    s 1 2    s 2 1    s 3 5    s 4 4    s 5 3    s 6 2    s 7 3
g 0      g 1      g 2      g 3      g 4      g 5      g 6      g 7
s 3 8             g 2      g 7
s 3 -100          g 0      g 7
r 3
s 1 4
g 0      g 1      g 2      g 0

    Output

    3 5 6 11 15 18 20 23 6 26 3 -82
0 4 4 0
    • Information
    Author
    Jordi Petit
    Language
    English
    Official solutions
    C++
    User solutions
    C++