Struktury danychhard

Co to jest segment tree i jaką złożoność daje dla zapytań i aktualizacji zakresowych?

Tagi

#segment-tree#range-query#updates#big-o

Odpowiedź

Segment tree to drzewo binarne nad przedziałami tablicy. Umożliwia zapytania zakresowe (suma/min/max) i aktualizacje punktowe w O(log n) po zbudowaniu w O(n). Z lazy propagation potrafi też obsługiwać aktualizacje zakresowe.

class SegTree {
  private tree: number[];
  private n: number;

  constructor(n: number) {
    this.n = n;
    this.tree = Array(4 * n).fill(0);
  }

  update(node: number, l: number, r: number, idx: number, val: number) {
    if (l === r) {
      this.tree[node] = val;
      return;
    }
    const mid = Math.floor((l + r) / 2);
    if (idx <= mid) this.update(node * 2, l, mid, idx, val);
    else this.update(node * 2 + 1, mid + 1, r, idx, val);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
  }
}

Odpowiedź zaawansowana

Głębiej

Rozwinięcie krótkiej odpowiedzi — co zwykle ma znaczenie w praktyce:

Kontekst (tagi): segment-tree, range-query, updates, big-o
Złożoność: porównaj typowe operacje (średnio vs najgorzej).
Inwarianty: co musi być zawsze prawdą, żeby struktura/algorytm działał poprawnie.
Kiedy wybór jest zły: objawy w produkcji (latencja, GC, cache misses).
Wytłumacz "dlaczego", nie tylko "co" (intuicja + konsekwencje).
Trade-offy: co zyskujesz i co tracisz (czas, pamięć, złożoność, ryzyko).
Edge-case’y: puste dane, duże dane, błędne dane, współbieżność.

Przykłady

Poniżej dodatkowy przykład (bazuje na tym, co już jest w odpowiedzi):

class SegTree {
  private tree: number[];
  private n: number;

  constructor(n: number) {
    this.n = n;
    this.tree = Array(4 * n).fill(0);
  }

  update(node: number, l: number, r: number, idx: number, val: number) {
    if (l === r) {
      this.tree[node] = val;
      return;
    }
    const mid = Math.floor((l + r) / 2);
    if (idx <= mid) this.update(node * 2, l, mid, idx, val);
    else this.update(node * 2 + 1, mid + 1, r, idx, val);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
  }
}

Typowe pułapki

Zbyt ogólna odpowiedź (brak konkretów, brak przykładów).
Brak rozróżnienia między "średnio" a "najgorzej" (np. złożoność).
Pomijanie ograniczeń: pamięć, współbieżność, koszty sieci/dysku.

Pytania uzupełniające na rozmowie

Kiedy zastosował(a)byś alternatywę i dlaczego?
Jakie są typowe problemy w produkcji i jak je diagnozować?
Jak byś przetestował(a) edge-case’y?

Powiązane pytania

Struktury danych

Budowanie kopca z tablicy: dlaczego może być O(n), a nie O(n log n)?

#heap#heapify#complexity

Struktury danych

Dlaczego resize tablicy haszującej może powodować skoki latencji i jak temu zapobiegać?

#hash-table#rehash#latency

Struktury danych

Co to jest sparse table i do jakich problemów się nadaje?

#sparse-table#rmq#preprocessing

Struktury danych

Co to jest segment tree i do czego służy?

#segment-tree#range-query#big-o

Struktury danych

Na czym polega własność kopca (heap property) w kopcu binarnym?

#heap#binary-heap#priority-queue

Struktury danych

Co to jest skip list i jak wypada w porównaniu do zbalansowanych drzew?

#skip-list#linked-list#probabilistic

Odpowiedź

class SegTree {
  private tree: number[];
  private n: number;

  constructor(n: number) {
    this.n = n;
    this.tree = Array(4 * n).fill(0);
  }

  update(node: number, l: number, r: number, idx: number, val: number) {
    if (l === r) {
      this.tree[node] = val;
      return;
    }
    const mid = Math.floor((l + r) / 2);
    if (idx <= mid) this.update(node * 2, l, mid, idx, val);
    else this.update(node * 2 + 1, mid + 1, r, idx, val);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
  }
}

Odpowiedź zaawansowana

Głębiej

Rozwinięcie krótkiej odpowiedzi — co zwykle ma znaczenie w praktyce:

Kontekst (tagi): segment-tree, range-query, updates, big-o
Złożoność: porównaj typowe operacje (średnio vs najgorzej).
Inwarianty: co musi być zawsze prawdą, żeby struktura/algorytm działał poprawnie.
Kiedy wybór jest zły: objawy w produkcji (latencja, GC, cache misses).
Wytłumacz "dlaczego", nie tylko "co" (intuicja + konsekwencje).
Trade-offy: co zyskujesz i co tracisz (czas, pamięć, złożoność, ryzyko).
Edge-case’y: puste dane, duże dane, błędne dane, współbieżność.

Przykłady

Poniżej dodatkowy przykład (bazuje na tym, co już jest w odpowiedzi):

class SegTree {
  private tree: number[];
  private n: number;

  constructor(n: number) {
    this.n = n;
    this.tree = Array(4 * n).fill(0);
  }

  update(node: number, l: number, r: number, idx: number, val: number) {
    if (l === r) {
      this.tree[node] = val;
      return;
    }
    const mid = Math.floor((l + r) / 2);
    if (idx <= mid) this.update(node * 2, l, mid, idx, val);
    else this.update(node * 2 + 1, mid + 1, r, idx, val);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
  }
}

Typowe pułapki

Zbyt ogólna odpowiedź (brak konkretów, brak przykładów).
Brak rozróżnienia między "średnio" a "najgorzej" (np. złożoność).
Pomijanie ograniczeń: pamięć, współbieżność, koszty sieci/dysku.

Pytania uzupełniające na rozmowie

Kiedy zastosował(a)byś alternatywę i dlaczego?
Jakie są typowe problemy w produkcji i jak je diagnozować?
Jak byś przetestował(a) edge-case’y?