Segmentbaum Grundlagen

Geschrieben von Timon Gehr.

Mögliche Problemstellungen

  • Die N+1 Städte von Absurdistan sind alle in einer Reihe angeordnet und es gibt jeweils genau eine Strasse zwischen zwei Städten, die in dieser Reihe nebeneinander liegen. Es gibt keine weiteren Strassen zwischen Städten. Für jede der N Strassen wird ein Wegzoll erhoben. Der Wegzoll, der für eine bestimmte Strasse erhoben wird kann sich gelegentlich ändern. Die Bewohner von Absurdistan wollen manchmal von einer Stadt in die andere fahren. Kannst du ihnen helfen, zu bestimmen, wieviel Wegzoll sie für so einen Weg insgesamt bezahlen müssen? In der Eingabe gibt es insgesamt Q Ereignisse: Entweder ändert sich der Wegzoll für eine Mautstelle, oder ein Bewohner möchte von Stadt A nach Stadt B reisen, und du sollst bestimmen, wieviel Wegzoll das kostet.
  • Entwickle eine Datenstruktur, die eine Menge von natürlichen Zahlen darstellt, wobei einfügen und entfernen einer Zahl effizient sein soll. Zusätzlich soll die Datenstruktur die folgende Operation effizient unterstützen: Berechne den grössten gemeinsamen Teiler aller Zahlen in der Menge.

Lösung: Segmentbaum

Ein Segmentbaum ist eine Datenstruktur, die für jeden Index in einem bestimmten Bereich einen Wert abspeichern kann, ähnlich wie ein Array.

Zusätzlich zu aktualisieren und auslesen eines Wertes erlaubt ein Segmentbaum aber einige weitere Operationen: Es ist möglich, effizient eine Zusammenfassung aller Werte in einem zusammenhängenden Index-Bereich abzufragen, wie z.B. die Summe aller Werte in einem solchen Bereich oder das Maximum aller Werte in einem solchen Bereich. (Unter bestimmten Bedingungen können sogar alle Werte in einem Bereich zusammen aktualisiert werden, was wir in diesem Dokument jedoch noch nicht diskutieren). Jede dieser Operationen ist effizient: Ihre Laufzeit ist logarithmisch in der Grösse des Index-Bereiches, welchen der Segmentbaum abspeichern kann.

Segmentbäume

Gegeben sei eine beliebige Operation \(\circ \) mit \((v₁\circ v₂)\circ v₃ = v₁\circ (v₂\circ v₃) = v₁\circ v₂\circ v₃\). Das heisst, dass nur die Werte \(vᵢ\) und möglicherweise ihre Reihenfolge eine Rolle spielt, aber nicht, in welcher Reihenfolge wir nebeineinander liegende Werte miteinander verrechnen: Wir sagen dass ∘ assoziativ ist. Wir schreiben allgemein für das Resultat der Operation auf \(k\) Werten: \(v₁\circ v₂\circ \ldots \circ vₖ\). (\(\circ \) könnte zum Beispiel für \(+\), oder \(\max\) stehen.)

Der Segmentbaum ist eine einfache Datenstruktur, welche die Werte \(v₁,...,vₙ\) darstellt und effizient folgende Operationen auf Segmenten von Werten unterstützt: (Für die Laufzeitangaben nehmen wir an, dass \(\circ \) in konstanter Zeit ausgerechnet werden kann.)

set(i,v) – führe Zuweisung \(vᵢ\leftarrow v\) aus. Laufzeit: \(O(\log n)\). get(l,r) – für \(l\leq r\), berechne \(vₗ\circ vₗ₊₁\circ \ldots \circ vᵣ₋₁\circ vᵣ\). Laufzeit: \(O(\log n)\).

Die Grundidee ist, die Werte \(v₁,\ldots ,vₙ\) in einem Binärbaum anzuordnen, der \(\Theta (n)\) Knoten, jedoch nur \(O(\log n)\) Stufen hat. Zum Beispiel:

Als linearer Ausdruck: \((((v₁\circ v₂)\circ (v₃\circ v₄))\circ ((v₅\circ v₆)\circ (v₇\circ v₈)))\)

Visualisierte Baumstruktur:

                ∘
             /     \

       ∘               ∘
     /   \           /    \
  ∘        ∘       ∘       ∘
 /  \     /  \    /  \    /  \
.    .   .    .  .    .  .    .
v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈

Jeder Knoten mit . stellt den entsprechenden Wert vᵢ dar. Ein Knoten mit stellt den Wert dar, den man erhält, wenn man auf den Wert der beiden Nachfolgerknoten (Kinder) darunter anwendet.

