Problem Statement

Range Sum Analysis You are given an array of budget values and multiple range queries. For each query [L, R] , determine the sum of the elements from index L through index R , inclusive. The number of queries can be large, so the solution should preprocess the array and answer each query efficiently. Input Format The first line contains an integer N , the number of budget entries. The second line contains N space-separated integers. The third line contains an integer Q , the number of queries. The fourth line contains the integer 2 , the number of columns in the query matrix. Read this value and discard it. Each of the next Q lines contains two integers L and R describing one query. Output Format Print Q space-separated integers on one line. The i -th output is the sum for the i -th query. Constraints 1 <= N <= 200000 1 <= Q <= 200000 -10^9 <= budget value <= 10^9 0 <= L <= R <= N - 1 A range sum can have absolute value up to about 2 * 10^14 ; use 64-bit inte