Drzewo Segmentowe: Zapytania Zakresowe w O(log n)

Cena prostego tablicy - brak możliwości wyboru zakresu

Rozważmy, jak operacje na podzbójch tablicy wpływają na wydajność. Odpowiadanie na pytanie o sumę (lub minimum) elementów z i do wymaga obliczeń, które w prostym tablicie są O(1), ale zmiana wartości elementu powoduje, że wszystkie kolejne sumy stają się nieprawidłowe, co kosztuje O(n). Z drugiej strony, brak prewencji sprawia, że zapytanie o sumę elementów z i do wymaga O(n) czasu. Drzewo segmentowe oferuje rozwiązanie: zarówno operacje zapytania, jak i aktualizacji kosztują O(log n), ponieważ przechowuje agregaty dla wszystkich zakresów, które można uzyskać dzięki rekurencyjnemu podziałowi na poddrzewa.

To sprawia, że drzewo segmentowe jest idealnym rozwiązaniem do operacji na podzbójch tablicach, gdzie zarówno zapytania, jak i aktualizacje są wykonywane w czasie O(log n).

Budowanie drzewa

Korzeń obejmuje cały tablicę [0, n). Każedy węzeł wewnętrzny dzieli swój zakres na pół i przekazuje połowy do swoich dwóch potomków; liść pokrywa pojedynczy element. Ponieważ drzewo zawsze dzieli się równomiernie, ma wysokość ⌈log₂ n⌉ i około 2n − 1 węzłów, zwykle przechowywanych w tablicy o rozmiarze 4n dla prostego schematu indeksowania bez wskaźników:

funkcja build(node, lo, hi) { if (lo === hi) { tree[node] = a[lo]; return; } const mid = (lo + hi) >> 1; build(2*node, lo, mid); build(2*node+1, mid+1, hi); tree[node] = combine(tree[2*node], tree[2*node+1]); // suma, minimum, gcd... } Budowanie odwiedza każdy węzeł raz, więc konstrukcja jest O(n), nawet jeśli drzewo wygląda na kosztowne rekurencyjnie na papierze.

function build(node, lo, hi) {
  if (lo === hi) { tree[node] = a[lo]; return; }
  const mid = (lo + hi) >> 1;
  build(2*node, lo, mid);
  build(2*node+1, mid+1, hi);
  tree[node] = combine(tree[2*node], tree[2*node+1]);  // sum, min, gcd...
}

Odpowiadanie na zapytanie o zakres

Każdy zapytany zakres [l, r] można dokładnie pokryć przez mały zbiór zakresów węzłów już przechowywanych w drzewie – jego kanoniczną dekompozycję. Rekursja zapytania zatrzymuje się natychmiast, gdy zakres węzła całkowicie mieści się lub całkowicie wyklucza [l, r], a dalsze zejście odbywa się tylko wtedy, gdy zakresy częściowo nakładają się:

funkcja query(node, lo, hi, l, r) { if (r < lo || hi < l) return IDENTITY; // brak nakładania się if (l <= lo && hi <= r) return tree[node]; // całkowicie pokryte const mid = (lo + hi) >> 1; return combine(query(2*node, lo, mid, l, r), query(2*node+1, mid+1, hi, l, r)); } Na każdym poziomie drzewa, maksymalnie dwa węzły mogą częściowo nakładać się z zapytaniem – jeden zawierający lewe graniczne, a drugi zawierający prawą – dlatego całe zapytanie dotyka tylko O(log n) węzłów, niezależnie od tego, jak szeroki jest zakres.

function query(node, lo, hi, l, r) {
  if (r < lo || hi < l) return IDENTITY;       // no overlap
  if (l <= lo && hi <= r) return tree[node];    // fully covered
  const mid = (lo + hi) >> 1;
  return combine(query(2*node, lo, mid, l, r),
                 query(2*node+1, mid+1, hi, l, r));
}

Aktualizacja punktowa i propagacja opóźniona dla aktualizacji zakresu

Aktualizowanie pojedynczego elementu prowadzi po tym samym ścieżku od korzenia do liścia, w którym zbudowano drzewo, modyfikuje liść, a następnie rekombinuje wszystkie przodki podczas wraca z powrotem – koszt O(log n) dotkniętych węzłów, idealnie dopasowujący się do kosztu zapytania. Aktualizacja całego zakresu naraz (dodaj 5 do każdego elementu od i do j) jest wtedy, gdy naiwna aktualizacja punkt po punkcie staje się O(n log n), a potrzebna jest sprytniejsza sztuczka: propagacja opóźniona. Węzeł, którego zakres jest w pełni pokryty aktualizacją, przechowuje oczekujący znacznik zamiast natychmiast aktualizowania wszystkich potomków; znacznik jest przesyłany tylko do dzieci następnym razem, gdy zapotrzebowanie na zewnątrz lub rekursja aktualizacji faktycznie potrzebuje zaobserwować ten węzeł.

funkcja pushDown(node, lo, hi) { if (!lazy[node]) return; const mid = (lo + hi) >> 1; applyTag(2*node, lo, mid, lazy[node]); applyTag(2*node+1, mid+1, hi, lazy[node]); lazy[node] = 0; } Dzięki znacznikom opóźnionym zarówno aktualizacje zakresu, jak i zapytania zakresu pozostają O(log n), co czyni segmentowe drzewa standardowym narzędziem dla problemów łączących "dodaj x do wszystkiego w [l, r]" z "jaki jest suma/minimum w [l, r]" w tej samej obciążeniu.

function pushDown(node, lo, hi) {
  if (!lazy[node]) return;
  const mid = (lo + hi) >> 1;
  applyTag(2*node, lo, mid, lazy[node]);
  applyTag(2*node+1, mid+1, hi, lazy[node]);
  lazy[node] = 0;
}

Drzewo segmentowe, drzewo Fenwicka lub tabela rozszczepiona?

Drzewo Fenwicka (binary indexed tree) wykonuje to samo zapytanie o sumę prefiksów O(log n) i aktualizację punktową z znacznie mniejszym kodem i mniejszym współczynnikiem stałym, ale działa czysto tylko dla operacji odwracalnych, takich jak suma, gdzie można odejmować, aby uzyskać dowolny zakres z dwóch prefiksów — nie obsługuje ona bezpośrednio min lub max. Tabela rozszczepiona odpowiada na zapytania o zakres minimalny lub zakres GCD w czasie O(1) po zbudowaniu w czasie O(n log n) przez obliczanie potęg długości opartej na potędze dwójki, ale jest statyczna: wykorzystuje to idempotencję (przecinanie tego samego elementu dwa razy nie łamie min lub GCD) i nie ma żadnego wydajnego sposobu na obsługę aktualizacji w ogóle. Drzewo segmentowe jest generalistą: dowolna funkcja łącząca, z aktualizacjami, w czasie O(log n) po obu stronach — cena za tę ogólność to dodatkowa struktura drzewa, którą inne dwa pomijają.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Segment Tree i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.