BIT(Binary Indexed Tree)

어려운거 많이 가르치기로 소문난 양교수님께서 왜 BIT를 설명 안해주셨을까

이렇게 감탄스러운 자료구조가 있는 줄 몰랐다.

RB Tree, AVL, 24 Tree이런거는 구현이 어려운데

이거는 구현도 어렵지 않고 편리하다

간단히 소개를 하면

기본적으로 어떤 data를 추가 할 때 O(1) 

그리고 그 data의 총 합을 구할 때는 O(n)이 걸린다.

하지만 BIT는 추가 할때도 O(logn) 총 합을 구할 떄도 O(logn) 시간이 걸리는

신기한 자료구조이다.

http://183.106.113.109/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree

개념 설명이 내가 너무너무 부족하니 여기 있는 글을 통해서 이해하길...

나는 이것을 어떻게 응용할 것인지를 생각해보면...

위 사이트에서도 이미 응용 했지만

부분 합을 구하는 자료 구조 뿐만 아니라

부분 최소 값을 구하는 자료 구조로도 이용 할 수 있지 않을까 한다.

1차원을 사용하면 원래 값들을 모두 잃어버리겠지만

만약 내가 최소값을 찾길 원한다면 모두 다 돌아다니지 않아도 O(logn)시간에 찾을 수 있으니

효율적이다. 

LIS에서도 이 방법을 적용 할 수 있다고 하니

응용할 수 있는 방법이 무궁무진한 자료구조이다.

#include<iostream>

using namespace std;

int tree[20];

#define MaxVal 16

int read(int idx)

{

int sum = 0;

while(idx > 0){

sum += tree[idx];

idx -= (idx & -idx);

}

return sum;

}

void update(int idx, int val)

{

while(idx <= MaxVal)

{

tree[idx] += val;

idx += (idx & -idx);

}

}

int main()

{

for(int i = 1; i <= 16; i++)

update(i, i);

for(int i = 1; i <= 16; i++)

cout<<tree[i]<<endl;

return 0;

}