请大神帮看下代码，在OJ上时间超限

有优化空间，按暴力解法会有很多重复计算

比如输入

2

1 2

1 2 3

第一次循环计算了1 + 2 = 3

第二次循环计算1 + 2 + 3 = 6 （重复计算了1 + 2）

你可以把1 + 2的结果保存下来put(1 + 2)，下次要用的时候直接取出来，那第二次循环就变成了

get(1 + 2) + 3 = 6,就省略了重复的计算

最好的方法是直接初始化一个大的数组，数组每个槽对应的初始值就是前面所有值之和

求n到m的值只用把n之前的减掉就行，你可以尝试一下

超时了还用数组?.....用数组不还是要做那么m-n次吗?

用等差数列求和公式

最多300万的量遍历一次数组是很快的吧，毫秒级别，初始化数组完成后的代值计算是O(1)的，当然楼上数学公式是最快的

我不是跟您杠啊,从1加到300万,用您的方法。用这么多内存,您觉得合适吗

在没有特解的情况下,还是用【前缀和】吧。

这个概念就是 一楼说的。

即 设置数组 b[1]- b[0] = a[0] 

                    b[2]-b[1]=a[1] 

                    b[3]-b[2]=a[2] 

那么这样存一次,我再继续进行第二次查询的时候,就直接拿数组里的值,减一下就行了...不必重新从n算到m

n+(n+1)+(n+2)...+m=(n+m)*(m-n+1)*1/2（n∈N）

在这里刚好能用到。

不TLE的代码：

#include <stdio.h>
int main() {
	int t; scanf("%d", &t);
	while (t--) {
		int n, m; scanf("%d %d", &n, &m);
		printf("%d\n", 1ll * (n + m) * (m - n + 1) / 2);
	}
	return 0;
}