1.前文嗯对在昨天作者写了一些无脑的玩意大家就当个乐子看。顺便放一下网址昨天的东西2.正文2.1前缀和的介绍讲一个小故事虽然纯属虚构从前有一个程序员他想求多个从第个数到第个数的总和。假设下面的变量代表的数字全都不超过他首先就想到要输入个数再输入代表要测几次。再分别输入和用一个变量求从第个数到第个数的总和。代码大致是这样的#includebits/stdc.h using namespace std; int a[10005]; int main() { int n,m; cinn; for(int i1;in;i) { cina[i]; } cinm; for(int i1;im;i) { int sum0,x,y; cinxy; for(int jx;jy;j) { suma[j]; } coutsumendl; } return 0; }听起来很简单但他发现如果评测机一秒钟测试上限是和等于或接近时时间就会超过一秒钟。为此他想破脑袋才想出来了一个绝妙的方法——前缀和。2.2前缀和的代码他告诉你前缀和是怎么运作的假设有一个数组里面的元素是这样的1、3、5、7、9。让你求第二个到第四个的和。正常人都会一个个加。可前缀和不是这样。它在输入数组的时候就开始了。#includebits/stdc.h using namespace std; int a[10005]; int s[10005]; int main() { int n,m; cinn; for(int i1;in;i) { cina[i]; s[i]s[i-1]a[i]; } return 0; }此时数组前缀和数组里面的值是1、4、9、16、25。求第二个数到第四个数的和就是s[4]-s[1];你可能会问为什么要减[1]而不是[2]呢他又说“看看数组里的数”一个个加的做法35715。前缀和的做法16-115。这可快多了这个程序员又把下面代码放到评测机里测试#includebits/stdc.h using namespace std; int a[10005]; int s[10005]; int main() { int n,m; cinn; for(int i1;in;i) { cina[i]; s[i]s[i-1]a[i]; } cinm; for(int i1;im;i) { int x,y; cinxy; couts[x]-s[y-1]endl; } return 0; }我去什么时间超限不是秒了吗至此故事结束。逃新手小白提高A
