Przetwarzaj wstępnie tablicę do zliczania elementu w wycinku (redukcja do RMQ?)

Biorąc pod uwagę tablicę liczb naturalnych , gdzie jest stałą, chcę odpowiedzieć na zapytania o formie: „ile razy pojawia się w tablicy między indeksami i ”? $a_1,\ldots,a_n$ $\leq k$ $k$ $O(1)$ $m$ $i$ $j$

Tablica powinna być wstępnie przetworzona w czasie liniowym. W szczególności chciałbym wiedzieć, czy nastąpiło ograniczenie zapytania minimalnego zakresu.

Jest to równoważne z RMQ w przypadku, gdy i chcesz zapytać o liczbę jednych w przedziale. Więc można używać go . ^{Nie mogłem odpowiedzieć na własne pytanie z powodu ograniczeń SE.} $k=1$

algorithms arrays algorithm-design andy
źródło

Możesz zmniejszyć rozróżnienie elementu na problem (w czasie liniowym). Być może mówienie o modelu jest w porządku?

Aryabhata

@Aryabhata co to właściwie jest problem odróżnienia elementu? Teraz czytam to: en.wikipedia.org/wiki/Range_Queries

andy

Jest to o wiele łatwiejsze niż RMQ. Wskazówka: Ponieważ k jest stałą, przetwarzanie wstępne może spędzać czas proporcjonalnie do kn i nadal liczy się jako czas liniowy.

Tsuyoshi Ito

@Aryabhata: Redukcja, o której myślę, że mówisz, nie działa, ponieważ k jest stałą w tym problemie.

Tsuyoshi Ito

Na wszelki wypadek, jeśli tablica jest podana na początku i nie jest później aktualizowana, RMQ to przesada, jak zasugerowałem w moim wcześniejszym komentarzu.

Tsuyoshi Ito

Odpowiedzi:

Ponieważ jest stałe, możemy przechowywać liczbę każdego elementu w zakresie dla w w czas i przestrzeń. Podstawowa obserwacja polega na tym, że można utworzyć tablicę dwuwymiarową w czasie , a następnie zapytać o zakresy, znajdując różnicę wskaźników w stałym czasie. $k$ $0..m$ $0\leq m \lt n$ $0..n$ $O(nk) = O(n)$ count[pos][elem] = occurences of 'elem' in the indices 0..pos $O(nk)$ $i,j$

Przetwarzanie wstępne

initialise count[pos][elem] to 0 for all elem, pos
for pos=0 to n
  for num=0 to k
      count[pos][num] = (0 if pos==0 else count[pos-1][num])
  count[pos][arr[pos]] ++

Pytanie

(przy założeniu, że i, j są granicami włącznie)

if i == 0
  return count[j][m]
else
  return count[j][m] - count[i-1][m]

Jeśli tablica jest również aktualizowana podczas całego procesu zapytania, zamiast tablicy można użyć drzewa Fenwick (indeks binarny) . Umożliwia to aktualizację w i zapytanie w . $k$ count $O(\log n)$ $O(\log n)$

Przepraszamy za wszelkie problemy z tą odpowiedzią, to moja pierwsza.

złotawy
źródło