Range-Minima-problem

• sei B = (b₁, b₂, ..., b_n) eine beliebige Folge natürlicher Zahlen
• sei zu B gegeben:
  • Indiziess i<j
  • Knoten vÎB
  • seien B_v = (b_r, ..., b_i, ..., b_j, ..., b_s) die Nachfolgeknoten von v
  • Nachfolgeknoten von v = alle Knoten die an v hängen
  • 
    
    B_v = <B_u, B_w> = <(b_r, ..., b_i, ..., b_p)(b_p+1, ..., b_j, ..., b_s)>
• Algorithmus RANGE-MINIMA
  • INPUT: Array B der Länge n=2^l
  • OUTPUT:
    • vollständiger Binärbaum mit Blättern von B

    • Hilfsvariablen P(h,j), S(h,j): 0 ≤ h ≤ log n; 1 ≤ j ≤	n
      	2h

  • begin
  • for 1 ≤ j ≤ n pardo
    • P(0,j) = B(j)
    • S(0,j) = B(j)
    • // Eintragen der Werte aus dem Array B (Input)
  • for h=1 to log n
    • // n ist 2er-Potenz

    • for 1 ≤ j ≤	n	pardo
      	2h

      • Merge P(h-1,2j-1) mit P(h-1,2j) zu P(h,j)
      • Merge S(h-1,2j-1) mit S(h-1,2j) zu S(h,j)
      • // Zum Mergen:
        • Erzeugen von P(h,j):
          • es sei x das letzte Element von P(h-1,2j-1)
          • ersetze in P(h-1,2j) alle Stellen i durch min(P(h-1,2j), x)
          • füge P(h-1,2j-1) und das erhaltene P(h-1,2j) zu P(h,j) zusammen
        • Erzeugen von S(h,j):
          • es sei x das letzte Element von S(h-1,2j)
          • ersetze in S(h-1,2j-1) alle Stellen i durch min(S(h-1, 2j-1), x)
          • füge S(h-1,2j) und das erhaltene S(h-1,2j-1) zu S(h,j-1) zusammen
  • end
  • Lemma:
    • Þ der Algorithmus RANGE MINIMA verarbeitet B in O(log n) Time mit O(n log n) Work
      • auf CREW
      • auch auf EREW möglich
    • Þ Ergebnis: jede Range-Minima-Anfrage kann dann in O(1) Zeit sequentiell beantwortet werden
    • Beweis: (i,j) suche in dem vom Preprocessing erzeugten Binärbaum den LCA(i,j)
    • 
      
      wie im Beispiel: i=2, j=5
    • Betrachte Söhne des LCA:

      • Range-Minimum = Minimum aus

        Suffixminimum des linken Sohnes des LCA Präfixminimum des rechten Sohnes des LCA

      • Also im Beispiel:
        • LCA = (3,1)
        • linker Sohn von (3,1) ist (2,1)
        • S(2,1)[2] = 4, 3, 3, 3
        • rechter Sohn von (3,1) ist (2,2)
        • P(2,2)[1] = 7,1,1,1
        • ÞRange-Minimum = 3
    • Größe der Einzelarrays (in den Knoten) = 2^h (1 ≤ h ≤ log n)
• 
  
  Min B_v[b_i,..., b_j] = min( min([b_i,...,b_p]) , min(b_p+1,...,b_j) )
• Ansatz für optimale Laufzeit

  • accelerated cascading: Teilen von B in	n	Anschnitte der Länge log n
    	log n

  • darauf Anwenden: seriellen Linearzeitalgorithmus
  • 
    
    Þ damit ergibt sich die Laufzeit O(log n) mit O(n) Work