Range Sum Query - Immutable（区间求和 · 不可变数组）

题目描述

给定一个长度为 (n) 的整数数组 nums，需要回答若干次区间求和查询。

每次查询给定两个整数 l 和 r，要求计算数组中从下标 l 到 r（包含两端）的所有元素之和。

即：

输入格式

第一行输入两个整数：

n q

表示：

• (n)：数组长度
• (q)：查询次数

第二行输入 (n) 个整数：

nums_0 nums_1 ... nums_{n-1}

表示数组元素。

接下来 (q) 行，每行输入两个整数：

l r

表示一次查询。

输出格式

对于每个查询，输出一行一个整数，表示区间 ([l,r]) 的元素之和。

输入输出样例

输入

6 3
-2 0 3 -5 2 -1
0 2
2 5
0 5

输出

1
-1
-3

数据范围

1 ≤ n ≤ 10^4
1 ≤ q ≤ 10^4
-10^5 ≤ nums[i] ≤ 10^5
0 ≤ l ≤ r < n

提示

可以预处理 ​前缀和数组​：

prefix[i] = nums[0] + nums[1] + ... + nums[i]

则区间和可以在 (O(1)) 时间计算：

sum(l,r) = prefix[r] - prefix[l-1]