Fenwick Tree(Binary Indexed Tree, BIT)

FenwickTree

  펜윅트리는 동적인 누적 빈도수 테이블을 구현할 때 유용한 자료구조이다. 여기서 동적인 누적 빈도수 테이블이란 다음의 예를 보면 쉽게 이해할 수 있다. 학생11명이 시험을 본다. 당연히 11개의 시험 결과과 나온다. 시험점수는 0 ~ 10점 사이이다. 학생들은 0점부터 10점까지의 점수를 받게되며 각 점수당 0 ~ 11명 사이의 학생이 해당점 수를 받을 수 있다. 즉, 0점을 받은학생, 1점을 받은학생, ... 10점을 받은학생을 다더하면 11명이된다. 그렇다면 0점을 받은 학생의 수, 1점을 받은학생의 수, 2점 ..., 10점을 받은 학생의 수를 알때 이에대한 누적합을 구하려고 한다. 여기서 누적합이란. 

"누적합(0)"은 0점을 받은 학생의 수이다. 

"누적합(1)"은 0점을 받은 학생 + 1점을 받은 학생 수이다.

"누적합(2)"는 0점을 받은 학생 + 1점을 ... + 2점을 받은 학생 수이다.

  프로그래밍 대회에서 펜윅트리의 용도는 '동적인 누적 빈도수 테이블' 이라는 부분에서  '빈도수' 보다는 '동적인 누적' 이라는 부분에 더 무게가 실린다고 생각된다. 물론 경우에 따라서 누적 빈도수가 필요할때에는 위의 설명대로 펜윅트리를 활용하여 문제 해결이 가능 하겠지만 꼭 위와 같이 빈도수의 연산이 아닐 지라도 펜윅트리는 유용한 자료구조로 사용 가능하다. 예를들어 구간합 또는 부분합을 생각해보자. 구간합이나 부분합은 정적인 배열에서는 dp테이블을 이용하여 배열의 길이가 n일 경우 O(n)의 시간복잡도와 공간복잡도로 구해진다. 하지만 이러한 작업을 할 배열이 동적이라면 즉, 배열의 값들이 수시로 갱신된다면 갱신될때마다 O(n)의 시간복잡도를 갖는 작업을 반복해야 된다. 이는 꽤나 비효율 적이다. 이렇게 동적인 선형 자료 구조에서 부분합을 구할경우 구간트리(SegmentTree)를 이용할 수 도 있지만 구현이 쉽고 연산의 속도가 빠른 펜윅트리를 이용하는 방법도 있다. 동적인 누적 빈도수를 구한다는 측면에서 각 배열의 값을 해당 인덱스의 빈도수로 생각한다면 펜윅트리를 이용하여 해당 구간의 부분합을 쉽게 구할 수 있는 것이다.

FenwickTree 구현

  펜윅 트리는 말그대로 트리이다. 해당 트리는 배열로 구현된다. 배열의 한칸이 트리의 한개의 노드가 된다. 우선 펜윅트리를 구현하기위해서 LSOne(i)라는 함수를 정의하자. LSOne(i) 는 "i & (-i)"를 반환한다. 해당 비트연산은 i의 비트중 최하위 비트를 반환한다. 이제 이 함수를 이용하여 어떻게 FenwickTree가 구현되는지 설명할 것이다. 우선 배열 ft를 선언한다. 이는 펜윅트리다. ft에서 인덱스 i에 즉, i번 펜윅트리 노드에 할당되는 구간은 {i - LSOne(i) + 1, i - LSOne(i) + 2, ... , i} 이다. 그러므로 i번 노드에 저장되는 값은 위구간의 누적 합니다. 즉 위 구간의 부분합이 되는 것이다. 이해를 돕기 위해 예시를 제시한다. 6번 노드(배열의 6번 인덱스)에는 {6 - LSOne(6) + 1, ... ,6}의 범위가 할당된다. 여기서 6 - LSOne(6)의 값은 4이다. 즉 6번 노드는 구간 {5, 6}의 누적 합을 저장하게 된다. 다시 말해 부분합을 구하는 배열 A중 A[4] + A[5] 의 값을 저장한다.(LSOne 연산의 예의를 없애기 위해 펜윅트리ft의 0번 인덱스를 건너 뛰기때문에 실제 배열의 인덱스보다 ft의 인덱스가 1씩 더 크다.)

  그렇다면 임의의 구간이 주어졌을때 해당 구간의 부분합을 구하기 위해서는 어떻게 해야 되는가의 문제가 남는다. 이를 위해서 함수를 하나 정의한다 rsq(i)이다. Range Sum Query 라는 구간합 쿼리이다. rsq(i)는 인덱스 1부터 인덱스 i까지의 구간합을 반환한다. 펜윅트리를 이용하여 rsq(i)를 효율적으로 구현할수 있다. 이 함수를 효율적으로 구현한다면 현재함수를 오버로딩하여 rsq(i, j)는 매우 쉽게 구현된다. rsq(i, j) 는 구간 i ~ j 의 부분합을 의미한다. 

