Algorithm: 부분합(Prefix Sum)

부분합이란?

• 부분합은 배열의 각원소까지의 누적합을 계산한 배열을 말한다.
• 부분합 배열의 i 번째 원소는 원래 배열 의 1번째부터 i 번째 원소까지의 합을 나타낸다.

Square Root Decomposition(전처리: O(n), 질의: O(sqrt(n))

• 이 방법은 배열을 sqrt(n) 개의 블록으로 나누고 각 블록에 대한 누적합을 계산하여 저장한다.
• 예를 들어 배열 A = [1,2,3,4,5,6,7,8,9,10] 의 배열이 있다.
  • 배열을 sqrt(n), 즉, 3개의 블록으로 나눈다면 다음과 같다
    • B[0] = A[0] + A[1] + A[2] -> 6
    • B[1] = A[3] + A[4] + A[5] ->15
    • B[2] = A[6] + A[7] + A[8] ->24
    • B[3] = A[9] -> 10
    • B = [6,15,24,10]
  • 만약 배열 A의 구간 [2,7] 에 대한 부분합을 구할 시 다음과 같은 동작을 띈다.
    • 구간[2,2] 는 블록 B[0]에 걸쳐있다 --> 따로 계산 : 3
    • 구간 [ 3,5 ] 는 블록B[1] 과 같다 --> 미리 저장한 값 15
    • 구간 [6,7]은 블록 2에 걸쳐있다 --> 따로 계산: 15
    • 모두 더하면 33
  • Update 할 시에 유용하다. 
    • 한 블록만 다시 계산하면 되기 때문
• 방법 2( 전처리: O(n), 질의 O(1))
  • 배열 A = [1,2,3,4,5] 가 주어졌을 때 prefix sum 배열을 생성한다.
    • B = [1,3,6,10,15]
  • 이 때 만약 Sum(i,j) 를 구하고 싶다면 B[j] - B[i-1] 을 해주면 된다.

Binary Indexed Tree(Fenwick Tree)

• Binary Indexed Tree 는 이진 트리 형태이며 각 노드는 그 자식노드들의 합을 저장한다.
  • 이 과정은 O(log n) 시간이 걸린다.
• 크기 15 의 배열을 BIT 로 만들면 다음과 같다

• 업데이트 과정을 살펴보자
  • 1번 인덱스를 업데이트 한다면 변경되어야 할 부분은 다음과 같다
  • 1 업데이트 후, 1-2 업데이트후, 1-4 업데이트 후, 1-8 업데이트 후, 1-16 업데이트
   

• 그럼 만약 5 - 15 사이의 구간합을 구하고자 한다면 다음과 같이 동작한다. 
• (1-8) + (9-12) + (13-14) + (15) 

• Fenwick Tree를 구현하기 위해서 어떠한 수 X를 이진수로 나타냈을 때, 마지막 1의 위치를 알아야 한다.
  • 마지막 1이 나타내는 값을 L[i] 라고 한다. 
  • L[i] 는 A[i] 부터 앞으로 L[i] 개의 합을 저장한다는 뜻이다
  • 이는 i & -i 로 구현된다.
  • Ex) Tree[12] 에는 12 부터 앞으로 L[12], 12 in binary = 1100, -12 in binary = 0100, 1100 & 0100 = 0100 = 4 개의 합 a[9]