Hier sind zwei Beispiele, eines mit \(a\circ b = a+b\) und eines mit \(a\circ b = \max(a,b)\). (Achtung: Beide diese Beispiele erfüllen auch \(a\circ b=b\circ a\) (d.h. \(\circ \) ist kommutativ), aber das ist im Allgemeinen nicht notwendig.)

∘=+:
                41
             /     \

       17              24
     /   \           /    \
  9        8       10      14
 /  \     /  \    /  \    /  \
5    4   2   6   9    1  4   10
v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈
∘=max:
               10
             /     \

       6               10
     /   \           /    \
  5        6       9       10
 /  \     /  \    /  \    /  \
5    4   2   6   9    1  4   10
v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈

Wenn nun eine set-Operation angewendet wird, lässt sich die gesamte Struktur effizient aktualisieren, wir können beispielsweise v₆ auf 11 setzen:

∘=+:
                ?
             /     \

       17              ?
     /   \           /    \
  9        8       ?       14
 /  \     /  \    /  \    /  \
5    4   2   6   9   11  4   10
v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈
∘=max:
                ?
             /     \

       6               ?
     /   \           /    \
  5        6       ?       10
 /  \     /  \    /  \    /  \
5    4   2   6   9   11  4   10
v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈

Die Knoten mit ? stellen nun die Knoten dar, von denen wir zunächst nicht mehr wissen welche Werte sie darstellen. Merke, dass das nur sehr wenige Knoten im Baum sind: Es sind genau die Knoten, die man passiert, wenn man vom veränderten Knoten v₆ zum obersten Knoten läuft. Auf jeder Stufe gibt es also nur einen Knoten dessen dargestellter Wert sich ändert. Wir können diese Knoten von unten nach oben durchlaufen, und ihre Werte durch anwenden der Operation neu berechnen:

∘=+:                                      ∘=+:                                      ∘=+:                                      ∘=+:
                ?                                         ?                                         ?                                         51
             /     \                                   /     \                                   /     \                                   /     \

       17              ?                         17              ?                         17              34                        17              34
     /   \           /    \                    /   \           /    \                    /   \           /    \                    /   \           /    \
  9        8       ?       14       ->      9        8       20      14       ->      9        8       20      14       ->      9        8       20      14
 /  \     /  \    /  \    /  \             /  \     /  \    /  \    /  \             /  \     /  \    /  \    /  \             /  \     /  \    /  \    /  \
5    4   2   6   9   11  4   10           5    4   2   6   9   11  4   10           5    4   2   6   9   11  4   10           5    4   2   6   9   11  4   10
v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈           v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈           v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈           v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈
∘=max:                                    ∘=max:                                    ∘=max:                                    ∘=max:
                ?                                         ?                                         ?                                         17
             /     \                                   /     \                                   /     \                                   /     \

       6               ?                         6               ?                         6               11                        6               11
     /   \           /    \                    /   \           /    \                    /   \           /    \                    /   \           /    \
  5        6       ?       10       ->      5        6       11      10      ->       5        6       11      10      ->       5        6       11      10
 /  \     /  \    /  \    /  \             /  \     /  \    /  \    /  \             /  \     /  \    /  \    /  \             /  \     /  \    /  \    /  \
5    4   2   6   9   11  4   10           5    4   2   6   9   11  4   10           5    4   2   6   9   11  4   10           5    4   2   6   9   11  4   10
v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈           v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈           v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈           v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈

Da wir insgesamt nur \(O(\log n)\) Operationen durchgeführt haben, ist das eine gute Art, set zu implementieren.

get(1, n) ist auch einfach zu berechnen, weil dieser Wert ja gerade am obersten Knoten (der Wurzel) steht. Das ist im Fall von ∘=max, oder ∘=gcd bereits nützlich: Wir können beliebige Werte aktualisieren und wissen immer, was ihr Maximum, oder ihr grösster gemeinsamer Teiler ist. (Für ∘=+ ist das weit weniger beeindruckend – wieso?)

Es bleibt also noch zu diskutieren, wie man get(l, r) für beliebige (l, r) mit \(l\leq r\) bestimmen kann. Wir machen zunächst ein Beispiel: get(2, 6).

∘=+:
                51
             /     \

       17              34
     /   \           /    \
  9       |8|     |20|     14
 /  \     /  \    /  \    /  \
5   |4|  2   6   9   11  4   10
v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈
     ──────────────────
∘=max:
                17
             /     \

       6               11
     /   \           /    \
  5        |6|    |11|     10
 /  \     /  \    /  \    /  \
5   |4|  2   6   9   11  4   10
v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈
     ──────────────────

