누적합 알고리즘

누적합 알고리즘 동작 방식

• 구간 합 문제 : 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 계산하는 문제
• 예를 들어 N개의 정수로 구성된 수열이 있다.
• M개의 쿼 리 정보가 주어진다.
• 각 쿼리는 LEFT와 RIGHT로 구성된다.
• 각 쿼리에 대하여 [LEFT, RIGHT] 구간에 포함된 데이터들의 합을 출력해야 한다.
• 수행 시간 제한은 O(N + M)이다.