Data Structureshard

What is a segment tree and what complexity does it give for range queries and updates?

Answer

A segment tree is a binary tree over array segments. It supports range queries (sum/min/max) and point updates in O(log n) after an O(n) build. With lazy propagation it can handle range updates too.

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];
  }
}

Advanced answer

Deep dive

Expanding on the short answer — what usually matters in practice:

Context (tags): segment-tree, range-query, updates, big-o
Complexity: compare typical operations (average vs worst-case).
Invariants: what must always hold for correctness.
When the choice is wrong: production symptoms (latency, GC, cache misses).
Explain the "why", not just the "what" (intuition + consequences).
Trade-offs: what you gain/lose (time, memory, complexity, risk).
Edge cases: empty inputs, large inputs, invalid inputs, concurrency.

Examples

Here’s an additional example (building on the short answer):

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];
  }
}

Common pitfalls

Too generic: no concrete trade-offs or examples.
Mixing average-case and worst-case (e.g., complexity).
Ignoring constraints: memory, concurrency, network/disk costs.