Segment Tree

Træ

En træstruktur til effektive range queries og updates på arrays, som sum, minimum, maximum på intervaller.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(1) for single element`
Search	`O(log n) for range query`
Insertion	`O(log n) for update`
Deletion	`O(log n) for update`

Beskrivelse

Segment Tree er en kraftfuld datastruktur designet til at løse range query problems effektivt. Givet et array kan vi hurtigt besvare queries som 'hvad er summen af elementer fra index i til j?' eller 'hvad er minimum værdi i dette interval?'. Uden Segment Tree ville sådanne queries tage O(n) tid, men med Segment Tree tager både queries og updates kun O(log n). Strukturen er et binært træ hvor hvert leaf node repræsenterer et enkelt array element, og hvert internal node repræsenterer merger af sine børns intervals. For eksempel, i en sum segment tree ville hver node gemme summen af elementerne i dens interval. Tree bygges bottom-up eller top-down rekursivt. Segment Trees er utroligt alsidige - samme struktur kan bruges til sum, min, max, GCD, eller enhver associativ operation. De findes i to varianter: array-based (kompakt men kræver 4n space) og pointer-based (mere fleksibel). Lazy propagation er en vigtig optimization der gør range updates effektive.

Kode Eksempel

// JavaScript Segment Tree Implementation (Range 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);
  }

  // Build segment tree
  build(arr, node, start, end) {
    if (start === end) {
      // Leaf node
      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);

    // Internal node = sum of children
    this.tree[node] = this.tree[leftChild] + this.tree[rightChild];
  }

  // Query sum in range [L, R]
  query(L, R) {
    return this.queryHelper(0, 0, this.n - 1, L, R);
  }

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

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

    // Partial 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;
  }

  // Update element at index idx to value
  update(idx, value) {
    this.updateHelper(0, 0, this.n - 1, idx, value);
  }

  updateHelper(node, start, end, idx, value) {
    if (start === end) {
      // Leaf node
      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);
    }

    // Update parent
    this.tree[node] = this.tree[leftChild] + this.tree[rightChild];
  }

  // Range update: add delta to all elements in [L, R]
  rangeUpdate(L, R, delta) {
    for (let i = L; i <= R; i++) {
      const current = this.query(i, i);
      this.update(i, current + delta);
    }
  }
}

// Segment Tree for Range Minimum Query
class MinSegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(Infinity);
    this.build(arr, 0, 0, this.n - 1);
  }

  build(arr, node, start, end) {
    if (start === end) {
      this.tree[node] = arr[start];
      return;
    }

    const mid = Math.floor((start + end) / 2);
    this.build(arr, 2 * node + 1, start, mid);
    this.build(arr, 2 * node + 2, mid + 1, end);
    this.tree[node] = Math.min(this.tree[2 * node + 1], this.tree[2 * node + 2]);
  }

  query(node, start, end, L, R) {
    if (R < start || L > end) return Infinity;
    if (L <= start && end <= R) return this.tree[node];

    const mid = Math.floor((start + end) / 2);
    const leftMin = this.query(2 * node + 1, start, mid, L, R);
    const rightMin = this.query(2 * node + 2, mid + 1, end, L, R);
    return Math.min(leftMin, rightMin);
  }

  rangeMin(L, R) {
    return this.query(0, 0, this.n - 1, L, R);
  }
}

// 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); // Change arr[2] from 5 to 10
console.log('Sum [0, 2] after update:', segTree.query(0, 2)); // 1+3+10 = 14

const minTree = new MinSegmentTree(arr);
console.log('Min [1, 4]:', minTree.rangeMin(1, 4)); // 3

Anvendelsesområder

•Range sum/min/max queries
•Competitive programming problems
•Dynamic statistics på arrays
•Interval scheduling problems
•Geographic information systems

Fordele

✓O(log n) queries og updates
✓Understøtter enhver associativ operation
✓Effektiv til range operations
✓Kan håndtere dynamiske arrays
✓Lazy propagation muliggør range updates

Ulemper

✗O(4n) space requirement
✗Kompleks implementation
✗Ikke intuitiv at forstå
✗Overkill for simple static queries
✗Cache-unfriendly ved meget store arrays

Eksempler fra den virkelige verden

•Stock market range queries (min/max price i periode)
•Gaming leaderboards (range rank queries)
•Weather data analysis (temperature ranges)
•Network monitoring (traffic in time intervals)
•Computational geometry interval problems

Relaterede strukturer

Fenwick TreeBinary Indexed TreeBinary TreeArray