Präfixsummen im veränderlichen 2D-Array

Angenommen, ich habe ein 2D-Array M[n][n]von Ganzzahlen (tatsächlich ist Binär in Ordnung, aber ich bezweifle, dass es wichtig ist). Ich interessiere mich für wiederholte Abfragen der Form: Wenn ein Koordinatenpaar , was ist Natürlich können alle diese Werte in Zeitsumme berechnet werden , und danach nehmen Abfragen . Mein Array ist jedoch veränderbar, und jedes Mal, wenn ich einen Wert ändere, erfordert die offensichtliche Lösung ein -Update. $k,l$

\sum_{i = 0}^{k - 1} \sum_{j = 0}^{l - 1} M [i] [j] ?

$\sum_{i = 0}^{k-1} \sum_{j = 0}^{l-1} M[i][j]?$

O (n^{2})

$\mathcal O(n^2)$

O (1)

$\mathcal O(1)$

O (n^{2})

$\mathcal O(n^2)$

Wir können einen Quad-Baum erstellen M. Die Vorverarbeitung benötigt $\mathcal O(n^2\log(n))$ . Auf diese Weise können wir Abfragen in $\mathcal O(n\log(n))$ und Aktualisierungen in $\mathcal O(\log(n))$ .

Meine Frage ist:

Können wir die Abfragen erheblich verbessern, ohne die Updates zu stark zu beeinträchtigen?

Ich bin besonders daran interessiert, sowohl die Aktualisierungs- als auch die Abfrageoperationen sublinear zu machen und insbesondere beide auf $\mathcal O(n^\epsilon)$ .

Bearbeiten: Für einige weitere Informationen, obwohl ich denke, dass das Problem auch ohne diese weitere Einschränkung interessant ist, erwarte ich ungefähr $\mathcal O(n^3)$ Abfragen und über $\mathcal O(n^2)$ Updates. Das ideale Ziel ist es, die volle Laufzeit auf ungefähr $\mathcal O(n^{3+\epsilon})$ . Daher wäre für mich auch eine Situation interessant, in der ein Update $\mathcal O(n \log(n))$ während eine Abfrage $\mathcal O(\log(n))$ .

complexity-theory data-structures trees Mees de Vries
quelle

Mit einem 2D-Fenwick-Baum (auch bekannt als BIT-Baum) können Sie sowohl Aktualisierungen als auch Abfragen in . Hier gibt es eine Seite, die es beschreibt: geeksforgeeks.org/… . Haftungsausschluss: Ich habe nicht vollständig verstanden, wie dies selbst funktioniert.

O (\log n)

$O(\log n)$

j_random_hacker

Antworten:

Es gibt eine relativ einfache Lösung, bei der jede Abfrage und jedes Update in -Zeit durchgeführt werden kann. Die Datenstruktur verwendet Raum. $O(\log^2 n)$ $O(n^2)$

Wir werden "Granularitäten" der Datenstruktur haben, eine für jede Potenz von zwei so dass . Die Datenstruktur für die Granularität speichert die Summen $\lg n$ $2^m$ $1 \le 2^m \le n$ $2^m$

\sum_{i = k_{0} \cdot 2^{m}}^{(k_{0} + 1) \cdot 2^{m} - 1} \sum_{j = 0}^{l - 1} M [i, j]

$\sum_{i=k_0 \cdot 2^m}^{(k_0+1) \cdot 2^m -1} \sum_{j=0}^{l-1} M[i,j]$

für jedes . Diese Datenstruktur für die Granularität kann wiederum unter Verwendung von ausgeglichenen Bäumen (einer für jeden möglichen Wert von ) zum Speichern von Präfixsummen dargestellt werden. $k_0,l$ $2^m$ $n/2^m$ $k_0$

Um nun die Präfixsumme für wir das Intervall in eine Vereinigung von Intervallen der Zweierpotenzlänge auf; Es werden höchstens Intervalle benötigt. Für jedes solche Intervall mit einer Länge von wir die Datenstruktur der Granularität . Somit können Anfragen beantwortet werden , indem Sie Lookups in einen ausgeglichenen Baum, von denen jede nimmt Zeit, für eine Gesamtzeit von pro Abfrage. $k,l$ $[0,k-1]$ $\lg n$ $2^m$ $2^m$ $O(\log n)$ $O(\log n)$ $O(\log^2 n)$

Aktualisierungen können auch in . Um für jede Granularität aktualisieren, aktualisieren Sie den entsprechenden ausgeglichenen Baum in der Datenstruktur der Granularität . Dies sind -Updates in -balancierten Bäumen. Jedes dieser Verfahren dauert , sodass die Gesamtzeit beträgt . $O(\log^2 n)$ $M[i,j]$ $2^m$ $2^m$ $O(\log n)$ $O(\log n)$ $O(\log n)$ $O(\log^2 n)$

Schließlich wird die Datenstruktur der Granularität enthält Bäumen, die jeweils Mitnahmen bis Raum, so dass die Gesamtplatznutzung ist . $2^m$ $n/2^m$ $O(n)$ $O(n^2 \cdot (1 + 1/2 + 1/4 + \cdots)) = O(n^2)$

DW
quelle