Znajdowanie najbliższa liczba w przedziale

Question

myślałem problem, który przedstawia się następująco:

Mamy tablicę A liczb całkowitych o rozmiarze n, a mamy testowych sprawach T iw każdym przypadków testowych daje nam M numer i zakres [s, e] tj. otrzymujemy s i e, a my musimy znaleźć najbliższą liczbę m w zakresie tej macierzy (A [s] -A [e]).

Możesz założyć, że tablica ma indeks od 1 do n.

Na przykład:

A = {5, 12, 9, 18, 19} 
    m = 13 
    s = 4 and e = 5 

Więc odpowiedź powinna być 18.

Ograniczenia:

n<=10^5 
t<=n 

Wszystko mogę myśl jest O (n) rozwiązanie dla każdego przypadku testowego, i myślę, że istnieje lepsze rozwiązanie.

Answer 1

To jest przybliżony szkic: Utwórz dane z segment tree. W każdym węźle, oprócz zwykłych danych, takich jak indeksy lewy i prawy, przechowujesz również liczby znalezione w drzewie podrzędnym zrootowanym w tym węźle, przechowywane w posortowanej kolejności. Możesz to osiągnąć, budując drzewo segmentów w kolejności od dołu. W węźle tuż nad liściem przechowujesz wartości dwóch liści w posortowanej kolejności. W węźle pośrednim zachowujesz liczby w lewym elemencie podrzędnym i prawym elemencie potomnym, które możesz scalić ze sobą przy użyciu standardowego scalania. W drzewku znajdują się O (n) węzły, a przechowywanie tych danych powinno ogólnie zająć O (nlog (n)).

Po uzyskaniu tego drzewa, dla każdego zapytania, idź ścieżką, aż dojdziesz do odpowiedniego węzła (ów) w podanym zakresie ([s, e]). Jak pokazuje samouczek, jeden lub więcej różnych węzłów łączyłoby się, tworząc dany zakres. Ponieważ głębokość drzewa wynosi O (log (n)), jest to czas na zapytanie, aby osiągnąć te węzły. Każde zapytanie powinno być O (log (n)). Dla wszystkich węzłów, które leżą całkowicie w zakresie, znajdź najbliższy numer za pomocą wyszukiwania binarnego w posortowanej tablicy przechowywanej w tych węzłach. Ponownie, O (log (n)). Znajdź najbliższy spośród wszystkich, a to jest odpowiedź. W ten sposób możesz odpowiedzieć na każde zapytanie w czasie O (log (n)).

Samouczek, do którego linkuję, zawiera inne struktury danych, takie jak rzadka tabela, które są łatwiejsze do wdrożenia i powinny dać O (sqrt (n)) na zapytanie. Ale nie myślałem o tym zbyt wiele.

Answer 2

Jestem pewien, że nie istnieje szybsze rozwiązanie. Nieznaczna zmiana twojego problemu to:

Nie ma tablicy A, ale każdy przypadek testowy zawiera nieposortowaną tablicę liczb do przeszukania. (Fragment tablicy od A do s).

W takim przypadku nie ma lepszego sposobu niż wyszukiwanie liniowe dla każdego przypadku testowego.

Teraz, w jaki sposób oryginalny problem jest bardziej szczegółowy niż powyższa odmiana? Jedyną dodaną informacją jest to, że wszystkie plasterki pochodzą z tej samej tablicy. Nie sądzę, że to dodatkowe ograniczenie może być użyte do przyspieszenia algorytmicznego.

EDYCJA: Stoję poprawione. Struktura danych drzewa segmentów powinna działać.

Answer 3

posortuj tablicę i wykonaj wyszukiwanie binarne. złożoność: o (nlogn + logn * t)