구간합구하기

수 N개가 주어졌을 때 i 번째 수에서 j 번째 수까지의 합을 구하는 프로그램을 작성하시오.

입력

1번째 줄에 수의 개수 N(1<=N<=100000), 합을구해야하는 횟수 M(1<=M<=100000),2번째줄에 N개의 수가 주어진다. 각수는 1000보다 작거나 같은 자연수다. 3번째 줄부터는 M개의 줄에 합을 구해야하는 구간 i와 j가 주어진다.

5 3
5 4 3 2 1
1 3
2 4
5 5

출력

12
9
1

코드

public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        int q= sc.nextInt();
        int[] arrN = new int[n+1];
        arrN[0]=0;
        for(int i=1;i<=n;i++){
            arrN[i]=sc.nextInt();
            arrN[i]+=arrN[i-1];
            System.out.println(arrN[i]);
        }

        for(int i=0;i<q;i++){
            int a= sc.nextInt();
            int b= sc.nextInt();
            System.out.println(arrN[b]-arrN[a-1]);
        }
    }

맨압 리스트를 0으로 두고 받는대로 이전값과 더해나가서 합배열을 생성

그후 받은 구간에 맞게 빼주어서 값을 뽑아낸다.

• 합배열 공식
  S[i]=S[i-1]+A[i]

• 구간합공식
  S[구간끝]-S[구간시작-1]

이를만족하기위해서는 배열을 0에서부타담는것이 아닌 1부터담아야한다. 그래야 1 1일경우 예외처리도됨

즉
index 0 1 2 3 4 5
원배열A 0 5 4 3 2 1
합배열S 0 5 9 12 14 15

이런식으로 담아야한다.