1365: 你好，求和（hard）

给定一个长度为 $n$ 的整数数组 $a$，以及 $q$ 个查询。每个查询包含两个整数 $l$ 和 $r$（表示数组的区间范围），请你计算并输出数组中从第 $l$ 个元素到第 $r$ 个元素的总和（包含 $l$ 和 $r$ 对应的元素）。

数组的下标从 $1$ 开始，且所有查询的区间均满足 $1≤l≤r≤n$。

注：本题为hard版本，与easy版本的唯一区别为数组长度小于 $10^5$。

第一行包含两个整数 $n$ 和 $q$（$1≤n,q≤10^5$），分别表示数组的长度和查询的次数。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n（-10^3≤a_i≤10^3）$，表示给定的数组。

接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$$（1≤l≤r≤n）$，表示一个查询的区间。

对于每个查询，输出一行整数，表示该区间的元素总和。

5 3
1 2 3 4 5
1 3
2 5
4 4

6
14
4