Segment Tree — Point Update and Range Sum

Practice this coding question on Coding Gurukul.

Problem statement

Given an array, implement a segment tree for these commands: - SET i x: replace a[i] with x. - SUM l r: print a[l] + a[l+1] + ... + a[r]. Indices are zero-based and both range endpoints are included. SET replaces the value; it does not add to it. Only SUM prints output. Values may be negative. Use signed 64-bit sums and O(log n) time per command. Worked example For [2, 4, 6], SUM 0 2 prints 12. SET 1 -3 changes the array to [2, -3, 6]. SUM 1 2 then prints 3.

Input format

First line: n q. Second line: n integers. Next q lines: SET i x or SUM l r.

Output format

Print each range sum on its own line.

Constraints

1 <= n,q <= 100000; -10^9 <= initial values,x <= 10^9; 0 <= i < n; 0 <= l <= r < n. At least one SUM.

Sample input

3 3
2 4 6
SUM 0 2
SET 1 -3
SUM 1 2

Sample output

12
3

Sign in to run or submit a solution in C++, Java or Python.