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.