Fenwick Tree — Point Add and Range Sum

Practice this coding question on Coding Gurukul.

Problem statement

Given an array, implement a Fenwick tree for these commands: - ADD i x: add x to a[i]. - SUM l r: print a[l] + a[l+1] + ... + a[r]. Indices are zero-based and both range endpoints are included. Apply each update before processing the next command. 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. ADD 1 -3 changes the array to [2, 1, 6]. SUM 1 2 then prints 7.

Input format

First line: n q. Second line: n integers. Next q lines: ADD 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
ADD 1 -3
SUM 1 2

Sample output

12
7

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