一维前缀和[模版]

题目链接

题目:

分析:

• 因为要求数组中连续区间的和, 可以使用前缀和算法
• 注意:下标是从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[n+1];
        for(int i = 1;i < n+1;i++){
            arr[i] = in.nextInt();
        }
        long[] dp = new long[n+1];
        for(int i = 1;i < n+1;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--;
        }
    }
}