구간합

구간합구간 합은 합 배열을 이용해서 시간 복잡도를 줄이기 위해 사용하는 알고리즘합 배열 S의 정의A[0]부터 A[i]까지의 합S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i];합 배열은 기존의 배열을 전 처리한 배열로써 이런 식으로 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(n) 에서 O(1)로 감소인덱스012345배열A1513107312합배열 S152838454860합 배열 S를 만드는 공식S[i] = S[i-1] + A[i]구간 합을 구하는 공식S[j] - S[i-1] //i에서 j까지의 구간 합구간 합을 예제import java.util.Scanner;public class 구간합구하기4_11659 { public static vo..