수색…


세그먼트 트리 소개

배열이 있다고 가정합니다.

+-------+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |
+-------+-----+-----+-----+-----+-----+-----+
| Value |  -1 |  3  |  4  |  0  |  2  |  1  |
+-------+-----+-----+-----+-----+-----+-----+

이 배열에 대해 몇 가지 쿼리를 수행하려고합니다. 예 :

  • 인덱스 -2 에서 인덱스 -4 까지의 최소값은 얼마입니까? -> 0
  • 인덱스 0 에서 인덱스 3 까지의 최대 값은 얼마입니까? -> 4
  • 인덱스 1 에서 인덱스 5 까지의 합계는 얼마입니까? -> 10

우리는 그것을 어떻게 발견 할 수 있습니까?

무력 :
배열을 시작 인덱스에서 마무리 인덱스로 이동하여 쿼리에 응답 할 수 있습니다. 이 접근법에서 각 쿼리는 O(n) 시간이 소요됩니다. 여기서 n 은 시작 인덱스와 마무리 인덱스의 차이입니다. 수백만 건의 질의와 수백만 건의 질의가 있다면 어떨까요? m 개의 쿼리의 경우 O(mn) 시간이 걸립니다. 따라서 배열의 105 개의 값에 대해 최악의 경우에 대해 105 개의 쿼리를 수행하면 1010 개의 항목을 트래버스해야합니다.

동적 프로그래밍 :
다른 범위의 값을 저장하기 위해 6X6 행렬을 만들 수 있습니다. 범위 최소 쿼리 (RMQ)의 경우 배열은 다음과 같습니다.

              0     1     2     3     4     5
     +-----+-----+-----+-----+-----+-----+-----+
     |     |  -1 |  3  |  4  |  0  |  2  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+
  0  |  -1 |  -1 |  -1 |  -1 |  -1 |  -1 |  -1 |
     +-----+-----+-----+-----+-----+-----+-----+
  1  |  3  |     |  3  |  3  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  2  |  4  |     |     |  4  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  3  |  0  |     |     |     |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  4  |  2  |     |     |     |     |  2  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+
  5  |  1  |     |     |     |     |     |  1  |
     +-----+-----+-----+-----+-----+-----+-----+

이 행렬을 만들면 모든 RMQ에 응답하는 것으로 충분할 것입니다. 여기서, Matrix [i] [j] 는 index- i 에서 index- j 까지의 최소값을 저장합니다. 예 : 인덱스 -2 에서 인덱스 -4 까지의 최소값은 행렬 [2] [4] = 0 입니다. 이 행렬은 O(1) 시간에 쿼리에 응답하지만이 행렬을 빌드하는 데는 O (n²) 시간을, O(n²) 공간에는 O(n²) 공간이 필요합니다. 그래서 n 이 정말로 큰 숫자라면, 이것은 잘 확장되지 않습니다.

세그먼트 트리 :
세그먼트 트리는 간격 또는 세그먼트를 저장하기위한 트리 데이터 구조입니다. 저장된 세그먼트에 주어진 포인트가 포함되어 있는지 조회 할 수 있습니다. 세그먼트 트리를 만들기 위해 O(n) 시간이 걸리며 O(n) 공간을 유지 관리하고 O(logn) 시간에 쿼리에 응답합니다.

세그먼트 트리는 2 진 트리이며 지정된 배열의 요소는 해당 트리의 잎이됩니다. 하나의 요소에 도달 할 때까지 배열을 반으로 나누어 세그먼트 트리를 만듭니다. 그래서 우리 부서는 우리에게 다음을 제공 할 것입니다 :

세그먼트 화 된 배열

이제 잎이 아닌 노드를 나뭇잎의 최소값으로 대체하면 다음을 얻습니다.

최소값 대체 됨

