Answer these queries

23.02.2010 - Tomasz Górzny
TrudnośćTrudnośćTrudnośćTrudność

GSS3

Dla porządku i czytelności:

  • $  A[1] \ldots A[N]  $ - ciąg wejściowy
  • $  val(A[i] \ldots A[j]) = A[i] + \ldots + A[j]  $

Wstępne rozważania

Zadanie polega na odpowiedzi na takie same zapytania, jak w poprzednim, z jedną drobną różnicą: mogą pojawiać się żądania modyfikacji wejściowego ciągu. Tylko.. czy aby na pewno jest to drobna różnica? Zacznijmy od skopiowania struktury z pierwszego zadania i zastanówmy się, jak poradzić sobie ze zmianami.

Podejście naiwne

Zmiana wartości jednego elementu powoduje konieczność zmiany wielu sum prefiksowych w naszej strukturze. A dokładniej, jeżeli wartość A[i] zmieni się o x, to do $ S[i] \ldots S[N] $ należy dodać wartość x. Spójrzmy jak wygląda to w przełożeniu na węzły drzewa (cały czas zakładając, że jesteśmy naiwni):
  1. jeżeli i jest w prawym poddrzewie, należy je przeliczyć i uaktualnić informacje
  2. jeżeli i jest w lewym, należy przeliczyć oba poddrzewa
  3. jeżeli i jest na lewo od przedziału, liczymy oba

Leniwość obliczeń

Zauważmy, że w przypadku c) potrafimy dokładnie powiedzieć, jakie będą te wartości po przeliczeniu - minimum i maksimum zmienią się o x, a maksymalny wynik się nie zmieni. Nie ma zatem potrzeby odwiedzania poddrzew. Zachowajmy się zatem leniwie i tego nie róbmy! Czy mimo tego będziemy potrafili odtworzyć wartości, które powinny być w nich zapisane? Tak! Bardziej bym się jednak skłaniał do tego, aby dodać nową wartość do węzła, w której zapiszemy o ile powinniśmy zmodyfikować poddrzewa. Oczywiście później w trakcie ich odwiedzania dokonujemy tych odpowiednich modyfikacji.

Nazwijmy tę nową wartość add. Zobaczmy jak teraz będzie wyglądało drzewo z poprzedniego przykładu:

Każdy węzeł ma wartość add ustawioną na 0 - w końcu nie wykonaliśmy jeszcze żadnej modyfikacji. Zobaczmy więc co się stanie po zwiększeniu o 1 wartości na przedziale [1,5]. (edukacyjnie, bo w naszym algorytmie zwiększanie zawsze będzie od pewnego miejsca do końca; zauważmy, że jest to jednoczesne zwiększenie 1. liczby o 1 i zmniejszenie 6. też o 1).
Na czerwono zaznaczone są zmodyfikowane wierzchołki. Na niebiesko te, w których informacja jest nieaktualna. Liczby w kółkach odpowiadają wyliczonemu ciągowi i nie są nigdzie w drzewie pamiętane.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.5
Twoja ocena: Brak Ocena: 4.5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com