Das Resultat ist jeweils einfach die Kombination der markierten Knoten. Oben ist get(2, 6) = 4+8+20 = 32 und unten haben wir get(2, 6) = max(4, 6, 11) = 11.

Die markierten Knoten bilden die sogenannte “kanonische Überdeckung” des Segmentes \([2,6]\). Die kanonische Überdeckung eines Segmentes ist wie folgt bestimmt:

Wir starten mit den Knoten des Segmentes auf der untersten Stufe, und ersetzen dann immer wieder zwei Knoten, die zum selben Elternteil gehören mit diesem Elternteil, solange das noch möglich ist:

                ∘                                      ∘                                      ∘
             /     \                                /     \                                /     \
                            Fasse zusammen:                        Fasse zusammen:
       ∘               ∘         ->           ∘               ∘         ->           ∘               ∘
     /   \           /    \     v₃,v₄       /   \           /    \     v₃,v₄       /   \           /    \
  ∘        ∘       ∘       ∘             ∘       |∘|      ∘       ∘             ∘       |∘|     |∘|      ∘
 /  \     /  \    /  \    /  \          /  \     /  \    /  \    /  \          /  \     /  \    /  \    /  \
.   |.| |.|  |.||.|  |.| .    .        .   |.|  .    . |.|  |.| .    .        .   |.|  .    .  .    .  .    .
v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈        v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈        v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈

Nach dem zweiten Schritt gibt es hier bereits keine zwei Knoten mehr, welche zusammengefasst werden könnten.

Wir machen ein weiteres Beispiel und bestimmen die kanonische Überdeckung von \([1,7]\) in insgesamt vier Schritten:

                 ∘                                     ∘                                      ∘
              /     \                               /     \                                /     \
                            Fasse zusammen:                        Fasse zusammen:
        ∘               ∘         ->           ∘               ∘        ->          |∘|              ∘
      /   \           /    \    v₁,v₂       /   \           /    \     ∘,∘         /   \           /    \
   ∘        ∘       ∘       ∘   v₃,v₄   |∘|      |∘|     |∘|      ∘             ∘        ∘      |∘|      ∘
  /  \     /  \    /  \    /  \ v₅,v₆   /  \     /  \    /  \    /  \          /  \     /  \    /  \    /  \
|.|  |.| |.|  |.||.|  |.||.|   .       .    .  .    .   .    .  .    .        .    .   .    .  .    . |.|   .
 v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈       v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈        v₁   v₂  v₃  v₄  v₅  v₆  v₇  v₈

Unsere Strategie, um einen Wert \(vₗ\circ vₗ₊₁\circ \ldots \circ vᵣ₋₁\circ vᵣ\) zu bestimmen wird sein, die kanonische Überdeckung von \([l,r]\) zu bestimmen und die Werte der Knoten darin mit \(\circ \) zusammenzufassen. Das ist korrekt, da die kanonische Überdeckung natürlich genau Segmente enthält, die zusammengenommen den ganzen Bereich darstellen.

Das einzige Problem ist, dass unsere bisherige Art, die kanonische Überdeckung zu bestimmen natürlich viel zu langsam ist, um diese Methode effizient zu machen. Damit die Methode in \(O(\log n)\) läuft, müssen wir uns überzeugen, dass die kanonische Überdeckung nur \(O(\log n)\) viele Knoten enthält, und dass wir diese Knoten in \(O(\log n)\) Zeit bestimmen können.

Wieso hat die kanonische Überdeckung nur \(O(\log n)\) Knoten? Für ein beliebiges Segment \([l,r]\) gibt es auf jeder Stufe im Baum höchstens zwei Knoten, die zur kanonischen Überdeckung gehören. Davon kann man sich leicht überzeugen: - Da die Reihenfolge, in der wir Knoten zusammenfassen für das Endresultat keine Rolle spielt (wieso?), können wir Stufenweise von unten nach oben zusammenfassen. Das haben wir bei beiden Beispielen oben bereits so gemacht. - Dann sind die Zwischenresultate auf jeder Stufe ein nebeineinanderliegendes Segment von Knoten. (Das ist am Anfang so, und wird auch nach jeder abgearbeiteten Stufe beibehalten, siehe auch die Skizzen unten.) - Jede Stufe lässt sich in nebeneinanderliegende Zweierpaare zerlegen, wobei die zwei Knoten eines Paares jeweils dasselbe Elternteil haben.

Schematisch sieht die ganze Anordnung also so aus:

|. .||. .||. .| ... |. .||. .|
   ───────────────────

oder so:

|. .||. .||. .| ... |. .||. .|
   ─────────────────────

oder so:

|. .||. .||. .| ... |. .||. .|
      ────────────────

oder so:

|. .||. .||. .| ... |. .||. .|
      ──────────────────

