甜品网站建设项目规划书,网页是怎么做的,百度指数批量查询,网站开发实例教程实训心得题目链接
题目: 分析:
因为要求数组中连续区间的和, 可以使用前缀和算法注意:下标是从1开始算起的, 真正下标0的位置是0第一步: 预处理出来一个前缀和数组dp dp[i] 表示: 表示[1,i] 区间所有元素的和dp[i] dp[i-1] arr[i]例如示例一中: dp数组为{1,3,7}第二步: 使用前缀数…题目链接
题目: 分析:
因为要求数组中连续区间的和, 可以使用前缀和算法注意:下标是从1开始算起的, 真正下标0的位置是0第一步: 预处理出来一个前缀和数组dp dp[i] 表示: 表示[1,i] 区间所有元素的和dp[i] dp[i-1] arr[i]例如示例一中: dp数组为{1,3,7}第二步: 使用前缀数组 要求[l,r]区间的和 dp[r] - dp[l-1]例如示例一中: 求[1,2]的和 dp[2] - dp[0] 3疑问: 为什么我们的下标要从1开始计数呢?为了处理边界情况 如果从0开始, 那么计算dp[i]时, dp[0] dp[-1] arr[0] 会出现越界, 并且在计算[0,2]的区间和时, dp[2] - dp[-1] 也会出现越界, 那么从下标从1开始计数就很好的规避了这个问题, 计算dp[i]时, dp[1] dp[0] arr[1], dp[0]的位置我们并没有管, 所以还是0, 那么dp[1] arr[1]正确, 在计算[1,2]的区间和时, dp[2] - dp[0] dp[2], 正确
代码:
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int q in.nextInt();int[] arr new int[n1];for(int i 1;i n1;i){arr[i] in.nextInt();}long[] dp new long[n1];for(int i 1;i n1;i){dp[i] dp[i-1] arr[i];}while(q0){int l in.nextInt();int r in.nextInt();System.out.println(dp[r] - dp[l - 1]);q--;}}
}