이것이 우리의 세그먼트 트리입니다. 루트 노드는 전체 배열 (범위 [0,5])의 최소값을 포함하고, 왼쪽 자식은 왼쪽 배열의 최소값 (범위 [0,2])을 포함하고, 오른쪽 자식은 최소 배열 우리의 오른쪽 배열 값 (범위 [3,5]) 등등. 잎 노드는 각 점의 최소값을 포함합니다. 우리는 얻는다 :

세그먼트 트리

이제이 트리에서 범위 쿼리를 실행 해 보겠습니다. 범위 쿼리를 수행하려면 세 가지 조건을 확인해야합니다.

  • 부분 겹침 : 두 잎을 모두 검사합니다.
  • Total Overlap : 노드에 저장된 값을 반환합니다.
  • 오버랩 없음 : 매우 큰 값 또는 무한대를 반환합니다.

예를 들어, 범위 [2,4] 를 확인하고자합니다. 즉, 인덱스 -2 에서 4로 최소값을 찾고 싶다는 뜻입니다. 루트에서 시작하여 노드의 범위가 쿼리 범위와 겹치지 않는지 확인합니다. 이리,

  • [2,4][0,5]와 완전히 겹치지 않습니다. 그래서 우리는 양방향을 점검 할 것입니다.
    • 왼쪽 하위 트리에서 [2,4]는 [0,2] 와 부분적으로 겹칩니다. 우리는 양방향을 점검 할 것이다.
      • 왼쪽 하위 트리에서 [2,4][0,1] 과 겹치지 않으므로 이것이 우리의 대답에 기여하지는 않습니다. 우리는 무한대를 돌려 보낸다 .
      • 오른쪽 하위 트리에서 [2,4]는 완전히 [2,2] 와 겹칩니다. 우리는 4를 반환합니다.
        이 두 반환 값 (4, 무한대)의 최소값은 4 입니다. 우리는이 부분에서 4 를 얻습니다.
    • 오른쪽 하위 트리에서 [2,4]는 부분적으로 겹칩니다. 그래서 우리는 양방향을 점검 할 것입니다.
      • 왼쪽 하위 트리에서 [2,4][3,4] 와 완전히 겹칩니다. 우리는 0을 반환합니다.
      • 오른쪽 하위 트리에서 [2,4] 는 겹쳐지지 않습니다 [5,5] . 우리는 무한대를 돌려 보낸다 .
        이 두 반환 값 (0, 무한대)의 최소값은 0 입니다. 이 부분에서 0 을 얻습니다.
  • 반환 값 (4,0)의 최소값은 0 입니다. 이것은 범위 [2,4] 에서 우리가 원하는 최소값입니다.

이제 쿼리가 무엇이든 관계없이이 세그먼트 트리에서 원하는 값을 찾으려면 최대 4 단계를 수행해야합니다.

용도:

  • 범위 최소 쿼리
  • 가장 낮은 공통 조상
  • 게으른 전파
  • 동적 서브 트리 합
  • 방범 & 민
  • 이중 필드
  • k 번째 최소 요소 찾기
  • 정렬되지 않은 쌍의 수 찾기

배열을 이용한 세그먼트 트리의 구현

예를 들어, Item = {-1, 0, 3, 6} 이라는 배열이 있다고 가정 해 봅시다. 우리는 주어진 범위에서 최소값을 찾기 위해 SegmentTree 배열을 만들고 싶습니다. 우리의 세그먼트 트리는 다음과 같습니다.

세그먼트 트리

노드 아래의 숫자는 SegmentTree 배열에 저장할 각 값의 인덱스를 보여줍니다. 우리는 4 개의 요소를 저장하기 위해 크기가 7 인 배열이 필요하다는 것을 알 수 있습니다.이 값은 다음에 의해 결정됩니다.

Procedure DetermineArraySize(Item):
multiplier := 1
n := Item.size
while multiplier < n
    multiplier := multiplier * 2
end while
size := (2 * multiplier) - 1
Return size

