누적합

누적합은, 보통 이중 반복문(배열 문제)으로 시간 초과가 될때 구간합을 O(1)로 줄여주는 경우가 많아서, 종종 쓰인다.

누적합 사용 유형

1. 구간 합 구하기: 배열에서 여러 번 특정 범위의 합을 구하는 경우, 배열의 누적합을 미리 계산해 두면 각 구간의 합을 빠르게 구할 수 있습니다.

   • 예시: 주어진 배열에서 여러 번 "i번째 원소부터 j번째 원소까지의 합"을 구하는 문제.

2. 최소/최대 구간 합: 배열에서 특정 길이의 구간 중 가장 큰 합 또는 가장 작은 합을 구하는 문제에서, 누적합을 활용하면 구간 합을 효율적으로 계산할 수 있습니다.

   • 예시: "배열의 부분 배열 중 합이 가장 큰 구간을 찾아라"와 같은 문제.

3. 차이 배열: 누적합을 활용하여 배열에서 구간별로 값을 추가하거나 뺄 때, 전체 배열을 매번 갱신하지 않고도 빠르게 처리할 수 있습니다.

   • 예시: 배열의 일부 구간에 동일한 값을 더하거나 뺄 때, 해당 구간의 시작과 끝 지점에서만 값을 변경하고, 이후 누적합으로 계산.

4. 투 포인터와 함께 사용: 투 포인터 기법과 결합하여 일정한 합을 만족하는 구간을 찾는 문제에서도 누적합을 사용할 수 있습니다.

   • 예시: "배열에서 합이 k인 부분 배열을 찾아라"는 문제에서 투 포인터와 누적합을 이용하면 효율적으로 해결할 수 있습니다.

5. 이차원 누적합: 2D 배열에서 특정 부분 영역의 합을 빠르게 구해야 하는 경우, 2차원 누적합을 사용할 수 있습니다.

   • 예시: "행렬에서 특정 좌표 범위 내의 값들의 합을 구하라"는 문제.

누적합은 계산을 미리 해 두어 시간을 줄이고, 나중에 특정 구간의 값을 빠르게 얻고자 할 때 유용한 기법입니다.

유형 예시 문제

1. 차이 배열 & 누적합
   코드트리 - 블럭쌓는 명령