int rsq(int i, int j){    return (i == 1 ? rsq(j) : rsq(j) - rsq(i - 1));    }

그렇다면 우리에게 남은 과젠느 rsq(i)를 펜윅트리를 활용하여 구현하는 것이다. 이때 펜윅트리를 초기화 하기 위해 위에서 정의했던 LSOne 이라는 함수가 유용하게 사용된다. 현재의 인덱스가 b라면 b가 0이 될때까지 #연산을 수행한다. #연산은 다음과 같다.

#b = b - LSOne(b)

즉 rsq(i)의 반환 값은 ft(b) + ft(#b) + ft(##b) ... , (#..#b > 0) 이 된다.

  마지막으로 이러한 부분합을 구하기 위해 dp테이블을 정의하지않고 구간트리를 구현한 이유는 부분합을 구하는 선형자료구조가 동적이기 때문이다. 즉, 언제든지 임의의 구간에 대한 값을 갱신 할 수 있어야 되고 이에 대한 부분합을 효율적인 시간복잡도를 갖고 구할 수 있어야 된다. 즉, 원배열의 임의의 인덱스에 값이 변경될 경우 그에 따라 펜윅트리 ft도 수정이 되어져야 된다는 것이다. 이때에도 LSOne(i) 함수는 유용하게 사용된다. 인덱스 i의 값을 3만큼 늘렸다고 가정하자. 그리고 $연산을 정의한다.

$i = i + LSOne(i)

그리고 ft(i)를 3만큼 늘린다. ft($i), ft($$i), ... ,($..$i <= n) 노드의 값을 3만큼 늘린다. 이로서 해당배열의 인덱스 i값이 수정됨에 따라 펜윅트리 ft의 노드의 값들도 수정이 끝났다. 여기까지 설명한 알고리즘의 연산의 정당성을 설명할 수 있는 증명은 생략했다. 내용이 너무 길어지고 또 개인적으로 연산의 정당성이 직관적으로 이해가 간다고 생각하기 때문이다.

ADT of FenwickTree

FenwickTree(int n) = 부분합을 구할 배열의 크기 또는 빈도수를 구할 키의 상한.(0~n)

int rsq(int i, int j) = 배열 구간, (i - 1) ~ (j - 1) 의 부분합

int rsq(int i) = 배열 구간 0 ~ (i - 1)의 부분합

Code of FenwickTree(BIT)

class FenwickTree{

private:    vi ft;    //typedef vector<int> vi;

public:  

FenwickTree(int n) {    ft.assign(n + 1, 0);    }    //0번 인덱스는 건너뛴다.

int rsq(int i) {

int ret = 0; for(; i; i -= LSOne(i))    ret += ft[i];

return ret;    }

itn rsq(int i, int j) {    return rsq(j) - (i == 1 ? 0 : rsq(i));    }

void adjust(int i, int k) {

for(; i <= n; i += LSOne(i))    ft[i] += k;

}     };