Alle Paare, die durch das Segment komplett abgedeckt werden, können also zusammengefasst werden und kommen damit auf die nächste Stufe. Es gibt höchstens zwei Paare, die nur zur Hälfte durch das Segment abgedeckt werden, und jedes solche Paar hinterlässt auf der aktuellen Stufe einen Knoten, der zur kanonischen Überdeckung gehört.

Da die einzige Information, die nötig ist, um die Anordnung auf jeder Stufe darzustellen und die Knoten der kanonischen Überdeckung zu bestimmen die linke und die rechte Grenze des aktuellen Segmentes ist, liefert dies auch bereits einen effizienten Algorithmus, um die kanonische Überdeckung zu bestimmen.

Darstellung

Eine mögliche Variante, den Segmentbaum im Speicher darzustellen ist für jede Stufe eine Liste der Knoten auf dieser Stufe zu behalten. (Es gibt aber viele andere gute Möglichkeiten.) Der Segmentbaum in unserer Implementierung speichert Werte vom Typ T. (T kann zum Beispiel int sein.)

// wir stellen den Segmentbaum dar als std::vector der Stufen,
// wobei segtree[0] die unterste Stufe ist.
vector<vector<T>> segtree;
segtree.push_back(vector<int>(n)); // erstelle unterste Stufe
for(int i=1;segtree[i-1].size()>1;i++){
    int size = segtree[i-1].size()/2;
    segtree.push_back(vector<int>(size)); // erstelle restliche Stufen
}

set-Operation

Wir nehmen an, dass eine funktion T f(T, T) existiert, die implementiert: \(a\circ b =\) f(a, b).

// führe auf Segmentbaum segtree die Zuweisung vᵢ← v aus
void set(vector<vector<T>> &segtree, int i, int v){
    segtree[0][i] = v; // setze Wert auf unterster Stufe
    int k = i>>1; // k ist Index des aktuell betrachteten Elternteils
    for(int l = 1; l < (int)segtree.size(); l++){ // aktualisiere Werte auf oberen Stufen
        if(k >= segtree[l].size()) break; // Elternteil existiert nicht, fertig
        segtree[l][k] = f(segtree[l-1][2*k], segtree[l-1][2*k+1]); // berechne Wert neu aus Werten der Kinder
        k >>= 1; // setze k auf Elternteil von k
    }
}

Merke, dass das & in der Funktionssignatur wichtig ist: Es bedeutet, dass der Segmentbaum per Referenz übergeben wird (das heisst, keine Kopie wird erstellt).

get-Operation

Wir bestimmen die kanonische Überdeckung mit dem stufenweisen Algorithmus, und fassen die Werte der Knoten, die vom linken bzw. rechten Ende des Segmentes generiert werden separat zusammen. Sobald das betrachtete Segment leer ist, kombinieren wir die beiden erhaltenen Werte. Um den Code möglichst einfach zu gestalten, nehmen wir an, dass es einen Wert e gibt, sodass f(a, e) == a und f(e, b) == b, also einen Wert, den man einer leeren Liste von Werten zuordnen könnte. (Das kann man immer sicherstellen, indem man T und die Operation leicht anpasst, ist also keine Einschränkung. Wenn ∘ = +, dann ist e = 0, und wenn ∘ = max, dann ist e = -∞.)

// für l≤r, berechne vₗ∘vₗ₊₁∘ …∘ vᵣ₋₁∘vᵣ auf Segmentbaum segtree
T get(vector<vector<T>> &segtree, int l, int r){
    int a = l, b = r; // Indizes der linken und rechten Grenzen des Segmentes
    T v_l = e, v_r = e; // zusammengefasste Werte links und rechts
    for(int i = 0; a <= b; i++){
        if(a%2 == 1){ // Paar an linker Grenze nicht ganz überdeckt
            v_l = f(v_l, segtree[i][a]); // füge a zu kanonischer Überdeckung hinzu
            a++; // zu betrachtendes Segment wird kleiner
        }
        if(b%2 == 0){ // Paar an rechter Grenze nicht ganz überdeckt
            v_r = f(segtree[i][b], v_r); // füge b zu kanonischer Überdeckung hinzu
            b--; // zu betrachtendes Segment wird kleiner
        }
        a >>= 1, b >>= 1; // gehe eine Stufe nach oben
    }
    return f(v_l, v_r); // füge Werte von links und rechts zusammen
}

Falls f(a, b) == f(b, a), kann man die beiden separaten Variablen v_l und v_r zu einer einzelnen Variable zusammenfassen. Die Implementierung oben funktioniert auch, wenn n keine Zweierpotenz ist (wieso?).