Prefix Sum 알고리즘

https://app.codility.com/programmers/lessons/5-prefix_sums/

 

n 개의 숫자가 있고, m 개의 쿼리에 각 쿼리마다 a 인덱스부터 b 인덱스까지의 숫자의 합을 구하는 문제

숫자들의 합산을 저장하는 배열을 선언하고 n 개의 숫자 배열을 순회하며 합산을 저장한다.

a 부터 b 까지의 숫자들의 합은 합산 배열의 b 인덱스 에서 a - 1 인덱스 값을 뺀 결과값이다.

prefix sum 알고리즘을 이용하면 m * n 의 시간 복잡도를 m + n 으로 줄여준다.