그래서 우리가 길이 5의 배열을 가지고 있다면, SegmentTree 배열의 크기는 ( 8 * 2 ) - 1 = 15가 될 것 입니다. 이제, 노드의 왼쪽과 오른쪽 자식의 위치를 ​​결정하기 위해 노드가 인덱스 i 에 있으면 그 위치는 다음과 같습니다.

  • 왼쪽 자식은 (2 * i) + 1 로 표시됩니다.
  • 오른쪽 자식은 (2 * i) + 2 로 표시됩니다.

그리고 인덱스 i 에있는 노드부모 인덱스는 다음과 같이 결정할 수 있습니다. (i - 1) / 2 .

따라서 예제를 나타내는 SegmentTree 배열은 다음과 같습니다.

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  3  |  -1 |  0  |  3  |  6  |
+-----+-----+-----+-----+-----+-----+-----+

이 배열을 생성하기위한 의사 코드를 보자 :

Procedure ConstructTree(Item, SegmentTree, low, high, position):
if low is equal to high
    SegmentTree[position] := Item[low]
else
    mid := (low+high)/2
    constructTree(Item, SegmentTree, low, mid, 2*position+1)
    constructTree(Item, SegmentTree, mid+1, high, 2*position+2)
    SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
end if

먼저 값의 입력을 가져 와서 Item 배열의 길이를 크기로 사용하여 infinity SegmentTree 배열을 초기화합니다. 우리는 다음을 사용하여 프로 시저를 호출합니다.

  • 낮음 = 항목 배열의 시작 인덱스입니다.
  • 높음 = 아이템 배열의 인덱스 끝내기.
  • position = 0은 세그먼트 트리의 루트 를 나타냅니다.

이제 예제를 사용하여 절차를 이해해 보겠습니다. 새로운 예 (-1, 2, 4, 0)

Item 배열의 크기는 4 입니다. 길이 (4 * 2) - 1 = 7 배열을 만들고 infinity 초기화합니다. 매우 큰 값을 사용할 수 있습니다. 배열은 다음과 같습니다.

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | inf | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

이것은 재귀 적 프로 시저이기 때문에 각 호출에서 low , high , position , midcalling line 을 추적하는 재귀 테이블을 사용하여 ConstructTree 의 연산을 볼 수 있습니다. 먼저 ConstructTree (Item, SegmentTree, 0, 3, 0)를 호출합니다. 여기에서 lowhigh 과 같지 않습니다. mid 얻습니다. calling line 은이 명령문 다음에 calling line 되는 ConstructTree 나타냅니다. 프로 시저 내부의 ConstructTree 호출을 각각 12로 나타냅니다. 우리의 테이블은 다음과 같습니다.

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+

ConstructTree-1 을 호출하면 low = 0 , high = mid = 1 , position = 2*position+1 = 2*0+1 = 1 됩니다. 당신이 알아 차릴 수있는 한가지는 2*position+1루트 의 왼쪽 자식이며 1 입니다. low 값이 high 값과 같지 않기 때문에 우리는 mid 값을 얻습니다. 우리의 테이블은 다음과 같습니다.

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+

다음 재귀 호출에서 우리는 low = 0 , high = mid = 0 , position = 2*position+1 = 2*1+1=3 합니다. 다시 인덱스 1 의 왼쪽 자식은 3 입니다. 여기에서 lowhigh 때문에 SegmentTree[position] = SegmentTree[3] = Item[low] = Item[0] = -1 합니다. SegmentTree 배열은 다음과 같습니다.

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf |  -1 | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

재귀 테이블은 다음과 같습니다.

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   0  |     3    |     |              |
+-----+------+----------+-----+--------------+

그래서 -1 이 올바른 위치에 있다는 것을 알 수 있습니다. 이 재귀 호출이 완료되었으므로 우리는 재귀 테이블의 이전 행으로 돌아갑니다. 탁자:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+

