931. Range Sum Query — Segment Tree Build

Given an integer array and a list of range queries, each query [l, r] asks for the sum of elements from index l to r inclusive. Build a segment tree (or prefix sums) and return the answer to each query 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,3,5,7,9,11],"queries":[[0,2],[1,4],[0,5]]}
Output: [9,24,36]
Explanation: Range sums for each query.

Input: {"nums":[2,4,6],"queries":[[0,0],[0,2],[1,2]]}
Output: [2,12,10]
Explanation: Various ranges.

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

Constraints

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

Asked by