U629404 魔法使基本：算法导论

当那扇通往不思议之国的大门缓缓开启，铃仙并未坠入奇幻纷呈的异世界，反倒像是被一股温柔的力量牵引，踏入了一座恍若梦境编织而成的图书馆。 ​ 静谧又神秘，一只白兔悠然现身，它胸前那物件，究竟是怀表，还是时钟？这奇异的景象，勾起了铃仙心底的遐想。“呵，看来我果真是踏入这不思议之国啦。”铃仙轻声自语，眼中闪烁着好奇的光芒。这时，白兔竟口吐人言，彬彬有礼道： ​ “欢迎铃仙大人莅临，此乃爱丽丝大人特意为您打造的算法乐园——**不思议之国**哟。” ​ 铃仙闻言：“爱丽丝？爱丽丝在哪里？”白兔仿佛看透了铃仙的心思，伸出爪子，携着铃仙来到图书馆中一处魔法阵前。 ​ “铃仙大人，您须得先习得魔法的基础算法，掌握区间信息的常用处理之法，如此，方能随意传送到国度的任何角落。”白兔一本正经地说道。 ​ “而这魔法之要义，便是如此：给定一个魔法数组，您需迅速算出数组中第$x$个元素至第$y$个元素之间的所有元素之和。” ​ “唯有如此，您方能引发魔法的共鸣，开启真正的冒险之旅。” ​ 言罢，铃仙深吸一口气，怀揣着对爱丽丝的憧憬与期待，踏上了那神秘的魔法阵，踏上了寻觅之旅。

**给定**： - ​ 长度为$n$的数组； - ​ $m$次询问，每次询问给出区间 $[x, y]$ 。 **要求**： - ​ 计算每次询问中数组第$x$个元素到第$y$个元素的和； - ​ $m$可能较大，可考虑优化算法，若无优化方法按常规计算亦可。

第一行包含两个整数 $n$ 和 $m$，分别表示数组的长度和查询的次数。 ​ 第二行包含 $n$ 个整数，表示给定的数组。 ​ 接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示一次查询的区间 $[x, y]$。 ​ 对于$100\%$的数据，$n,m

输出共 $m$ 行，每行一个整数，表示对应查询的区间和。

样例中有三个询问 ​ 第一个询问，数组第1个元素到第3个元素的总和，为 $1+2+3=6$