우리의 절차에서는 ConstructTree-2 호출을 실행합니다. 이번에는 low = mid+1 = 1 , high = 1 , position = 2*position+2 = 2*1+2 = 4 합니다. 우리의 calling line2로 변경됩니다. 우리는 얻는다 :

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+

lowhigh 과 같으므로 SegmentTree[position] = SegmentTree[4] = Item[low] = Item[1] = 2 합니다. 우리의 SegmentTree 배열 :

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf |  -1 |  2  | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

우리 재귀 테이블 :

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+
|  1  |   1  |     4    |     |              |
+-----+------+----------+-----+--------------+

다시 한 번 볼 수 있습니다. 2 는 올바른 위치에 있습니다. 이 재귀 호출 후에 우리는 재귀 테이블의 이전 행으로 돌아갑니다. 우리는 얻는다 :

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+

우리는 SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1 이다. 우리의 SegmentTree 배열 :

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf |  -1 | inf |  -1 |  2  | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

이 재귀 호출이 완료되었으므로 우리는 재귀 테이블의 이전 행으로 돌아가서 ConstructTree-2 호출합니다.

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       2      |
+-----+------+----------+-----+--------------+

세그먼트 트리의 왼쪽 부분이 완성되었음을 알 수 있습니다. 이러한 방식으로 계속 진행한다면 전체 절차를 완료 한 후 마침내 완성 된 SegmentTree 배열을 얻습니다.

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  0  |  -1 |  2  |  4  |  0  |
+-----+-----+-----+-----+-----+-----+-----+

SegmentTree 배열을 구성하는 시간과 공간의 복잡성은 O(n) . 여기서 nItem 배열의 요소 수를 나타냅니다. 우리의 생성 된 SegmentTree 배열은 범위 최소 쿼리 (RMQ) 를 수행하는 데 사용될 수 있습니다. Range Maximum Query 를 수행하기위한 배열을 만들려면 다음 행을 대체해야합니다.

SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])

와:

SegmentTree[position] := max(SegmentTree[2*position+1], SegmentTree[2*position+2])

최소값 쿼리 실행

RMQ를 수행하는 절차는 이미 소개 부분에 나와 있습니다. 범위 최소 쿼리를 확인하기위한 의사 코드는 다음과 같습니다.

Procedure RangeMinimumQuery(SegmentTree, qLow, qHigh, low, high, position):
if qLow <= low and qHigh >= high        //Total Overlap
    Return SegmentTree[position]
else if qLow > high || qHigh < low      //No Overlap
    Return infinity
else                                    //Partial Overlap
    mid := (low+high)/2
    Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
end if

여기, qLow = The lower range of our query , qHigh = The upper range of our query qLow = The lower range of our query qHigh = The upper range of our query . low = starting index of Item array , high = Finishing index of Item array , position = root = 0 . 이제 이전에 작성한 예제를 사용하여 절차를 이해해 보겠습니다.

세그먼트 트리 예

우리의 SegmentTree 배열 :

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  0  |  -1 |  2  |  4  |  0  |
+-----+-----+-----+-----+-----+-----+-----+

우리는 범위 [1, 3] 에서 최소값을 찾고자합니다.
이것은 재귀 적 절차이기 때문에 qLow , qHigh , low , high , position , midcalling line 추적하는 재귀 테이블을 사용하여 RangeMinimumQuery 의 연산을 볼 수 있습니다. 먼저 RangeMinimumQuery (SegmentTree, 1, 3, 0, 3, 0 )를 calling line . 처음 두 조건은 충족되지 않습니다 (부분적으로 겹침). mid 됩니다. calling line 은이 후에 호출되는 RangeMinimumQuery 나타냅니다 procedure 내에서 RangeMinimumQuery 호출을 각각 12 로 지정합니다. 우리 테이블은 다음과 같습니다.

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

