세그먼트 트리 : x보다 작은 숫자

Question

this 문제를 해결하려고합니다.

이 문제에 대해 tutorial이 발견되었지만 O (로그 n) (x는 변경할 수 있음)에 x보다 작은 숫자가있는 세그먼트 트리를 작성하는 방법을 얻지 못합니다. 튜토리얼에서는 생략되었습니다.

아무에게도 어떻게 설명 할 수 있습니까?

Answer 1

은 꽤 간단

1. 저장소 (초기화 O(n * log n) 메모리 및 시간)을 특정 노드
   커버하는 범위 내의 모든 수치의 정렬 된 어레이.

2. 쿼리에 응답하려면 O(log n) 노드로 쿼리 세그먼트를 분해하고 (표준 최소/최대/합계 세그먼트 트리에 대해 수행되는 것과 같은 방식으로) 각 노드에 저장된 배열에 대해 이진 검색을 실행하십시오. x보다 작은 요소의 수를 찾으십시오. 쿼리 당 시간은 O(log^2 n)입니다. 분수 캐스케이드를 사용하여 O(log n)을 얻을 수도 있지만 필수는 아닙니다.