누적합누적합(Cumulative Sum)은 배열이나 리스트의 특정 구간 합을 빠르게 계산하기 위해 사용하는 알고리즘 기법이다. 일반적으로 대량의 데이터에서 특정 구간의 합을 반복적으로 구해야 하는 경우, 단순히 반복문을 이용해 매번 합을 계산하는 것은 비효율적일 수 있다. 이때, 누적합 배열을 활용하면 원하는 구간의 합을 상수 시간 내에 구할 수 있다. 누적합의 원리누적합의 기본 원리는 배열의 각 위치까지의 값을 순차적으로 더해 새로운 배열을 생성하는 것이다. 이를 통해 배열의 특정 구간 합을 빠르게 계산할 수 있다. 예를 들어, 배열의 i번째 위치까지의 누적합은 원본 배열의 0번째 인덱스부터 i번째 인덱스까지의 합을 저장하는 형태다.누적합 배열을 S라고 할 때, 원본 배열 A에서 구간 [i, j]의 합..