블로그 이사 중입니다 >> gumgood.github.io

Segment Tree (구간 트리) 본문

Problem Solving/분류없음

Segment Tree (구간 트리)

gumgood 2017. 5. 27. 03:41

Segment tree (구간 트리) : 1차원 좌표 상의 구간을 저장하고 특정위치를 포함하는 구간들을 찾는 자료구조

  - Query (질의) : 구간에 대한 연산을 실행한다. ex) RMQ(Range Minimum Query)


$ f(x) = x^2 $

$ \sum_{k=1}^N k^2 $


1. Segment tree 성질

  ① Seg-tree의 root는 항상 data배열의 '전체 구간'을 *표현한다. 즉 [1, n]

  ② 한 tree의 왼쪽 자식과 오른쪽 자식은 각각 해당 구간의 반을 표현한다.

  길이가 1인 구간은 tree의 left가 될 것이다.


  (*구간을 표현하다 : 해당 구간의 계산결과를 node에 저장한다. (ex, 구간의 합))


2. Segment tree 표현

  Segment tree를 1차원 array로 표현하여 쉽게 구현할 수 있다.

  root node의 index가 1일 때, 어떤 i번 node에 대해 왼쪽 node는 2i, 오른쪽은 2i+1이다.


  data의 크기가 n일 때, seg-tree에 필요한 array의 크기는 4n이다. (생각해보자)


3. Segment tree 구현

  ① init() : array가 주어질 때, 각 node마다 최소치를 계산한다.

    - init()함수를 tree의 순회와 같이 직접 구현하면 

    - init()함수 대신 각 node에 대해 upd()를 호출하면 

     * 즉, n의 값이 적절히 작다면 init()함수 구현을 생략할 수 있다.

  ② upd() : array에서 index에 있는 값이 바뀌었을 때, 이를 포함하는 구간들을 갱신한다.

      한 data를 포함하는 구간이 개 있으므로 시간복잡도는 

        * 구간 update X -> Fenwick Tree


  ③ query() : 임의의 구간의 계산값을 반환한다. (min, max, sum...)


  init() 구현 O(n + mlogn) :  C++11

  init() 생략 O(nlogn + mlogn) : C++11


4. Segment tree 활용

  plane sweeping와 같이 다른 알고리즘에 많이 쓰인다. (아직 안배움)


  tree의 LCA(link)를 찾는데에 쓰이기도 한다.

'Problem Solving > 분류없음' 카테고리의 다른 글

Minimum Spanning Tree  (0) 2017.05.27
Longest Increasing Subsequence  (0) 2017.05.27
Segment Tree (구간 트리)  (0) 2017.05.27
Disjoint-set  (0) 2017.05.27
Diameter of tree  (0) 2017.05.27
Tree Traversal  (0) 2017.05.27
0 Comments
댓글쓰기 폼