本文主要是介绍每日OJ题_算法_前缀和①_牛客DP34 【模板】前缀和（附一维二维前缀和模板），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
前缀和算法介绍
一维前缀和
①牛客DP34 【模板】前缀和
解析代码
前缀和算法介绍
前缀和算法是一种用于高效计算数组前缀和的算法。前缀和是指从数组的起始位置到某一位置的所有元素的和。（前缀和算法一般分为一维前缀和，二维前缀和，后者放在下一篇OJ了，完整的前缀和OJ在第八个专栏，Offer必备算法）
前缀和算法其实是一个小的动态规划，其算法一般步骤如下：
一维前缀和
- 创建一个与原始数组相同长度的前缀和数组。初始时，前缀和数组的第一个元素与原始数组的第一个元素相同。
- 从第二个元素开始，遍历原始数组，计算每个位置处的前缀和，即将前一个位置的前缀和与当前位置的元素相加。
- 将计算得到的前缀和存储到前缀和数组的相应位置。
- 完成遍历后，前缀和数组中存储了原始数组每个位置的前缀和值。
代码步骤：
- 先预处理出来⼀个前缀和数组： 用 dp[i] 表表示：[1, i] 区间内所有元素的和（注意从1开始，dp[0]给0就行），那么 dp[i - 1] 里面存的就是 [1, i - 1] 区间内所有元素的和，那么：可得递推公式： dp[i] = dp[i - 1] + arr[i] ；
- 使用前缀和数组，快速求出某⼀个区间内所有元素的和： 当询问的区间是 [left , right] 时：区间内所有元素的和为： dp[right] - dp[left - 1] 。
前缀和算法的主要优势在于它可以用较低的时间复杂度O（N）计算指定范围内的元素和，而不是每次都需要重新遍历计算。
以下是一个示例，演示如何使用前缀和算法计算数组的前缀和：
原始数组: [1, 2, 3, 4, 5]，其前缀和数组: [1, 3, 6, 10, 15]
解释：原始数组的前缀和：[1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5] = [1, 3, 6, 10, 15]
①牛客DP34 【模板】前缀和
【模板】前缀和_牛客题霸_牛客网
#include <iostream>
using namespace std;int main() {int a, b;while (cin >> a >> b) { // 注意 while 处理多个 casecout << a + b << endl;}
}
// 64 位输出请用 printf("%lld")解析代码
暴力解法就是模拟（模拟题目意思），q次询问就遍历数组q次，这样时间复杂度是O（N^2），使用前缀和算法只需遍历一遍数组处理出前缀和数组，询问的时候O（1）就能询问了，时间复杂度是O（N）。
#include <iostream>
#include <vector>
using namespace std;int main()
{int n = 0, q = 0;cin >> n >> q;vector<int> arr(n + 1, 0);for (int i = 1; i <= n; i++) // 读取数据{cin >> arr[i];}vector<long long> dp(n + 1, 0); // 防溢出for (int i = 1; i <= n; i++) // 处理前缀和数组{dp[i] = dp[i - 1] + arr[i];}int left = 0, right = 0;while (q--) // 计算区间和{cin >> left >> right;cout << dp[right] - dp[left - 1]<< endl;}return 0;
}二维前缀和链接：（题解放在下一篇了）
【模板】二维前缀和_牛客题霸_牛客网
这篇关于每日OJ题_算法_前缀和①_牛客DP34 【模板】前缀和（附一维二维前缀和模板）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
