어떤 구간의 최대,최소를 O(lgN)에 알게 해주는 자료구조 정의되는 연산 1.) 원소값 갱신 2.) a~b의 최대 또는 최소값 반환 완전이진트리를 배열로 구현 ( 들어갈 원소 숫자만큼의 단말노드를 가질 수 있도록 크기를 조정 , 편의상 그냥 4 * N으로 잡으면 된다. 값은 단말노드를 통해서만 들어간다. 예 : 들어갈 원소가 9개라고 한다면 최소한 단말노드가 9개 여야 하므로 비단말노드 15개, 단말노드 16개를 가지는 완전이진트리 형태가 되어야 할것이다. ) 원소값 갱신: 원소가 하나 추가될때마다 부모노드와 비교하여 최대, 최소 ( 또는 다른 그 구간을 대표할만한)을 갱신한다. a~b의 최대,최소 반환: a (왼쪽끝 노드)에 있는 노드가 오른쪽노드일때 그 부모노드가 구간을 대표하는 값을 가질 수 없다는점을 이용하여 노드의 위치가 오른쪽일때는 그 오른쪽에 에 위치하는 왼쪽노드 (이 두 노드는 서로 다른 부모노드를 가진다.) 로, 왼쪽노드일때는 부모노드로 위치를 옮겨가면서 리턴값을 갱신한다. 반대로 b(오른쪽끝 노드) 노드는 왼쪽노드일때 그 노드의 왼쪽에 있는 오른쪽노드, 오른쪽 노드일때 그 부모노드로 위치를 옮겨가면서 리턴값을 갱신한다. 두 위치가 교차되거나 겹칠때 루프를 종료한다. const int INF = 2e9 ; struct Tree { int first; vector<int> tree; Tree (int n) { for...
댓글
댓글 쓰기