静态区间和（Static Range Sum）

问题描述

给你一个非负整数序列 $A = (a_0, a_1, \dots, a_{N-1})$，长度为 $N$。请按顺序处理以下 $Q$ 个查询：

• 给定整数 $l_i$ 和 $r_i$，输出 $\sum_{k = l_i}^{r_i - 1} a_k$。

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 5 \times 10^5$
• $0 \leq a_i \leq 10^9$
• $0 \leq l_i < r_i \leq N$

输入格式

$N\ Q$
$a_0\ \cdots\ a_{N-1}$
$l_1\ r_1$
:
$l_Q\ r_Q$

5 5
1 10 100 1000 10000
2 3
0 3
2 5
3 4
0 5

100
111
11100
1000
11111