티스토리 뷰

struct IndexedTree {

   vector<inttree;

   int size;

   IndexedTree(int nint *arr) :

          tree(4 * n987654321) {   //넉넉하게 4*n 사이즈 배열 생성초기값 지정

       size = 1;

       while (size < n//2 배수로 최저 깊이레벨 노드 개수 결정

          size *= 2;

       for (int i = 0i < ni++)

          tree[size + i] = arr[i];   // 복사

       init(1);  //값들  계산.

   }

   /* 후라이빗 함수 */

   int init(int pos) {

       if (pos >= size//단말 노드일 경우

          return tree[pos];

       return tree[pos] = min(init(pos * 2), init(pos * 2 + 1));

   }

   int query(int leftint rightint nodeint nodeLeftint nodeRight) {

       left = max(leftnodeLeft);

       right = min(rightnodeRight);

       if (left > right)

          return 987654321;   //초기값

       if (left == nodeLeft && right == nodeRight)

          return tree[node];

       int mid = (nodeLeft + nodeRight) / 2;

       return min(query(leftrightnode * 2nodeLeftmid),

              query(leftrightnode * 2 + 1mid + 1nodeRight));

   }

 

   void update(int pos) {

       if (pos < 1)

          return;   //루트까지만

       tree[pos] = min(tree[pos * 2], tree[pos * 2 + 1]);   //갱신

       update(pos / 2);   //부모 노드 따라 계속 올라감

   }

 

   /* 사용시 직접 호출할 함수 */

   int query(int leftint right) {  //left~right 사이의 대표값

       return query(leftright10size - 1);

   }

   void update(int indexint newValue) {   //index 노드 값을 갱신

       tree[size + index] = newValue//해당 노드 업데이트

       update((size + index) / 2); //부모 노드 재귀 업데이트

   }

};


사용시 초기값(987654321)은 const 선언하거나 define 해서 사용하시면 됨니다.

구간 합만을 구하는 경우는 더 간단한 펜윅트리가 있습니다.(대신 초기화가 없습니다.. lgN 시간으로 되지 않는다는 말)


사용법


생성

int arr[10]={1,2,3,4,5,6,7,8,9,10};

이런 배열이 있으면

IndexedTree tree(10, arr);

이렇게 트리 생성. 그러면 배열의 값 모두 복사하고 그 외 값은 아주 큰 값으로 초기화 함.


구간 쿼리

query(5,8) 하면 5~8중 가장 작은 값 리턴.


값 갱신

update(4,30) 하면 4번 값을 30으로 갱신. 부모 재귀적으로 모두 갱신.



시간복잡도

쿼리,갱신 모두 O(lgN)



초기화 및 업데이트 부분은 자작인데 구간 쿼리 함수는 어려워서 참고 하였습니다. https://jmk.pe.kr/read/generic-segment-tree-using-templates

초기값을 바꾸고 min 비교를 max로 바꾸거나 합을 구하는 식으로 바꿔 구간 최대값이나 구간 합으로 쉽게 변경이 가능합니다.

댓글
댓글쓰기 폼
공지사항
Total
325,497
Today
25
Yesterday
135
링크
«   2018/10   »
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
글 보관함