Updates

[2026.5.30] 新增了 8 组数据卡掉了优化后的暴力（$n=10^5$），并将题目名称直接修改为 [模板] 一维前缀和。
[2026.5.31] 新增了 30 分部分分

题目背景

年糕所在的班级一共有 $n$ 个人，大家刚刚进行了期末考试，第 $i$ 个同学的分数为 $a_i$。
为了方便统计，老师把所有同学分成了 $k$ 个小组，每个小组成员的编号为 $l_i$ 到 $r_i$。
现在，请你帮助年糕统计出每个小组的分数和（一个人可能同时存在于多个小组。）

题目描述

给定 $n$ 个整数，现有 $k$ 个询问，请你求出 $l_i$ 到 $r_i$ 的区间和。

输入格式

第一行输入两个整数 $n,k$。
第二行输入 $n$ 个整数。
接下来 $k$ 行 $k$ 个询问，每行输入两个整数 $l_i$ 和 $r_i$。

输出格式

对于每个询问，输出一个整数，表示 $l_i$ 到 $r_i$ 的区间和。

输入输出样例

5 3
90 80 70 100 60
1 3
2 4
5 5

240
250
60

说明/提示

数据范围

子任务 1：30 分，$1≤n≤10^2,1≤k≤20$
子任务 2：70 分，$1≤n≤10^5,1≤k≤10^3$

对于 $100\%$ 的数据，$1≤l_i≤r_i≤n$，$0≤a_i≤100$