枚举 · 例5-【模板】静态区间和（前缀和）
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\hspace{15pt}对于给定的长度为 n 的数组 \{a_1,a_2,\dots,a_n\} ，你需要构建一个能够维护区间和信息的数据结构，使得其能支持：
\hspace{22.5pt}\bullet\区间和查询：输出 [l,r] 这个区间中的元素之和，即 \sum_{i=l}^r a_i 。

输入描述:

\hspace{15pt}第一行输入两个整数 n,q \left( 1 \leqq n,q \leqq 10^6\right) 代表数组中的元素数量、操作次数。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left( -10^9 \leqq a_i \leqq 10^9 \right) 代表初始数组。
\hspace{15pt}此后 q 行，每行输入两个整数 l, r \left( 1 \leqq l \leqq r \leqq n \right) 代表区间和查询。

输出描述:

\hspace{15pt}对于每一次询问，输出一行一个整数代表区间和。
示例1

输入

复制 
3 2
1 2 4
1 2
2 3

输出

复制 
3
6