前缀和

解决的问题
前缀和主要用于求一段区间的和，以O(1)的时间复杂度
而平时我们如果想要计算一段区间的和，需要O(n)

构造前缀和数组
可以使用公式s[i]=s[i-1]+a[i]构造前缀和数组，然后计算区间[L,R]的值的时候，只需使用S[R]-S[L-1]即可计算出a[L]到a[R]的和

代码如下
···

import java.util.*;

public class Main {

static int N=100010;



static int[] s=new int[N];
static int n,m;
public static void main(String[] args) {


    Scanner sc=new Scanner(System.in);

    n=sc.nextInt();

    m=sc.nextInt();

    // 计算前缀和数组
    for(int i=1;i<=n;i++) {

        s[i]=s[i-1]+sc.nextInt();


    }

    while(m--!=0) {
        int l=sc.nextInt();
        int r=sc.nextInt();

        // 计算前缀和
        System.out.println(s[r]-s[l-1]);




    }





}

}

···