따라서 RangeMinimumQuery-1 을 호출하면 low = 0 , high = mid = 1 , position = 2*position+1 = 1 합니다. 당신이 알아챌 수있는 한 가지는, 2*position+1노드 의 왼쪽 자식입니다. 그 말은 우리가 뿌리 의 왼쪽 아이를 확인한다는 뜻입니다. [1,3] 부분적으로, 처음 두 가지 조건이 충족되지 [0,1]을 겹쳐 있기 때문에, 우리는 얻을 mid . 우리 테이블 :

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+

다음 재귀 호출에서 우리는 low = 0 , high = mid = 0 , position = 2*position+1 = 3 합니다. 우리는 우리 나무의 가장 왼쪽 잎에 닿습니다. [1,3][0,0] 과 겹치지 않기 때문에 호출 함수에 infinity 를 반환합니다. 재귀 테이블 :

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   0  |     3    |     |              |
+------+-------+-----+------+----------+-----+--------------+

이 재귀 호출이 완료되었으므로 우리는 재귀 테이블의 이전 행으로 돌아갑니다. 우리는 얻는다 :

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+

이 절차에서는 RangeMinimumQuery-2 호출을 실행합니다. 이번에는 low = mid+1 = 1 , high = 1position = 2*position+2 = 4 합니다. 우리의 calling line changes to **2** . 우리는 얻는다 :

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       2      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  1  |   1  |     4    |     |              |
+------+-------+-----+------+----------+-----+--------------+

그래서 우리는 이전 노드의 오른쪽 자식에게 갈 것입니다. 이번에는 전체 오버랩이 있습니다. 우리는 SegmentTree[position] = SegmentTree[4] = 2 값을 반환합니다.

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

위로 함수를 호출 할 때, 우리는 두 개의 호출 함수 중 반환 된 두 값 중 최소값을 확인합니다. 분명히 최소값은 2 이고, 호출 함수에 2 를 반환합니다. 재귀 테이블은 다음과 같습니다.

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

이제 세그먼트 트리의 왼쪽 부분을 살펴 보았습니다. 이제 여기서 RangeMinimumQuery-2 를 호출 할 것입니다. 우리는 low = mid+1 = 1+1 =2 , high = 3 , position = 2*position+2 = 2 통과시킬 것입니다. 우리 테이블 :

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  2  |   3  |     2    |     |              |
+------+-------+-----+------+----------+-----+--------------+

총 겹침이 있습니다. 따라서 우리는 값을 반환합니다 : SegmentTree[position] = SegmentTree[2] = 0 . 우리는이 두 아이가 호출 된 곳에서 재귀로 돌아와서 (4,0) 의 최소값 인 0 을 반환하고 값을 반환합니다.

프로 시저를 실행 한 후, 우리는 3 인덱스 -하는 인덱스 - 1에서 최소 인 0을 얻는다.

이 프로 시저의 런타임 복잡성은 O(logn) 여기서 nItems 배열의 요소 수입니다. 범위 최대 쿼리를 수행하려면 다음 행을 대체해야합니다.

Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))

와:

Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))

게으른 전파

예를 들어 이미 세그먼트 트리를 만들었습니다. 배열의 값을 업데이트해야합니다. 그러면 세그먼트 트리의 리프 노드뿐만 아니라 일부 노드의 최소 / 최대 값도 변경됩니다. 예제를 보자.

세그먼트 트리 예

