Struktura danych dla aktualizacji interwałów i zapytań o liczbę zer

Szukam struktury danych, która utrzymywałaby tablicę liczb całkowitych o rozmiarze , i pozwalała na następujące operacje w czasie . $t$ $n$ $O(\log n)$

$\text{increase}(a,b)$ , który zwiększa . $t[a],t[a+1],\ldots,t[b]$
$\text{decrease}(a,b)$ , co zmniejsza . $t[a],t[a+1],\ldots,t[b]$
$\text{support}()$ , która zwraca liczbę indeksów takich, że . $i$ $t[i]\neq 0$

Obiecujesz, że każde połączenie do zmniejszenia można dopasować do poprzedniego połączenia, aby zwiększyć przy tych samych parametrach . Aplikacja, o której myślę, to algorytm linii prostej do obliczania w czasie obszaru zjednoczenia n danych prostokątów prostoliniowych. $a,b$ $O(n\log n)$

Drzewo quad miałoby rozmiar , więc nie jest to rozwiązanie. Drzewa Fenwick lub Interval mają odpowiedni smak, ale nie widzę, jak je rozszerzyć, aby wspierały powyższe operacje. $\Theta(n^2)$

ds.data-structures cg.comp-geom

— Christoph Dürr
źródło

Drzewa Fenwicka nie skorzystałyby z obietnicy, że „każde wezwanie do zmniejszenia można dopasować do poprzedniego wywołania, aby zwiększyć przy tych samych parametrach a, b”, więc może istnieć prostsze rozwiązanie, korzystając z tej obietnicy (ale na razie mi ucieka).

— Jeremy,

Ponieważ liczba danych wejściowych, które możesz mieć, wynosi najwyżej (możesz wykryć powtórzenia i nie wstawiać do struktury danych), nadal uzyskujemy wydajność przy użyciu wspólnej struktury danych drzewa miar. Zobacz cosy.sbg.ac.at/~ksafdar/data/courses/SeminarADS/… slajd 47-52.

n^{2}

$n^2$

O (\log n)

$O(\log n)$

— Chao Xu

Jérémie i Chao Xu. Dziękuję za komentarze. Rozumiem teraz, w jaki sposób można wykorzystać Drzewo interwałów do utrzymania całkowitej długości połączenia zmieniającego się zestawu interwałów. To w rzeczywistości bardzo urocza struktura danych.

— Christoph Dürr

W przypadku ogólnego problemu ze strukturą danych wyszukiwanie w wymaga czasu gdzie jest rozmiarem listy aktywne pary współrzędnych. Ale tak naprawdę dla algorytmu linii prostej więc przestrzeń pozostaje liniowa. Problem jest nadal otwarty dla struktury danych z lepszą przestrzenią niż , gdy .

\log (n^{2}) \in O (\log (n))

$\log(n^2)\in O(\log(n))$

O (p) \subset O (n^{2})

$O(p)\subset O(n^2)$

p

$p$

p \in O (n)

$p\in O(n)$

O (p)

$O(p)$

p \in ω (n)

$p\in\omega(n)$

— Jeremy

Oto fajny link, w którym możesz przetestować swoje implementacje pod kątem

— Erel Segal-Halevi

Odpowiedzi:

Użyj drzewa segmentów - rekurencyjnej partycji zakresu na mniejsze zakresy. Każdy przedział operacji aktualizacji można podzielić na zakresów w tej partycji rekurencyjnej. Dla każdego zakresu przechowuj: $[1,n]$ $[a,b]$ $O(\log n)$ $[x,y]$

Liczba w odstępach , że została zwiększona, a nie zmniejszyła się w taki sposób, to jeden z przedziałów, w którym rozdziela $c(x,y)$ $[a,b]$ $[x,y]$ $[a,b]$
Liczba komórek, które nie są objęte podzielonymi podzbiorami przedziałów o wartości lub niższej w rekurencji $u(x,y)$ $[x,y]$

