Range Sum Query – Mutable

Problem statement

A stock dashboard maintains item counts that can be corrected during the day. It must answer totals over consecutive shelves after applying all earlier corrections, without rebuilding every prefix sum each time. Your task Support update index value, which assigns a new value at that index, and sum left right, which returns the inclusive range sum. Use O(log n) time per operation. Important details Updates replace the previous value rather than adding to it. Queries observe all preceding updates and none of the later ones. A segment tree or Fenwick tree can support both operations efficiently; use 64-bit sums. Worked example For [1, 3, 5], sum 0 2 returns 9. After update 1 2, the same query returns 8.

Input format

First line: n q. Next line: n values. Next q lines: update index value or sum left right.

Output format

Print one result per sum query; print EMPTY if there are none.

Constraints

1 <= n, q <= 30000; -1000000000 <= values <= 1000000000; all indices and ranges are valid.

Sample input

3 3
1 3 5
sum 0 2
update 1 2
sum 0 2

Sample output

9
8