이것은 8 요소의 최소 세그먼트 트리입니다. 빠른 알림을 제공하기 위해 각 노드는 그 옆에 언급 된 범위의 최소값을 나타냅니다. 예를 들어, 배열의 첫 번째 항목의 값을 3 만큼 증가시키고 싶다고합시다. 어떻게 할 수 있니? 우리는 RMQ를 수행하는 방식을 따를 것입니다. 프로세스는 다음과 같습니다.

  • 처음에는 루트를 횡단합니다. [0,0][0,7] 과 부분적으로 겹치 므로 우리는 양방향으로갑니다.
    • 왼쪽 하위 트리에서 [0,0][0,3] 과 부분적으로 겹치고 양쪽 방향으로갑니다.
      • 왼쪽 하위 트리에서 [0,0][0,1] 과 부분적으로 겹치고 두 방향으로 이동합니다.
        • 왼쪽 하위 트리에서 [0,0][0,0] 과 완전히 겹치고, 리프 노드 이후로 s 값을 3 만큼 증가시켜 노드를 업데이트합니다. -1 + 3 = 2 값을 반환합니다.
        • 오른쪽 하위 트리에서 [1,1][0,0] 과 겹치지 않으며 노드 ( 2 )에서 값을 반환합니다.
          이 두 반환 값 ( 2 , 2 )의 최소값은 2 이므로 현재 노드의 값을 업데이트하고 반환합니다.
      • 오른쪽 서브 트리 [2,3][0,0] 과 겹치지 않으며 노드의 값을 반환합니다. ( 1 ).
        이 두 반환 값 ( 2 , 1 )의 최소값은 1 이므로 현재 노드의 값을 업데이트하고 반환합니다.
    • 오른쪽 하위 트리 [4,7][0,0] 과 겹치지 않습니다. 노드의 값을 반환합니다. ( 1 ).
  • 마지막으로 두 개의 반환 값 (1,1) 중 최소값이 1 이므로 루트 노드의 값이 업데이트됩니다.

단일 노드 업데이트에는 O(logn) 시간 복잡도가 필요합니다. 여기서 n 은 리프 노드의 수입니다. 따라서 우리가 i 에서 j로 몇몇 노드를 업데이트하라는 요청을 받으면 O(nlogn) 시간의 복잡성이 필요합니다. 이것은 n 의 큰 값에 대해 성 가시다. 게으르다, 즉 필요할 때만 일을하자. 방법? 간격을 업데이트해야 할 경우 노드를 업데이트하고 업데이트해야하는 자식을 표시하고 필요할 때 노드를 업데이트합니다. 이를 위해서는 세그먼트 트리와 동일한 크기의 게으른 배열이 필요합니다. 처음에 지연 배열의 모든 요소는 보류중인 업데이트가 없음을 나타내는 0 이됩니다. lazy [i] 에 0이 아닌 요소가 있으면이 요소는 쿼리 작업을 수행하기 전에 세그먼트 트리에서 노드 i 를 업데이트해야합니다. 우리가 어떻게 그걸 할거야? 예제를 살펴 보겠습니다.

예를 들어, 몇 가지 쿼리를 실행하려고한다고 가정 해 봅시다. 이것들은:

  • [0,3]3 만큼 증가시킵니다.
  • [0,3]1 씩 증가시킵니다.
  • [0,0]2 립니다.

[0,3]을 3 씩 증가시킵니다.

  • 루트 노드부터 시작합니다. 처음에는이 값이 최신인지 확인합니다. 이를 위해 지연 배열이 0 인지 확인합니다. 이는 값이 최신임을 의미합니다. [0,3]은 [0,7] 과 부분적으로 겹칩니다. 그래서 우리는 두 가지 방향으로갑니다.

    • 왼쪽 하위 트리에는 보류중인 업데이트가 없습니다. [0,3] 완전히 [0,3] 중첩. 그래서 노드의 값을 3으로 갱신합니다. 따라서 값은 -1 + 3 = 2가 됩니다. 이번에는 우린 끝까지 다가 가지 않을거야. 아래로 내려가는 대신 현재 노드의 게으른 트리에서 해당 자식을 업데이트하고 3 씩 증가시킵니다. 또한 현재 노드의 값을 반환합니다.
    • 오른쪽 하위 트리에는 보류중인 업데이트가 없습니다. [0,3] 은 겹쳐지지 않습니다 [4,7] . 따라서 현재 노드 (1) 의 값을 반환합니다.
      반환되는 값의 최소값 ( 2 , 1 )은 1 입니다. 루트 노드를 1로 업데이트합니다.