Następnie, jeśli jest rekurencyjnie podzielony na i , mamy dzięki czemu możemy aktualizować każdą wartość w stałym czasie, gdy inne dane dla zakres się zmienia. Na każde zapytanie wsparcia można odpowiedzieć, patrząc na . $[x,y]$ $[x,z]$ $[z+1,w]$

u (x, y) = {\begin{cases} 0 & if c (x, y) > 0 \\ u (x, z) + u (z + 1, y) & otherwise \end{cases}

$u(x,y)=\begin{cases} 0&\text{if }c(x,y)>0\\ u(x,z)+u(z+1,y)&\text{otherwise} \end{cases}$

u (x, y)

$u(x,y)$

u (1, n)

$u(1,n)$

Aby wykonać operację zwiększenia , podziel na zakresy , zwiększ dla każdego z tych zakresów i użyj powyższego wzoru, aby ponownie obliczyć dla każdego z tych zakresów i każdego z ich przodków. Operacja zmniejszania jest taka sama z dekrementacją zamiast inkrementem. $(a,b)$ $[a,b]$ $O(\log n)$ $c(x,y)$ $u(x,y)$

— David Eppstein
źródło

Nie sądzę, że rozumiem twoją drugą kulę. Które komórki w poddrzewie z zgnilizną oznaczoną nie są objęte podzielonymi podzbiorami przedziałów w ? Czy nie obejmuje całego zakresu , więc ?

[x, y]

$[x,y]$

[x, y]

$[x,y]$

[x, y]

$[x,y]$

u (x, y) = 0

$u(x,y) = 0$

— jbapple

To zależy od tego, jakie operacje zwiększania wykonałeś. Początkowo wszystkie z nich są odkryte, ale jeśli zwiększysz mały interwał w ciągu (lub dowolny interwał, który zaczyna się lub kończy w ciągu lub który zawiera w swojej partycji), zmniejsza się.

[x, y]

$[x,y]$

[x, y]

$[x,y]$

[x, y]

$[x,y]$

— David Eppstein

Czy możesz podać przykład?

— jbapple

Załóżmy, że twoim interwałem są liczby [1,8]. Jest on rekurencyjnie podzielony na [1,4], [4,8], a następnie [1,2], [3,4], [5,6] i [7,8], a następnie wszystkie zakresy jednoelementowe. Początkowo wszystko jest odkryte, wszystkie c [x, y] = 0, a każdy zakres ma u = swoją długość. Ale załóżmy, że wykonujesz operację zwiększania [2,6]. Maksymalne zakresy O (log n), na które można rozkładać [2,6], wynoszą [2,2], [3,4] i [5,6], więc dla tych trzech ustawiamy c [x, y] zakresy do 1. Zgodnie ze wzorem w mojej odpowiedzi powoduje to, że u [x, y] również dla tych trzech zakresów staje się 0. u [1,2] staje się 1, u [1,4] również staje się 1, u [ 5,8] = 2, au [1,8] = 1 + 2 = 3

— David Eppstein

Możesz obsłużyć i w i w czasie . $\text{increase}$ $\text{decrease}$ $O(\sqrt{n}\log n)$ $\text{support}$ $O(1)$ Kluczową ideą jest podzielenie tabeli na grupy o rozmiarze . Następnie każda operacja modyfikująca ( lub ) działa na co najwyżej grupach i tylko tych na końcu zakresu ( i , w twoim sformułowaniu) weź czas. $\Theta(\sqrt{n})$ $\text{increase}$ $\text{decrease}$ $O(\sqrt{n})$ $a$ $b$ $\omega(\log n)$

— jbapple
źródło

Dlaczego nie podejść do tego ograniczenia? Zamiast segmentować do segmentów , możemy zamiast tego utworzyć drzewo podobne do tego: 1 / \ 2 3 / \ / \ 4 5 6 7 Z czego aktualizując, bierzesz dla wszystkich operacji.

O (\sqrt{n})

$O(\sqrt{n})$

O (\log n)

$O(\log{n})$

— S. Pek,