알고리즘: (BIT 부분 합, 누적 합)

부분 합:

A[n]배열이 있을 때, a,b (0<=a,b<=n)가 주어지면,

A[a]~A[b]까지 더하는 문제.

 

1. Brute-force

1. 순회하여 부분 합을 구한다.

 

전처리: x

시간복잡도: O(n)

 

2. O(n) 전처리, O(sqrt(n)) 질의

1. 배열 A를 sqrt(n)개의 원소씩 그룹으로 묶음

2. 각각의 합을 구함

3. a, b가 주어지면 양 끝부분의 합만 직접 구하고 중간 부분은 미리 구한 합을 더해줌 

 

전처리: O(n)

시간복잡도: O(sqrt(n))

    전처리 후 sqrt(n)개의 그룹,

    worst case: a=1, b=n-1

    중간 값을 처리하는 시간복잡도: sqrt(n)-2 (총 그룹의 수-양 끝의 2그룹)

    양 끝 값을 처리하는 시간복잡도: 2sqrt(n) (양 그룹의 원소의 수)

    총 시간 복잡도 = 3sqrt(n)-2 = O(sqrt(n))

업데이트: O(sqrt(n))

   원소가 바뀐 그룹만 다시 전처리함

 

3. O(n) 전처리, O(1)질의

1~i까지의 합인 PrefixSum[i]를 미리 다 구함.

Sum(a, b) = PrefixSum[b] - PrefixSum[a-1]

 

전처리: O(n)

시간복잡도: O(1)

업데이트: O(n)

---

4. BIT (Binary Indexed Tree)

L[i]:

    i를 2진수로 나타냈을 때 마지막 1에 해당하는 값

    ex: L(6) = 2 (6=>0110=>0010 = 2)

    구하는 법:

        L[i] = i & -i

Tree[i]:

    A[i]부터 L[i]개의 값 만큼 더한다.

 prefixSum[i]: 

    ex: prefixSum[13] = Tree[13]+ Tree[12] + Tree[8]

         13-L[13] = 12 -L[12] = 8 -L[8] = 0 (i -= (i & -i))

 

업데이트:

 

전처리: O(n)

시간복잡도: O(log n)

업데이트: O(log n)

    

참고