우리의 Segment Tree와 Lazy Tree는 다음과 같습니다.

세그먼트 나무와 게으른 나무

Lazy Tree의 노드에있는 0이 아닌 값은 해당 노드와 그 아래에 보류중인 업데이트가 있음을 나타냅니다. 필요한 경우 업데이트 해 드리겠습니다. 우리가 물어 보면 범위 [0,3] 의 최소값은 무엇인가? 루트 노드의 왼쪽 하위 트리에 올 것이고 보류중인 업데이트가 없으므로 2 가 반환됩니다. 따라서이 과정은 세그먼트 트리 알고리즘의 정확성에 영향을 미치지 않습니다.

[0,3]을 1 씩 증가시킵니다.

  • 루트 노드부터 시작합니다. 대기중인 업데이트가 없습니다. [0,3]은 [0,7] 과 부분적으로 겹칩니다. 그래서 우리는 양방향으로갑니다.
    • 왼쪽 하위 트리에는 보류중인 업데이트가 없습니다. [0,3] 완전히 [0,3] 중첩. 현재 노드를 업데이트합니다 ( 2 + 1 = 3) . 이것은 내부 노드이기 때문에 Lazy Tree의 자식 노드를 1 씩 증가시킵니다. 또한 현재 노드 ( 3 )의 값을 반환합니다.
    • 오른쪽 하위 트리에는 보류중인 업데이트가 없습니다. [0,3] 은 겹쳐지지 않습니다 [4,7] . 현재 노드 ( 1 )의 값을 반환합니다.
  • 최소 두 개의 반환 값 ( 3 , 1 )을 취하여 루트 노드를 업데이트합니다.

우리의 Segment Tree와 Lazy Tree는 다음과 같습니다 :

세그먼트 트리 및 지연 트리 업데이트 됨

보시다시피 Lazy Tree에 업데이트가 누적되지만 누를 필요는 없습니다. 이것이 게으른 전파의 의미입니다. 우리가 그것을 사용하지 않았다면 우리는 잎에 값을 밀어 넣어야했기 때문에 불필요한 시간 복잡성을 초래했습니다.

[0,0]을 2 씩 증가시킵니다.

  • 루트 노드부터 시작합니다. 근음이 최신이고 [0,0]이 부분적으로 [0,7] 과 겹치기 때문에 우리는 양방향으로갑니다.
    • 왼쪽 하위 트리에서 현재 노드는 최신 상태이고 [0,0]은 부분적으로 [0,3] 과 겹치므로 두 방향으로 이동합니다.
      • 왼쪽 하위 트리에서 지연 트리의 현재 노드의 값이 0이 아닙니다. 따라서 아직이 노드로 전파되지 않은 업데이트가 있습니다. 먼저 세그먼트 트리에서이 노드를 업데이트 할 것입니다. 그래서 -1 + 4 = 3이 됩니다. 그런 다음이 4 를 게으른 나무의 자식에게 전파 할 것입니다. 현재 노드를 이미 업데이트 했으므로 지연 트리의 현재 노드 값을 0으로 변경 합니다. 그러면 [0,0]은 [0,1] 과 부분적으로 겹치므로 양쪽 방향으로갑니다.
        • 왼쪽 노드에서 지연 트리의 현재 노드에 0이 아닌 값이 있으므로 값을 업데이트해야합니다. 그래서 값을 -1 + 4 = 3으로 갱신합니다. 이제, 이후는 [0,0] 전체적으로, 우리는 3 + 2 = 5 현재 노드의 값을 업데이트 [0,0] 중첩. 이것은 잎 노드이므로 더 이상 값을 전달할 필요가 없습니다. 우리는 모든 노드가이 노드까지 전파 되었기 때문에 지연 트리의 해당 노드를 0으로 업데이트합니다. 현재 노드 ( 5 )의 값을 반환합니다.
        • 오른쪽 노드에서 값을 업데이트해야합니다. 따라서 값은 4 + 2 = 6이 됩니다. [0,0][1,1] 과 겹치지 않기 때문에 현재 노드 ( 6 )의 값을 반환합니다. 또한 Lazy Tree의 값을 0으로 업데이트합니다. 리프 노드이므로 전파가 필요하지 않습니다.
          최소 두 개의 반환 값 ( 5 , 6 )을 사용하여 현재 노드를 업데이트합니다. 현재 노드 ( 5 )의 값을 반환합니다.
      • 오른쪽 하위 트리에는 보류중인 업데이트가 있습니다. 노드의 값을 1 + 4 = 5로 갱신합니다. 이것은 잎 노드가 아니기 때문에, 값을 우리의 Lazy Tree에있는 자식 노드로 전달하고 현재 노드를 0으로 업데이트합니다. [0,0][2,3] 와 겹치지 않기 때문에 현재 노드 ( 5 )의 값을 반환합니다.
        우리는 반환 된 값 (5, 5)의 최소를 사용하여 현재 노드를 업데이트하고 값을 반환 (5).
    • 오른쪽 하위 트리에는 보류중인 업데이트가 없으며 [0,0][4,7] 과 겹치지 않으므로 현재 노드 ( 1 )의 값을 반환합니다.
  • 최소 두 개의 반환 값 ( 5 , 1 )을 사용하여 루트 노드를 업데이트합니다.

