ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Segment Tree
    알고리즘/자료구조 2015. 9. 7. 16:34

    옛날에 min max Tree를 공부 할 때 배열 특정 구간 내에서의 최대값과 최소값을 미리 저장해두어 범위가 주어 질 때 O(logN)시간내에 해결 했었는데 이렇게 구간 내의 특정 값을 저장해두는 방식을 Segment Tree라고 하나 보다.



    범위가 주어지면 위 배열을 이용해서 해결하면 된다. 만약 3~6사이의 범위에 대해 구하라고 하면


    이렇게 풀면 된다.


    사실 이건 생각하는 것은 책 한번 보면 어렵지 않은데 이걸 어떻게 구현 할 것인가가 문제이다. 예전에는 이차원 배열 사용하며 메모리 낭비도 심하고 코드도 지저분하게 풀었는데 코드포스에 깔끔한 구현이 있어 참조해본다




    펜윅트리와는 다르게 Segment 트리는 구간의 최대값과 최소값 또한 저장 할 수 있고 갱신도 용이하다. 앞으로 자주 사용해야겠다.


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

    LCA(Lowest Common Ancestor)  (0) 2016.07.30
    Count sort  (0) 2016.07.23
    Segment Tree  (0) 2015.09.07
    SQRT Decomposition  (0) 2015.09.05
    LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27
    c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26

    댓글 0

Designed by Tistory.