题目描述

一维前缀和

样例

import java.util.Scanner;

public class Main {
    /*
    S[i] = a[1] + a[2] + ... a[i]                 s[i] = s[i - 1] + a[i];
    a[l] + ... + a[r] = S[r] - S[l - 1]

    [r-L,r] = S[r] - s[r-L]

    循环下标都是从1开始

    arr   1 3 7  5  2
    init  1 4 11 16 18  
    假如是算[3,5] 我们可以发现init[5]-init[3-1]=arr[3]+arr[4]+arr[5]

    数组多开一点空间，给最左和最右留点空间
    private static final int N = 100010;
    private static final int[] a = new int[N + 5];
    private static final int[] s = new int[N + 5];

    private static void init(int n) {
       for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + a[i];
       }
   }

   private static int sumPrefix(int left, int right) {
      return s[right] - s[left - 1];
   }
   */
    private static final int N = 100010;
    private static final int[] a = new int[N + 5];
    private static final int[] s = new int[N + 5];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
        }
        init(n);
        while (m-- > 0) {
            int l = in.nextInt();
            int r = in.nextInt();
            int res = sumPrefix(l, r);
            System.out.println(res);
        }
    }

    //计算长度为n的区间和
    private static void init(int n) {
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + a[i];
        }
    }

    //计算长度为n的区间当中[l,r]的区间和
    private static int sumPrefix(int left, int right) {
        //a[r] - a[l - 1]也就是a[r] - a[r-(r-l+1)]也就是a[r] - a[r-区间长度]
        return s[right] - s[left - 1];
    }
}