시퀀스의 두 항목 사이의 최소값

Question

다음에 신속하게 응답 (O (logn))하기 위해 O (N) 시간 배열의 숫자 시퀀스를 저장하는 프로그램을 만들려고합니다.

min (int i, int j) : 포지션 i와 j 사이의 시퀀스에서 최소값의 포지션을 반환합니다.

예를 들어 시퀀스가 ​​A = (22, 51, 83, 42, 90, 102, 114, 35)이고 i가 min (3,6) 을 호출하면 42 < 83,90,102이기 때문에 4를 반환합니다.

시퀀스의 값이 정렬되지 않았거나 O (logn)을 얻고 싶기 때문에 빠른 시간을 얻을 수 없다는 것을 알고 있습니다. 이진 트리를 구현할 생각이었습니다.

문제는 내가 필요로하는 일을 min()을 위해 신속하게 액세스 할 수 있도록 이진 트리에 시퀀스의 값을 어떤 방법으로 배치해야하는지 파악할 수 없다는 것입니다.

Answer 1

이것은 간격 트리로 해결해야하는 일반적인 문제입니다. O(n) 시간에 구성하고 O(log n)에서 쿼리를 실행할 수 있습니다.

일반적인 생각은 인덱스 i에있는 노드의 인덱스가 2i 및 2i+1 인 배열에 완벽한 이진 트리를 저장하는 것입니다. 나뭇잎에 시퀀스의 값을 저장하고 모든 리프가 아닌 노드에 대해 최소한의 모든 자손을 저장합니다. 잎을 위쪽에서 나무를 만들면 O(n) 시간에 할 수 있습니다. a 및 b

반복적으로 아래로가는 잎에서 뿌리 향해

• :
  는 두 가지 기본 방법 (O(log n) 시간에 모두 작업)를 취할 수, 간격 [a; b]에 대한 쿼리를 실행하려면 나무 뿌리부터 시작하여

'간격 나무'구를 인터넷에서 쉽게 찾을 수있는 두 가지 방법에 대한 설명. 귀하의 문제에 대한 전 조금 더 빨리해야하기 때문에 전 하나를 확실히하는 것이 좋습니다.

요청에 따라 트리를 쿼리하는 방법에 대한 대답을 확장했습니다. 당신의 문제에 대해 제안한 상향식 접근법에 대해 자세히 살펴 보도록하겠습니다. 배열이 0에서 n - 1으로 인덱싱된다고 가정합니다. 또한 n은 k 인 경우 2^k과 같다고 가정합니다. 그렇지 않은 경우 최소 값을 쿼리하는 경우 하단 수준 끝에 +Inf 요소를 추가하여 가장 가까운 2의 제곱으로 증가시킵니다. 그것은 유효한 쿼리에 영향을 미치지 않을 것이고 이전에 설명한 것처럼 쉽게 인덱싱 할 수있는 완벽한 이진 트리를 얻게됩니다. 편안한 구현을 위해 인덱스 1을 루트로 사용하는 것이 좋으며,이 설명을 위해 가정합니다.

이 그림은 더 명확하게해야합니다. 맨 아래의 검정색 인덱스는 원래 배열의 인덱스입니다. 각 노드 옆의 녹색 색인은 트리의 색인입니다. 이제는 쿼리 예제와 관련된 직사각형을 무시하십시오. query(a, b)으로

우리는 간격 [a; b] (포함)에서 최소에 대한 쿼리를 나타내는 것입니다.첫째, 특수한 경우 : a이 b 일 때 tree[n + a]을 반환합니다 (tree[1]이 루트 인 경우 올바른 색인임을 유의하십시오).

a != b 일 때 더 복잡한 경우로 이동하십시오. 알고리즘의 단서는 모든 간격을 공통 요소가없고 원래 간격을 완전히 포함하는 O(log n) 기본 간격으로 나눌 수 있다는 것입니다. 각 기본 간격의 크기는 2의 거듭 제곱이며 각 기본 간격은 우리 노드 중 하나에 의해 표시됩니다. 모든 관련 간격을 나열하면 query(a, b)에 대한 답을 얻기 위해 노드의 최소값을 취하면됩니다.

이제 기본 간격을 선택하는 방법을 설명 할 것입니다. 예제 이미지에서는 모두 직사각형으로 둘러싸여 있습니다. 다음 코드 스 니펫을 살펴보십시오.

int x = a + n; 
int y = b + n; 
int result = Math.min(tree[x], tree[y]); 

while (x/2 != y/2) { 
    if (x % 2 == 0) { 
     result = Math.min(result, tree[x + 1]); 
    } 
    if (y % 2 == 1) { 
     result = Math.min(result, tree[y - 1]); 
    } 

    x /= 2; 
    y /= 2; 
} 

처음에는 원래 색인을 트리의 색인으로 변환합니다. 그런 다음 쿼리의 경계가 포함 된 단일 항목 간격을 고려합니다. a == b 일 때 나는 특별한 경우를 제외했다는 것을 기억하십시오.

알고리즘은 트리를 위쪽으로 이동하면서 다음과 같이 진행됩니다. x % 2 == 0 때마다 우리는 나무에서 x의 형제 인 간격을 고려합니다. 이 형제가 항상 [a; b] 간격에 완전히 포함되어 있는지 확인하십시오. 형제가 y의 왼쪽에 있다는 점을 제외하고는 y % 2 == 1과 동일합니다. x/2 == y/2 일 때 x과 y이 이제 형제임을 의미하며 알고리즘을 중지해야합니다. 이 방법이 완전히 [a; b]을 덮는 방식으로 간격을 선택하는지 직접 확인할 수 있습니다.

트리의 최하위 레벨에있는 노드를 최대 4 개까지 확인할 수 있습니다. 각 레벨에서 우리는 노드를 2 개까지 검사하지 않을 것입니다. 트리의 레벨이 O(log n)이므로 우리는 쿼리의 시간 복잡도가 O(log n)임을 알 수 있습니다.

보너스 - 배열 수정. 설명 된 문제는 배열을 수정할 필요가 없지만 기본적인 경우에는 매우 깨끗하여 여기에 추가 할 것입니다. 또한 명령어를 처리하려는 경우 array[a] = v을 의미하므로 O(log n) 시간에 쉽게 수행 할 수 있습니다. 먼저 tree[a + n] = v으로 설정하고 경로의 최소값을 업데이트하는 루트로 이동하십시오.