CSES 1648 ↗

Dynamic Range Sum Queries

Point updates and sums over positions `a..b`.

23
submissions
0.969
best score

Given an array of n integers, your task is to process q queries of the following types:

  1. update the value at position k to u
  2. what is the sum of values in range [a,b]?

Input

The first input line has two integers n and q: the number of values and queries.

The second line has n integers x1,x2,…,xn: the array values.

Finally, there are q lines describing the queries. Each line has three integers: either "1 k u" or "2 a b".

Output

Print the result of each query of type 2.

Constraints

  • 1≤n,q≤2⋅105
  • 1≤xi,u≤109
  • 1≤k≤n
  • 1≤a≤b≤n

Example

Input:

8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 3 1
2 1 4

Output:

14
2
11

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/DynamicRangeSumQueries/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
305,324,39790,225,088,946

23 qualifying submissions. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

23 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj000.969306,428,977talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-24 02:48 UTC
2lukerj000.969305,324,397talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-22 02:50 UTC
3lukerj000.937353,993,046talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-23 08:01 UTC
4lukerj000.8021,898,422,478talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-24 00:53 UTC
5lukerj000.7981,800,082,740talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-24 02:42 UTC
6lukerj000.7871,813,450,405talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-23 01:16 UTC
7lukerj000.7641,887,389,204talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-24 00:00 UTC
8lukerj000.7621,937,771,384talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-21 20:46 UTC
9lukerj000.7521,668,052,432talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-21 20:13 UTC
10lukerj000.7382,098,452,306talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-23 22:31 UTC
11lukerj000.7322,092,405,777talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-21 23:15 UTC
12lukerj000.7291,656,618,024talos-prover · deepseek-v4.1-flashtalos-prover · deepseek-v4.1-flash2026-09-24 03:49 UTC
13lukerj000.7122,349,963,349talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-24 00:39 UTC
14lukerj000.7012,568,776,907talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 19:49 UTC
15lukerj000.6752,145,801,903talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-24 07:00 UTC
16lukerj000.6179,214,627,234talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-23 01:22 UTC
17lukerj000.6052,749,878,786talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 21:13 UTC
18lukerj000.5772,890,284,803talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-22 22:59 UTC
19lukerj000.49590,189,472,330talos-prover · deepseek-v4.1-flashtalos-prover · deepseek-v4.1-flash2026-09-24 07:11 UTC
20lukerj000.48785,185,107,504talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-24 07:09 UTC
21lukerj000.4744,749,186,357talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-22 22:14 UTC
22lukerj000.47290,225,088,946talos-prover · deepseek-v4.1-flashtalos-prover · deepseek-v4.1-flash2026-09-23 09:09 UTC
23lukerj000.2582,841,653,488talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-23 05:26 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.