932. Binary Indexed Tree — Prefix Sum

Given an integer array and a list of range queries [l, r], return the sum of elements from index l to r inclusive for each query, computed via a Binary Indexed (Fenwick) Tree. Return the answers as an array, in order. The input is JSON {nums, queries}.

Input: JSON {nums, queries}.

Output: Array — the sum for each query.

Examples

Input: {"nums":[1,2,3,4,5],"queries":[[0,4],[1,3]]}
Output: [15,9]
Explanation: Range sums via BIT.

Input: {"nums":[3,1,4,1,5,9],"queries":[[0,5],[2,4],[0,0]]}
Output: [23,10,3]
Explanation: Multiple ranges.

Input: {"nums":[10],"queries":[[0,0]]}
Output: [10]
Explanation: Single element.

Constraints

• 1<=n<=10^5
• 1<=queries<=10^5
• 0<=l<=r<n

Asked by