구간 합

구간 합이란?

합의 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 알고리즘

합 배열 S 만들기

S[i] = S[i-1] + A[i]

구간 합 구하기

A[i] = S[i] - S[i-1]

코드로 구현해보기

구간 합이 아닌 원소를 하나씩 더할 때

package baekjoon;
import java.util.Scanner;
public class Baekjoon11659 {

	public static void main(String[] args) {
		
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		int M = input.nextInt();
		
		int[] arr = new int[N] ; //N개의 원소를 가진 배열 생성
		
		for(int k=0; k<N; k++) { //배열에 N개의 숫자 대입
			arr[k]=input.nextInt();
		}
		
		for(int k=0; k<M; k++) {
			int sum = 0;
			int i = input.nextInt();
			int j = input.nextInt();
			for(int h=i-1; h<j; h++) {// i부터 j까지 구하기 위해 
				sum = sum + arr[h];
			}
			System.out.println(sum);
		}
	}

}

구간 합을 통해 구할 때
오류가 나서… 담에 올리도록 하죠