Segmenttræ

Træ

En træstruktur til effektive intervalforespørgsler og opdateringer på arrays, som sum, minimum, maksimum på intervaller.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(1) for enkelt element`
Search	`O(log n) for intervalforespørgsel`
Insertion	`O(log n) for opdatering`
Deletion	`O(log n) for opdatering`

Beskrivelse

Segmenttræet er en kraftfuld datastruktur designet til at løse intervalforespørgselsproblemer effektivt. Givet et array kan vi hurtigt besvare forespørgsler som 'hvad er summen af elementer fra indeks i til j?' eller 'hvad er minimumsværdien i dette interval?'. Uden segmenttræ ville sådanne forespørgsler tage O(n) tid, men med segmenttræ tager både forespørgsler og opdateringer kun O(log n). Strukturen er et binært træ hvor hver bladnode repræsenterer et enkelt array-element, og hver intern node repræsenterer sammenfletninger af sine børns intervaller. For eksempel, i et sum-segmenttræ ville hver node gemme summen af elementerne i dens interval. Træet bygges bottom-up eller top-down rekursivt. Segmenttræer er utroligt alsidige - samme struktur kan bruges til sum, min, max, GCD, eller enhver associativ operation. De findes i to varianter: array-baseret (kompakt men kræver 4n plads) og pointer-baseret (mere fleksibel). Doven propagering er en vigtig optimering der gør intervalopdateringer effektive.

Kode Eksempel

// JavaScript Segment Tree Implementation (interval-sum)
class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(arr, 0, 0, this.n - 1);
  }

  // Byg segmenttræ
  build(arr, node, start, end) {
    if (start === end) {
      // Bladnode
      this.tree[node] = arr[start];
      return;
    }

    const mid = Math.floor((start + end) / 2);
    const leftChild = 2 * node + 1;
    const rightChild = 2 * node + 2;

    this.build(arr, leftChild, start, mid);
    this.build(arr, rightChild, mid + 1, end);

    // Intern node = sum af børn
    this.tree[node] = this.tree[leftChild] + this.tree[rightChild];
  }

  // Forespørg sum i interval [L, R]
  query(L, R) {
    return this.queryHelper(0, 0, this.n - 1, L, R);
  }

  queryHelper(node, start, end, L, R) {
    // Ingen overlap
    if (R < start || L > end) {
      return 0;
    }

    // Komplet overlap
    if (L <= start && end <= R) {
      return this.tree[node];
    }

    // Delvis overlap
    const mid = Math.floor((start + end) / 2);
    const leftSum = this.queryHelper(2 * node + 1, start, mid, L, R);
    const rightSum = this.queryHelper(2 * node + 2, mid + 1, end, L, R);

    return leftSum + rightSum;
  }

  // Opdater element på indeks idx til værdi
  update(idx, value) {
    this.updateHelper(0, 0, this.n - 1, idx, value);
  }

  updateHelper(node, start, end, idx, value) {
    if (start === end) {
      // Bladnode
      this.tree[node] = value;
      return;
    }

    const mid = Math.floor((start + end) / 2);
    const leftChild = 2 * node + 1;
    const rightChild = 2 * node + 2;

    if (idx <= mid) {
      this.updateHelper(leftChild, start, mid, idx, value);
    } else {
      this.updateHelper(rightChild, mid + 1, end, idx, value);
    }

    // Opdater forælder
    this.tree[node] = this.tree[leftChild] + this.tree[rightChild];
  }
}

// Brug
const arr = [1, 3, 5, 7, 9, 11];
const segTree = new SegmentTree(arr);

console.log('Sum [1, 4]:', segTree.query(1, 4)); // 3+5+7+9 = 24
console.log('Sum [0, 2]:', segTree.query(0, 2)); // 1+3+5 = 9

segTree.update(2, 10); // Ændr arr[2] fra 5 til 10
console.log('Sum [0, 2] efter opdatering:', segTree.query(0, 2)); // 1+3+10 = 14

Anvendelsesområder

•Interval-sum/min/max-forespørgsler
•Konkurrenceprogrammeringsproblemer
•Dynamisk statistik på arrays
•Intervalplanlægningsproblemer
•Geografiske informationssystemer

Fordele

✓O(log n) forespørgsler og opdateringer
✓Understøtter enhver associativ operation
✓Effektiv til intervaloperationer
✓Kan håndtere dynamiske arrays
✓Doven propagering muliggør intervalopdateringer

Ulemper

✗O(4n) pladskrav
✗Kompleks implementering
✗Ikke intuitiv at forstå
✗Overkill for simple statiske forespørgsler
✗Cache-uvenlig ved meget store arrays

Eksempler fra den virkelige verden

•Aktiemarked intervalforespørgsler (min/max pris i periode)
•Spil-leaderboards (interval-rangforespørgsler)
•Vejrdataanalyse (temperaturintervaller)
•Netværksovervågning (trafik i tidsintervaller)
•Beregningsgeometri intervalproblemer

Relaterede strukturer

Fenwick TreeBinary Indexed TreeBinary TreeArray