算法025：前缀和

本文主要是介绍算法025：前缀和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【模板】前缀和给定一个长度为n的数组. 接下来有q次查询, 每次查询有两个参数l, r. 对。题目来自【牛客题霸】https://www.nowcoder.com/share/jump/8521810001724331400756

结束上一个板块二分查找，我们现在进入到的是前缀和。

本题要求是，返回一个数组中，给定的区间内的合。

使用到的方法是：前缀和。

具体来说，先利用给定的这个数组，再构造出一个新的数组。这个数组是原数组的前缀和数组。

红色的数组便是我们新构造的数组，每个位置的数字，是原数组当前下标及之前下标的合。

假设题目要问的是，arr[3] - arr[5]的和，我们只需要用新数组 dp[5] 减去 dp[2]  ，就是题目需要的值。

此时若需要求得是3 5 7 9 的和，我们只需要用25减去1就可以得到。

代码：

public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextInt()) {int n = in.nextInt();int q = in.nextInt();int[] arr = new int[n+1];for(int i = 1; i <= n; i++){arr[i] = in.nextInt();}long[] dp = new long[n + 1];for(int i = 1; i <= n; i++){dp[i] = dp[i - 1] + arr[i];}while(q > 0){int l = in.nextInt();int r = in.nextInt();System.out.println(dp[r] - dp[l - 1]);q--;}}}
}

这篇关于算法025：前缀和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---