公司名注册查询网站,南京营销网站开发制作报价,wordpress 换行无效,自媒体135的网站是多少何为前缀和
有一个数组a, 为 ......
前缀和 ......
有两个问题:
1.如何求? 只需要从前往后遍历,令 就可以了,最开始是 ,定义 0
2. 有什么用? 能够快速地求出原数组中某一段的和,预处理的…何为前缀和
有一个数组a, 为 ......
前缀和 ......
有两个问题:
1.如何求? 只需要从前往后遍历,令 就可以了,最开始是 ,定义 0
2. 有什么用? 能够快速地求出原数组中某一段的和,预处理的时间复杂度是O(n),而对于每次查询时间复杂度是O(1),例如求原数组中 [l,r]区间中所有的数的和 也就是 ...... ,如果没有前缀和数组的话,就要循环一遍才可以求出结果,他的时间复杂度是O(n),如果有前缀和数组,那么只需要 - 就能得到区间和,那么为什么是l-1,很简单,例如我们要求[1,3]区间和,也就是 , 这就是 - 的 差 3.为什么数组是从 开始,要定义 0 ?其实这主要是边界问题,我们要让每一个 的求值都能够用到统一的公式 ,我们求前缀和的公式是 ,那么求 就要有 ,我们求[1,10]的区间和是 - ,也需要 ,这样就不需要额外讨论了
题目 输入一个长度为 n的整数序列。 接下来再输入 m个询问每个询问输入一对 l,r。 对于每个询问输出原序列中从第 l个数到第 r个数的和。 输入格式 第一行包含两个整数 n和 m。 第二行包含 n 个整数表示整数数列。 接下来 m 行每行包含两个整数 l 和 r 表示一个询问的区间范围。 输出格式 共 m行每行输出一个询问的结果。 数据范围 1≤l≤r≤n, 1≤n,m≤100000, −1000≤数列中元素的值≤1000输入样例 5 3 2 1 3 6 4 1 2 1 3 2 4输出样例 3 6 10 代码 #include iostreamusing namespace std;const int N 100010;
int a[N];
int S[N];
int n, m;int main(void)
{cin n m;for (int i 1; i n; i){cin a[i];S[i] S[i - 1] a[i]; // 前缀和的初始化}int l, r;while (m--){cin l r;printf(%d\n, S[r] - S[l - 1]);}return 0;
}
完美运行,当然输入数据可以使用scanf,会比cin的速度快1倍,前缀和不是一个模版,而是一种思想
