Verarbeiten Sie ein Array zum Zählen eines Elements in einem Slice vor (Reduktion auf RMQ?)

Bei einem Array natürlicher Zahlen , wobei eine Konstante ist, möchte ich in -Anfragen der Form antworten : "Wie oft erscheint im Array zwischen den Indizes und "? $a_1,\ldots,a_n$ $\leq k$ $k$ $O(1)$ $m$ $i$ $j$

Das Array sollte in linearer Zeit vorverarbeitet werden. Insbesondere würde ich gerne wissen, ob es eine Reduzierung auf Range Minimum Query gibt.

Dies entspricht RMQ für den Fall, dass und Sie die Anzahl der Einsen innerhalb eines Intervalls abfragen möchten. So können wir nutzen es . ^{Ich konnte meine eigene Frage wegen der SE-Grenzen nicht beantworten.} $k=1$

algorithms arrays algorithm-design Andy
quelle

Sie können die Elementunterscheidbarkeit auf Ihr Problem reduzieren (in linearer Zeit). Vielleicht ist es angebracht, über ein Modell zu sprechen?

Aryabhata

@Aryabhata Was genau ist das Problem der Elementunterscheidbarkeit? Jetzt lese ich dies: en.wikipedia.org/wiki/Range_Queries

andy

Dies ist viel einfacher als RMQ. Hinweis: Da k eine Konstante ist, kann die Vorverarbeitung Zeit proportional zu kn verbringen und zählt immer noch als lineare Zeit.

Tsuyoshi Ito

@Aryabhata: Die Reduktion, von der ich denke, dass Sie sprechen, funktioniert nicht, weil k eine Konstante in diesem Problem ist.

Tsuyoshi Ito

Nur für den Fall, dass das Array zu Beginn angegeben und danach nicht aktualisiert wird, ist RMQ ein Overkill, wie ich in meinem früheren Kommentar vorgeschlagen habe.

Tsuyoshi Ito

Antworten:

Da konstant ist, können wir die Anzahl jedes Elements im Bereich für in in Zeit und Raum speichern . Die primäre Beobachtung ist, dass Sie ein zweidimensionales Array in -Zeit erstellen und dann Bereiche abfragen können, indem Sie die Differenz der Indizes in konstanter Zeit ermitteln. $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$

Vorverarbeitung

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]] ++

Abfrage

(nimmt an, dass i, j beide inklusive Grenzen sind)

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

$k$ count $O(\log n)$ $O(\log n)$

Entschuldigung für alle Probleme mit dieser Antwort, es ist meine erste.

Goldy
quelle