Abfragen im Segmentbaum

Question

Ich habe gekämpft, um die Logik der letzten 6 Zeilen in query() Funktion zu verstehen.

Dies ist der Code für das Problem GSS1 on spoj.

Lösung link

#include <cstdio> 
#include <algorithm> 
#define MAX 70000 

using namespace std; 

struct no { 
int lsum, rsum, msum; 
}; 

int array[ MAX + 1 ], sums[ MAX + 1 ]; 
no tree[ 4 * MAX + 1 ]; 

void init(int node, int i, int j) { 
if (i == j) { 
    tree[ node ] = ((no) { array[ i ], array[ i ], array[ i ] }); 
} 
else { 
    init(node * 2, i, (i + j)/2); 
    init(node * 2 + 1, (i + j)/2 + 1, j); 
    no left = tree[ node * 2 ], right = tree[ node * 2 + 1 ]; 
    tree[ node ].lsum = max(left.lsum, sums[ (i + j)/2 ] - sums[ i - 1 ] + right.lsum); 
    tree[ node ].rsum = max(right.rsum, sums[ j ] - sums[ (i + j)/2 ] + left.rsum); 
    tree[ node ].msum = max(left.msum, max(right.msum, left.rsum + right.lsum)); 
}} 

no query(int node, int a, int b, int i, int j) { 
if (a == i && b == j) { 
    return tree[ node ]; 
} 
else if (j <= (a + b)/2) { 
    return query(node * 2, a, (a + b)/2, i, j); 
} 
if (i > (a + b)/2) { 
    return query(node * 2 + 1, (a + b)/2 + 1, b, i, j); 
} 
no left = query(node * 2, a, (a + b)/2, i, (a + b)/2); 
no right = query(node * 2 + 1, (a + b)/2 + 1, b, (a + b)/2 + 1, j); 
return ((no) { 
      max(left.lsum, sums[ (a + b)/2 ] - sums[ i - 1 ] + right.lsum), 
      max(right.rsum, sums[ b ] - sums[ (a + b)/2 ] + left.rsum), 
      max(left.msum, max(right.msum, left.rsum + right.lsum)) 
      }); } 

int main() { 
int i, N, q, l, r; 
scanf("%d", &N); 
for (i = 0; i < N; ++i) { 
    scanf("%d", array + i); 
    if (i == 0) { 
     sums[ i ] = array[ i ]; 
    } 
    else { 
     sums[ i ] = sums[ i - 1 ] + array[ i ]; 
    } 
} 
init(1, 0, N - 1); 
scanf("%d", &q); 
for (i = 0; i < q; ++i) { 
    scanf("%d%d", &l, &r); 
    --l; 
    --r; 
    printf("%d\n", query(1, 0, N - 1, l, r).msum); 
} 
return 0; } 

Was die Notwendigkeit, dass es keine = & & no = rechts und dass die Rückkehr in Abfrage-Funktion verlassen.

Soll jemand vorschlagen bessere Implementierung/Tutorial fr Segmentbaum.

Ich kann diese Rekursionen während der Implementierung von Datenstrukturen nicht visualisieren. Irgendwelche Trinkgeld?

Answer 1

Was die Notwendigkeit, dass keine = ist links & & no = rechts und dass die Rückkehr in Abfragefunktion

das der Fall ist, wo das Segment, das Sie abfragen in beiden Kinder geht.

Angenommen, Sie haben einen Knoten, der das Intervall 1..n abdeckt und 2 Kinder 1 .. n/2 und n/2 + 1 ..n hat. Wenn Sie ein Intervall [a, b] so abfragen wollen, dass Sie eine < = n/2 < b benötigen, dann müssen Sie die Ergebnisse aus dem linken Zweig und dem rechten Zweig abrufen und kombinieren (dh die Abfrage in [a , n/2] und [n/2 +1, b] erhalten die 2 Ergebnisse und kombinieren sie

Für die Effizienz können Sie beweisen, dass es nur eine Aufteilung wie diese für jede Abfrage geben kann, da sich die Intervalle jetzt berühren der Rand (also während Sie immer einen der Kinder durchlaufen, wird der andere entweder ignoriert oder fällt vollständig in die Abfrage und Sie kehren zum nächsten Rekursionsschritt zurück)

Dieser Code ist für eine sehr effiziente Implementierung (Sie don 't Zeiger auf die Kinder zu speichern, sind die Knoten Bereiche implizit. Wenn Sie versuchen zu lernen/Debug aussehen für etwas, das Dinge expliziter speichert oder selbst schreibt. Zumindest einrücken Sie den Code richtig, ändern Sie die Variablennamen in etwas besser lesbares und ersetzen Sie (a+b)/2 durch middle. Das sollte den Code leichter verständlich machen. Zeichnen Sie auch die Struktur auf Papier (immer hilft).