우리의 Segment Tree와 Lazy Tree는 다음과 같습니다 :

세그먼트 트리 및 지연 트리 업데이트 됨

필요한 경우 [0,0] 의 값이 모든 증가를 얻음을 알 수 있습니다.

이제 당신이 범위 [3,5] 의 최소값을 찾도록 요청 받았을 때,이 점을 이해했다면, 쿼리가 어떻게 돌아갈 지 쉽게 알 수 있고 반환 값은 1이 됩니다. 우리의 세그먼트 트리와 게으른 나무는 다음과 같습니다.

쿼리 후 게으른 트리 및 세그먼트 트리

우리는 계류중인 업데이트에 대해 Lazy Tree를 확인하는 제약 조건이 추가 된 RMQ를 찾는 과정에서 간단히 따라했습니다.

우리가 할 수있는 또 다른 일은 현재 노드의 자식 노드가 무엇인지를 알기 때문에 각 노드에서 값을 반환하는 것이 아니라 단순히이 두 노드의 최소값을 확인하기 만하면됩니다.

지연 전파 (Lazy Propagation)에서 업데이트하기위한 의사 코드는 다음과 같습니다.

Procedure UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, low, high, position):
if low > high                                                //out of bounds
    Return
end if
if LazyTree[position] is not equal to 0                      //update needed
    segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high                              //non-leaf node    
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
    end if
    LazyTree[position] := 0
end if
if startRange > low or endRange < high                       //doesn't overlap
    Return
end if
if startRange <= low && endRange >= high                     //total overlap
    segmentTree[position] := segmentTree[position] + delta
    if low is not equal to high
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
    end if
    Return
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, low, mid, 2 * position + 1)
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, mid + 1, high, 2 * position + 2)
segmentTree[position] := min(segmentTree[2 * position + 1], 
                                                    segmentTree[2 * position + 2])

그리고 Lazy Propagation의 RMQ에 대한 의사 코드는 다음과 같습니다.

Procedure RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, low, high, position):
if low > high
    Return infinity
end if
if LazyTree[position] is not equal to 0                      //update needed
    segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high
        segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high                              //non-leaf node    
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + LazyTree[position]
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + LazyTree[position]
    end if
    LazyTree[position] := 0
end if
if qLow > high and qHigh < low                                //no overlap
    Return infinity
end if
if qLow <= low and qHigh >= high                              //total overlap
    Return segmentTree[position]
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
Return min(RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, 
                                        low, mid, 2 * position + 1),
           RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
                                        mid + 1, high, 2 * position + 1)


Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow