펜윅트리 (Binary Index Tree) feat. kotlin

Fenwick 트리 또는 BIT(Binary Indexed Tree)는 요소를 "효율적으로 update"하고, 숫자 테이블에서 "prefix sum"을 계산할 수 있는 데이터 구조입니다.

 

구조는 1989년에 Boris Ryabko가 제안했으며, 1992년에 추가 수정본이 발표되었습니다.

이후 그의 1994년 기사에서 이 구조를 설명한 Peter Fenwick의 이름을 따서 Fenwick 트리라는 이름으로 알려지게 되었습니다.

 

*이진법 비트연산 성질을 이용한다.

 

컴퓨터에서 정수를 저장하기위 사용되는 타입은  Int입니다.

int 자료형은 4byte(32bit)이다.

 

정수 15는

00000000 00000000 00000000 00001111

 

정수 -15는  *2의 보수( ~15 + 1) 

11111111 11111111 11111111 11110001

 

15 & -15 

00000000 00000000 00000000 00000001

정수 N & -N 연산을 하면 정수를 비트로 표현시 왼쪽방향으로(<---) 처음으로 값이 1인 비트가 나오는 비트를 알 수가 있다.

 

1. 초기화

 

각 index의 처음으로 값이 1인 비트의 값 = 자신을 포함한 index에서  왼쪽방향으로(<---) 누적되어 더해져 있는 원소의 개수

 

예시)

index 8 --> 8 & -8 = 8개(값8+값7+값6+값5+값4+값3+값2+값1)

index 7 --> 7 & -7 = 1개 (값7)

index 6 --> 6 & -6 = 2개 (값6 + 값5)

 

*0번 index는 사용하지 않는다.

크기가 original tree의 size+1 인 배열을 선언한다

 

2. update

변경하려는 index에서 시작하여, 처음으로 값이 1인 비트의 값을 "더하여" 해당 index 값을 변경하여 트리를 업데이트 한다.

마지막 index까지 업데이트 하면 종료한다.

* 변경하려는 index의 값의 변경시 영향을 미치는 모든 인덱스가 갱신된다.

 

예) index 5

index 5의 처음으로 값이 1인 비트의 값 = 1

index 6(5+1)의 처음으로 값이 1인 비트의 값 = 2

index 8(5+1+2)의 처음으로 값이 1인 비트의 값 = 8

index 16

val arr = arrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

lateinit var fwTree: Array<Int>

fun initFwTree() {
    fwTree = Array(arr.size + 1) { 0 }
    for (i in 0 until arr.size) {
        fwUpdate(i, arr[i])
    }
}

fun fwUpdate(idx: Int, value: Int) {
    val diff = value - arr[idx]

    var i = idx
    while (i < fwTree.size) {
        fwTree[i] += diff
        i += (i and -i)
    }
    arr[idx] = value
}

3. prefix_sum

 

1---index 까지의 합

시작 index에서, 처음으로 값이 1인 비트의 값을 '빼면서" 해당 index 값을 누적한다

1번째  index까지 더하면 종료한다.

fun fwPrefixSum(idx: Int): Int {

    var i = idx
    var sum = 0
    while (i > 0) {
        sum += fwTree[i]
        i -= (i and -i)
    }
    return sum
}

 

4. interval_sum

fun fwIntervalSum(startIdx: Int, endIdx: Int): Int 
	= fwPrefixSum(endIdx) - fwPrefixSum(startIdx-1)