Tablice różnicowe do aktualizacji zakresów

Sumy prefiksowe szybko odpowiadały na zapytania dotyczące zakresów. Tablica różnicowa odwraca ten pomysł i pozwala szybko wykonywać wiele aktualizacji zakresów. 🔁

Dodawanie wartości do każdego elementu zakresu, powtarzane wiele razy, kosztuje O(n) na aktualizację. Przy q aktualizacjach ten koszt gwałtownie rośnie.

Zamiast modyfikować każdą komórkę należy zapisać tylko miejsce, w którym zmiana się zaczyna, oraz miejsce, w którym się kończy. Należy oznaczyć krawędzie, a nie środek.

Tablica różnicowa przechowuje różnicę między każdym elementem a elementem poprzednim. Zmiana jednej różnicy przesuwa później całą serię wartości.

Aby dodać v do elementów od l do r, należy dodać v pod indeksem l i odjąć v pod indeksem r + 1. Tylko dwie modyfikacje obejmują cały zakres.

Dodanie wartości pod indeksem l włącza zmianę, a odjęcie jej pod indeksem r + 1 ją wyłącza. Razem ograniczają aktualizację do jednego zakresu.

Każda aktualizacja wymaga tylko dwóch zapisów do tablicy, więc q aktualizacji zajmuje łącznie O(q). Najbardziej pracochłonna część jest odroczona do końca.

Po umieszczeniu wszystkich oznaczeń należy obliczyć sumę prefiksową tablicy różnicowej. Jedno przejście odtwarza każdą wartość końcową.

Tablica powinna mieć o jedną komórkę więcej, aby r + 1 nigdy nie wychodziło poza jej koniec. Ta dodatkowa komórka ochronna zapobiega błędom indeksowania.

Na oznaczenie aktualizacji potrzeba O(q), a na jedno przejście odtwarzające tablicę O(n). Łączny koszt jest znacznie mniejszy niż naiwny O(n razy q).

Tablice różnicowe świetnie sprawdzają się przy zliczaniu rezerwacji, opłatach drogowych i każdym problemie z wieloma operacjami dodawania do zakresu oraz jednym końcowym odczytem.

Można grupować aktualizacje zakresów za pomocą tablicy różnicowej: oznaczyć l oraz r + 1, a następnie raz obliczyć sumy prefiksowe, aby odtworzyć tablicę. Szybkie aktualizacje, pojedynczy odczyt. ✅