수열의 구간 합을 빠르게 계산하는 방법1 -접두사 합(prefix sum)-

1. 개요 연속적으로 나열된 수 n개가 있을때, 특정 구간의 모든 수를 합한 값을 구하는 문제 예를 들어 [10,20,30,40,50]이 있다고 가정해보자. 두번째 수부터 네번째 수까지의 합은 20+30+40=90이다. 이러한 구간 합 계산 문제는 매우 간단하게 인덱싱으로 구할 수 있을 것 같지만, 여러개의 테스트 케이스로 구성된 문제라면 이야기가 달라진다 T개의 테스트 케이스가 주어지고 테스트케이스 각각이 [left,right]에 존재하는 모든 수의 합을 구하라고 한다고 하자 만약 수열의 길이가 N이라고 한다면, 최악의 경우 O(NT)의 시간복잡도를 가진다 매 테스트케이스마다 길이 N의 구간합을 계산하라고 할 수 있기 때문이다. 하지만 만약 N=1000000이고 T=1000000이라고 한다면? O(NT..