建网站的模块,wordpress一键采集淘宝商品,当当网网站开发计划和预算,厦门人才网唯一官网由于比赛基本都是采用Dev-C所以#xff0c;算法篇基本都是采用Dev-C来解释#xff08;版本5.11#xff0c;c11#xff09; 首先介绍一下前缀和算法
给定一个数组#xff0c;有q次询问#xff0c;每次询问#xff1a; 两个整数l,r#xff0c;求出数组 l 到 r的结果
遇…由于比赛基本都是采用Dev-C所以算法篇基本都是采用Dev-C来解释版本5.11c11 首先介绍一下前缀和算法
给定一个数组有q次询问每次询问 两个整数l,r求出数组 l 到 r的结果
遇到问题首先先来分析问题 上图 第一种方法相信大家都会写所以我们现在来写第二种解法 数学中的求和公式我们可以将其变为
那我们为什么要这么做呢
例如上面的数组 1 2 3 4 5 用这个公式可以得出 1 3 6 10 15 得出的东西是什么呢 可见每一项就等于自身的值加上前面的所有项的值 那我们应该如何求区间中的值呢 数组[r]-数组[l-1] 要求蓝色的值我们就要用从数组开始一直到 r 的值减去数组开始一直到 l-1 的值。
证明一下比如我们要求 l 2,r5 上面我们已经求得了数组开始一直加到数组结尾值为15数组[l-1]的值为1 最终我们所得的值为 14.
下来我们写一下代码
#includebits/stdc.h
using namespace std;
using lllong long;
const int N1e59;
void test()
{int lenth,q;cinlenthq;ll arr[N],perfix[N];for(int i1;ilenth;i){cinarr[i];}for(int i1;ilenth;i){perfix[i]perfix[i-1]arr[i];}while(q--){int l,r;cinlr;coutperfix[r]-perfix[l-1]\n;}
}
int main()
{int T;cinT;while(T--){test();}return 0;
}代码没有问题这里有一点我想提一下这里的代码,数组arr[0]是不存东西的是为了方便后面前缀和,有的小伙伴代码风格不同就是要从0开始也是可以的 通过调试 我们可以看到时这样存储的我们题目中询问l2 r5并不是问下标而是实打实元素的顺序要解决这一问题我们可以 将perfix[i]perfix[i-1]arr[i];改为现在这样这样就妥了 当然还有别的修改办法这里就不一 一列举了。
