C++: 누적 합 (Prefix Sum)

누적 합 (Prefix Sum)

• 미리 전체 합을 구해놓은 후 필요하지 않은 구간만 빼서 O(1)만에 결과를 구한다.

사용 예시

1. 1차원 배열 구간의 합

   

   • n개의 배열이 있을 때 같은 사이즈의 다른 배열에 각 인덱스까지의 합을 저장한다.
   • 구간의 합 = prefix[R] - prefix[L]

2. 2차원 배열 구역의 합

   

   • 1차원과 동일한 개념이다.
   • n * n 의 2차원 배열이 있을 때 같은 사이즈의 다른 배열에 각 인덱스까지의 합을 저장한다.
   • (r1,c1) 부터 (r2, c2)까지 직사각 구역의 합 = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix [r1][c1]

3. 차이 배열 - 구간합의 반대 개념

   

   • 인접한 원소와의 차이를 적은 배열을 차이 배열이라 한다.
   • 갱신해야 할 연산이 여러개라면 차이배열에 각각 $O(1)$으로 갱신해 모두 모으고, 원본배열에는 한번에 $O(n)$만에 갱신 가능.
     • ex) 구간 [a,b]에 x를 더한다면, 차이배열 D가 있을 때, D[a] = x, D[b+1] = -x
   • 누적합이 읽는 도구라면, 차이배열은 쓰는 도구

슬라이딩 윈도우와의 비교

• 슬라이딩 윈도우
  • 하나의 윈도우
  • 매단계 갱신
  • 윈도우 속의 상태가 복잡하지 않을때
  • 중복 빈도
• 누적합
  • 한번 전처리
  • 임의 시점/구간 질의
  • 질문이 여러번일때!
  • 구간이 매번 다를때
• 고정된 k개의 합의 최댓값 둘다 가능
  • “임의”구간 “다회” 질문이면 누적합이 유리해짐
  • 전처리 비용으로 질의횟수마다 늘어나는 비용을 감소

  • 기법간의 비교

    | 복잡도 | 기법 | |:–:|:–:| | $O(n)$ | 투포인터/슬라이딩 윈도우/누적합 질의 | | $O(nlogn)$ | 정렬/병합 | | $O(n^2)$ | 완전탐색의 평균적 한계 | | $O(n^3)$ | 3중 루프 | | $O(2^n)$ | 부분집합 완전탐색 | | $O(n!)$ | 순열 완전 탐색 | 상황과 문제에 따라 어떤 기법을 사용할지 떠올릴 수 있어야 한다.

활용

• 게임
  • 퍼즐게임/영역별 점수 산출
  • 히트맵, 영향력 그리드 계산
  • 적 사거리 합산
  • “영역”을 계속 계산해야 하는 상황에 적용되어 프레임을 유지
• 웹/서버
  • 시계열 DB 집계 함수
    • 테이블 전체 훑기
      • 인덱스 없을 시 $O(n)$
      • 있을 시엔 $O(log n) / O(1)$
      • 대신 있으면 인덱스 업데이트에 의해 쓰기 비용 증가
    • OLAP(Online Analytical Processing)
      • 다차원 누적합(큐브)로 빠른 답변
      • 이번 분기 매출, 광고 클릭률 통계등 빠른 계산/분석 중요한 영역.
    • 반대개념 - OLTP(Online Trasaction Processing)
      • 인덱스 적게 쓰는대신 빨리 쓰기
      • 쇼핑몰 주문, 금융 전산 처리등 빠른 갱신이 중요한 영역.
  • 누적합 + 인덱스
• CS 전반
  • 적분 영상(Integral Image)
  • 컴퓨터 비전 특징 추출, 라이트맵
  • 머신러닝 데이터 전처리
  • 한번 전처리로 이후 작업 효율 개선할 수 있는 분야들.