ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • BIT(Binary Indexed Tree)
    알고리즘/자료구조 2015. 2. 21. 21:56

    어려운거 많이 가르치기로 소문난 양교수님께서 왜 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;

    }


    '알고리즘 > 자료구조' 카테고리의 다른 글

    오일러회로  (0) 2015.02.27
    트라이  (0) 2015.02.27
    트립(Treap)  (0) 2015.02.25
    접미사배열  (0) 2015.02.24
    KMP 알고리즘  (0) 2015.02.24
    BIT(Binary Indexed Tree)  (0) 2015.02.21

    댓글 0

Designed by Tistory.