세그먼트 트리를 사용하여 겹쳐진 간격의 총 길이를 찾으시겠습니까?

Question

우리는 예를 들어 [1; 4] [7; 13] [9; 14] 입력에 3 + 6 + 1 = 10을 반환해야 할 간격이 있습니다. 세그먼트 트리를 사용하여 간격을 동적으로 삽입하거나 삭제할 수있는 경우 이러한 간격의 총 길이를 찾는 방법이 있습니까?

P.S. : 세그먼트 트리를 사용하지 않고 이것을 생각했지만 시간 복잡성이 나를 만족시키지 못합니다.

는

Answer 1

의 간격이 어레이 [m, n]을 저장하고있는 것으로 가정 할 수에 감사드립니다. 또 다른 가정은 배열이 정렬된다는 것입니다.

당신이 작은 차이를 발견하기 만하면 모든 : 단지주의 깊게 0 위치를 처리

int totalIntervales = 0; 
for(int index = 0; index < array.length ; index++) 
{ 
    int currentIntrval = array[index, 1] - array[index, 0]; 
    int differnceFromPrevious = array[index, 1] - array[index- 1, 1] 
    totalIntervale += currentIntrval > differnceFromPrevious ? differnceFromPrevious : currentIntrval; 
} 
return totalIntervale; 

합니다.

Answer 2

Kobi/Maureinik 대답은 매우 비슷하지만 maxEnd에 변수를 추가하고 differenceFromPrevious가 음수가 아닌지 확인해야했습니다. 이 알고리즘은 여전히 ​​범위는 시작 요소에 분류되어 있다고 가정

int totalInterval = array[0, 1] - array[0, 0]; 
int maxEnd = array[0, 1]; 
for(int index = 1; index < array.length ; index++) { 
    int currentIntrval = array[index, 1] - array[index, 0]; 
    int differnceFromPrevious = array[index, 1] - maxEnd; 
    if(differenceFromPrevious >= 0) { 
    totalInterval += (currentIntrval > differnceFromPrevious) ? differnceFromPrevious : currentIntrval; 
    } 
    maxEnd = (maxEnd >= array[index, 1]) ? maxEnd : array[index, 1]; 
} 
return totalInterval; 

편집 (즉, 배열 [난, 0].) : 원래 totalInterval 로직의 고정 된 사고 사본 작동하지 않았다. differenceFromPrevoius <이 0이면 totalInterval을 그대로 두어야합니다.