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.