Buổi 11 — Segment Tree

Navigation

← 10-Advanced-DP | → 12-Practice-FAANG-1 Giai đoạn: FAANG Mastery | Độ khó: ⭐⭐⭐⭐⭐

1. Analogy & Context

Company Hierarchy Analogy

Segment Tree = hệ thống báo cáo của một công ty lớn.

CEO (root) lưu thống kê toàn công ty (ví dụ: tổng doanh thu tất cả N nhân viên).

2 VPs mỗi người quản lý một nửa công ty.

Managers quản lý các phòng ban nhỏ hơn.

Individual employees (leaves) là từng phần tử trong mảng.

Query: Cần thống kê cho nhóm nhân viên [l, r]? → Không cần hỏi từng người (O(N)). Chỉ cần combine kết quả từ tối đa O(log N) managers.

Update: Nhân viên i thay đổi số liệu? → Cập nhật employee → manager → VP → CEO: O(log N) steps.

Tại sao cần Segment Tree?

Approach	Build	Query	Update	Use case
Brute force array	O(1)	O(N)	O(1)	Only queries
Prefix sum	O(N)	O(1)	O(N)	No updates
Segment Tree	O(N)	O(log N)	O(log N)	Queries + updates
BIT (Fenwick)	O(N log N)	O(log N)	O(log N)	Sum only, simpler

Khi nào dùng Segment Tree?

N = 10^5, Q = 10^5 queries với updates. Brute force = O(NQ) = 10^10 — TLE. Segment Tree = O((N + Q) log N) = 10^5 * 17 ≈ 1.7 * 10^6 — AC.

2. The FAANG Standard

Segment Tree ở FAANG

Google, Meta, Amazon thường không hỏi segment tree implementation từ đầu trong 45 phút.

Thường gặp ở: Google Kickstart, competitive programming rounds, senior interviews.

Kỳ vọng FAANG Senior+: biết segment tree concept, recognize khi nào cần, có thể implement nếu cho thêm thời gian.

Minimum expectation: biết Range Sum Query Mutable (#307) — đây là entry-level segment tree.

Bonus: Lazy propagation cho range update problems.

Must-Know Segment Tree Patterns:

Pattern	Problem	Complexity
Range sum + point update	#307 Range Sum Query Mutable	Build O(N), Q/U O(log N)
Range min/max + point update	Sliding window min (advanced)	Same
Range update + range query	Range update (add val to range)	O(log N) with lazy prop
Count elements in range	#315 Count Smaller After Self	O(N log N) total
Rectangle area union	#850 Rectangle Area II	O(N log N) with sweep line

3. Visual Thinking (Mermaid)

3.1 Segment Tree Structure — Array [1, 3, 5, 7, 9, 11]

graph TD
    R["[0,5]: sum=36"] --> L["[0,2]: sum=9"]
    R --> RR["[3,5]: sum=27"]
    L --> LL["[0,1]: sum=4"]
    L --> LR["[2,2]: sum=5"]
    RR --> RL["[3,4]: sum=16"]
    RR --> RRR["[5,5]: sum=11"]
    LL --> N1["[0,0]: 1"]
    LL --> N2["[1,1]: 3"]
    RL --> N4["[3,3]: 7"]
    RL --> N5["[4,4]: 9"]

3.2 Query(1, 4) — Which Nodes Are Combined

graph TD
    R["[0,5]=36 ✗ skip"] --> L["[0,2]=9 partial"]
    R --> RR["[3,5]=27 partial"]
    L --> LL["[0,1]=4 ✗ partial overlap"]
    L --> LR["[2,2]=5 ✓ fully inside"]
    RR --> RL["[3,4]=16 ✓ fully inside"]
    RR --> RRR["[5,5]=11 ✗ outside"]
    LL --> N1["[0,0]=1 ✗ outside"]
    LL --> N2["[1,1]=3 ✓ fully inside"]

    style LR fill:#90EE90
    style RL fill:#90EE90
    style N2 fill:#90EE90
    style LR color:#000
    style RL color:#000
    style N2 color:#000

Query Result = 3 + 5 + 16 = 24 (elements at indices 1,2,3,4: 3+5+7+9=24) ✓

3.3 Update(2, 6) — Which Nodes Are Recomputed

graph TD
    R["[0,5]: 36→37 ↑"] --> L["[0,2]: 9→10 ↑"]
    R --> RR["[3,5]: 27 unchanged"]
    L --> LL["[0,1]: 4 unchanged"]
    L --> LR["[2,2]: 5→6 ↑ LEAF"]

    style LR fill:#FFB347
    style L fill:#FFD700
    style R fill:#FFD700
    style LR color:#000
    style L color:#000
    style R color:#000

4. TypeScript Template

4.1 Segment Tree — Sum (Complete Implementation)

class SegmentTree {
  private tree: number[];
  private n: number;
 
  constructor(nums: number[]) {
    this.n = nums.length;
    // Allocate 4*n nodes — guaranteed enough for any input size
    // Explanation: 2 * 2^(ceil(log2(n))) ≤ 4n
    this.tree = new Array(4 * this.n).fill(0);
    if (this.n > 0) this.build(nums, 0, 0, this.n - 1);
  }
 
  // Build: O(N)
  private build(nums: number[], node: number, start: number, end: number): void {
    if (start === end) {
      // Leaf node: store the actual value
      this.tree[node] = nums[start];
      return;
    }
    const mid = (start + end) >> 1;
    const left = 2 * node + 1;
    const right = 2 * node + 2;
    this.build(nums, left, start, mid);
    this.build(nums, right, mid + 1, end);
    // Internal node: aggregate (sum) of children
    this.tree[node] = this.tree[left] + this.tree[right];
  }
 
  // Point update: change nums[index] to val — O(log N)
  update(index: number, val: number): void {
    this.updateHelper(0, 0, this.n - 1, index, val);
  }
 
  private updateHelper(node: number, start: number, end: number, index: number, val: number): void {
    if (start === end) {
      // Reached the leaf — update it
      this.tree[node] = val;
      return;
    }
    const mid = (start + end) >> 1;
    const left = 2 * node + 1;
    const right = 2 * node + 2;
    if (index <= mid) {
      this.updateHelper(left, start, mid, index, val);
    } else {
      this.updateHelper(right, mid + 1, end, index, val);
    }
    // Recompute this internal node from updated children
    this.tree[node] = this.tree[left] + this.tree[right];
  }
 
  // Range sum query [l, r]: O(log N)
  query(l: number, r: number): number {
    return this.queryHelper(0, 0, this.n - 1, l, r);
  }
 
  private queryHelper(node: number, start: number, end: number, l: number, r: number): number {
    // Case 1: Completely outside query range → return identity (0 for sum)
    if (r < start || end < l) return 0;
 
    // Case 2: Completely inside query range → return this node's value
    if (l <= start && end <= r) return this.tree[node];
 
    // Case 3: Partial overlap → recurse into children
    const mid = (start + end) >> 1;
    const left = 2 * node + 1;
    const right = 2 * node + 2;
    return (
      this.queryHelper(left, start, mid, l, r) +
      this.queryHelper(right, mid + 1, end, l, r)
    );
  }
}
 
// Usage — #307 Range Sum Query Mutable
class NumArray {
  private seg: SegmentTree;
 
  constructor(nums: number[]) {
    this.seg = new SegmentTree(nums);
  }
 
  update(index: number, val: number): void {
    this.seg.update(index, val);
  }
 
  sumRange(left: number, right: number): number {
    return this.seg.query(left, right);
  }
}
// Build: O(N) | update: O(log N) | sumRange: O(log N)

4.2 Segment Tree — Min Variant

class SegmentTreeMin {
  private tree: number[];
  private n: number;
 
  constructor(nums: number[]) {
    this.n = nums.length;
    this.tree = new Array(4 * this.n).fill(Infinity);
    if (this.n > 0) this.build(nums, 0, 0, this.n - 1);
  }
 
  private build(nums: number[], node: number, start: number, end: number): void {
    if (start === end) { this.tree[node] = nums[start]; return; }
    const mid = (start + end) >> 1;
    this.build(nums, 2*node+1, start, mid);
    this.build(nums, 2*node+2, mid+1, end);
    this.tree[node] = Math.min(this.tree[2*node+1], this.tree[2*node+2]);
  }
 
  update(index: number, val: number): void {
    this.updateHelper(0, 0, this.n - 1, index, val);
  }
 
  private updateHelper(node: number, start: number, end: number, idx: number, val: number): void {
    if (start === end) { this.tree[node] = val; return; }
    const mid = (start + end) >> 1;
    if (idx <= mid) this.updateHelper(2*node+1, start, mid, idx, val);
    else this.updateHelper(2*node+2, mid+1, end, idx, val);
    this.tree[node] = Math.min(this.tree[2*node+1], this.tree[2*node+2]);
  }
 
  // Returns minimum in range [l, r]
  queryMin(l: number, r: number): number {
    return this.queryHelper(0, 0, this.n - 1, l, r);
  }
 
  private queryHelper(node: number, start: number, end: number, l: number, r: number): number {
    if (r < start || end < l) return Infinity; // identity for min
    if (l <= start && end <= r) return this.tree[node];
    const mid = (start + end) >> 1;
    return Math.min(
      this.queryHelper(2*node+1, start, mid, l, r),
      this.queryHelper(2*node+2, mid+1, end, l, r)
    );
  }
}

4.3 Lazy Propagation — Range Update + Range Query

// Lazy Propagation: defer range updates until needed
// lazy[node] = pending add-value for all elements in this node's range
// Rule: before accessing children, PUSH DOWN the lazy value
 
class SegmentTreeLazy {
  private tree: number[];  // sum for each node's range
  private lazy: number[];  // pending add for each node's range
  private n: number;
 
  constructor(nums: number[]) {
    this.n = nums.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.lazy = new Array(4 * this.n).fill(0);
    this.build(nums, 0, 0, this.n - 1);
  }
 
  private build(nums: number[], node: number, start: number, end: number): void {
    if (start === end) { this.tree[node] = nums[start]; return; }
    const mid = (start + end) >> 1;
    this.build(nums, 2*node+1, start, mid);
    this.build(nums, 2*node+2, mid+1, end);
    this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
  }
 
  // Push pending lazy value down to children — MUST call before accessing children
  private pushDown(node: number, start: number, end: number): void {
    if (this.lazy[node] !== 0) {
      const mid = (start + end) >> 1;
      const left = 2 * node + 1;
      const right = 2 * node + 2;
 
      // Apply lazy to left child
      this.tree[left] += this.lazy[node] * (mid - start + 1);
      this.lazy[left] += this.lazy[node];
 
      // Apply lazy to right child
      this.tree[right] += this.lazy[node] * (end - mid);
      this.lazy[right] += this.lazy[node];
 
      // Clear lazy at current node (propagated to children)
      this.lazy[node] = 0;
    }
  }
 
  // Range add: add `val` to all elements in [l, r] — O(log N)
  rangeAdd(l: number, r: number, val: number): void {
    this.rangeAddHelper(0, 0, this.n - 1, l, r, val);
  }
 
  private rangeAddHelper(node: number, start: number, end: number, l: number, r: number, val: number): void {
    if (r < start || end < l) return; // outside range
 
    if (l <= start && end <= r) {
      // Fully covered: apply to this node, mark lazy for children
      this.tree[node] += val * (end - start + 1);
      this.lazy[node] += val;
      return;
    }
 
    // Partial: push down before going deeper
    this.pushDown(node, start, end);
 
    const mid = (start + end) >> 1;
    this.rangeAddHelper(2*node+1, start, mid, l, r, val);
    this.rangeAddHelper(2*node+2, mid+1, end, l, r, val);
    this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
  }
 
  // Range sum query [l, r] — O(log N)
  rangeQuery(l: number, r: number): number {
    return this.rangeQueryHelper(0, 0, this.n - 1, l, r);
  }
 
  private rangeQueryHelper(node: number, start: number, end: number, l: number, r: number): number {
    if (r < start || end < l) return 0; // outside
    if (l <= start && end <= r) return this.tree[node]; // fully inside
 
    // Partial: push down BEFORE querying children
    this.pushDown(node, start, end);
 
    const mid = (start + end) >> 1;
    return (
      this.rangeQueryHelper(2*node+1, start, mid, l, r) +
      this.rangeQueryHelper(2*node+2, mid+1, end, l, r)
    );
  }
}
// Build: O(N) | rangeAdd: O(log N) | rangeQuery: O(log N)
// Without lazy: range update = O(N*log N). With lazy: O(log N). Big difference!

4.4 Count Smaller Numbers After Self (#315) — Coordinate Compression + Segment Tree

// #315 Count of Smaller Numbers After Self
// Approach: process from RIGHT to LEFT
// For each element, query how many elements already inserted are SMALLER than it
// Then insert current element
// Use coordinate compression to map values to [0, n-1]
 
function countSmaller(nums: number[]): number[] {
  const n = nums.length;
 
  // Coordinate compression: map nums values to [0, n-1]
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  sorted.forEach((val, idx) => rank.set(val, idx));
 
  // Segment tree on compressed values — counts occurrences
  const m = sorted.length;
  const tree = new Array(4 * m).fill(0);
 
  function update(node: number, start: number, end: number, idx: number): void {
    if (start === end) { tree[node]++; return; }
    const mid = (start + end) >> 1;
    if (idx <= mid) update(2*node+1, start, mid, idx);
    else update(2*node+2, mid+1, end, idx);
    tree[node] = tree[2*node+1] + tree[2*node+2];
  }
 
  function query(node: number, start: number, end: number, l: number, r: number): number {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    const mid = (start + end) >> 1;
    return query(2*node+1, start, mid, l, r) + query(2*node+2, mid+1, end, l, r);
  }
 
  const result: number[] = new Array(n);
 
  // Process from right to left
  for (let i = n - 1; i >= 0; i--) {
    const r = rank.get(nums[i])!;
    // Count elements already inserted with rank < r (i.e., value < nums[i])
    result[i] = r > 0 ? query(0, 0, m - 1, 0, r - 1) : 0;
    // Insert current element
    update(0, 0, m - 1, r);
  }
 
  return result;
}
// Time: O(N log N) | Space: O(N)

4.5 #307 Range Sum Query Mutable — Clean Final Solution

// #307 — the standard segment tree interview problem
class NumArray {
  private tree: number[];
  private n: number;
 
  constructor(private nums: number[]) {
    this.n = nums.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(0, 0, this.n - 1);
  }
 
  private build(node: number, start: number, end: number): void {
    if (start === end) { this.tree[node] = this.nums[start]; return; }
    const mid = (start + end) >> 1;
    this.build(2*node+1, start, mid);
    this.build(2*node+2, mid+1, end);
    this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
  }
 
  update(index: number, val: number): void {
    this.nums[index] = val; // keep nums in sync (optional but useful)
    this.updateHelper(0, 0, this.n - 1, index, val);
  }
 
  private updateHelper(node: number, start: number, end: number, idx: number, val: number): void {
    if (start === end) { this.tree[node] = val; return; }
    const mid = (start + end) >> 1;
    if (idx <= mid) this.updateHelper(2*node+1, start, mid, idx, val);
    else this.updateHelper(2*node+2, mid+1, end, idx, val);
    this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
  }
 
  sumRange(left: number, right: number): number {
    return this.queryHelper(0, 0, this.n - 1, left, right);
  }
 
  private queryHelper(node: number, start: number, end: number, l: number, r: number): number {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return this.tree[node];
    const mid = (start + end) >> 1;
    return (
      this.queryHelper(2*node+1, start, mid, l, r) +
      this.queryHelper(2*node+2, mid+1, end, l, r)
    );
  }
}
// Time: build O(N), update O(log N), sumRange O(log N)
// Space: O(N) for tree array (size 4N)

5. Complexity Deep-dive

Complexity Analysis

Operation	Time	Explanation
Build	$O (N)$	Visit each node once, $2 N$ total nodes
Point Update	$O (lo g N)$	Path from leaf to root, height = $lo g N$
Range Query	$O (lo g N)$	At most $4 lo g N$ nodes visited per query
Range Update (no lazy)	$O (N lo g N)$	Must update each leaf in range
Range Update (lazy)	$O (lo g N)$	Defer update, mark lazy
Space	$O (N)$	Tree array of size $4 N$

Tại sao tree size = 4N?

Cây segment tree là full binary tree. Với $N$ leaves:

Nếu $N$ là power of 2: total nodes = $2 N - 1 < 2 N$
Nếu $N$ là NOT power of 2: cần pad lên power of 2 → tối đa $2 \cdot 2^{⌈ l o g_{2} N ⌉}$
Worst case: $N = 2^{k} + 1$ → next power of 2 = $2^{k + 1}$ → total nodes = $2 \cdot 2^{k + 1} = 4 \cdot 2^{k - 1} < 4 N$

Do đó $4 N$ nodes luôn đủ. Không cần tính chính xác — cứ dùng $4 N$ .

Lazy Propagation — Tại sao cần thiết?

Range update không có lazy: phải đi đến từng leaf trong range → $O (K)$ leaves → $O (K lo g N)$ per update.

Với lazy: khi một node hoàn toàn nằm trong update range:

Cập nhật aggregate của node ngay (tree[node] += val * rangeSize)
Đánh dấu lazy[node] += val
Không đi xuống children (chưa cần)
Khi sau này query/update đi qua node này → pushDown lazy xuống children trước

Result: $O (lo g N)$ per range update.

6. Edge Cases & Pitfalls

Pitfall 1: Tree Size Quá Nhỏ
// BUG: chỉ allocate 2*n
this.tree = new Array(2 * this.n).fill(0); // SAI! có thể bị index out of bounds
 
// CORRECT: luôn dùng 4*n
this.tree = new Array(4 * this.n).fill(0);
Index của node con: left = 2*node + 1, right = 2*node + 2. Node ở level sâu nhất có thể có index lên tới $\approx 4 N$ .

Pitfall 2: 0-indexed vs 1-indexed

Trong hầu hết implementations (kể cả code ở trên), arrays là 0-indexed:

Array indices: 0 to n-1

Tree node: root = 0, left child = 2node+1, right child = 2node+2

Một số implementations (đặc biệt competitive programming) dùng 1-indexed:

Tree node: root = 1, left = 2node, right = 2node+1

Chọn một convention và nhất quán.

Pitfall 3: Quên pushDown trong Lazy Propagation

// BUG: query children trực tiếp mà không pushDown
private queryHelper(node, start, end, l, r): number {
  if (...) return 0;
  if (...) return this.tree[node]; // OK — fully covered
  // MISSING pushDown! Children có lazy pending chưa được apply
  const mid = ...;
  return this.queryHelper(left, ...) + this.queryHelper(right, ...);
}
 
// CORRECT: pushDown BEFORE accessing children
private queryHelper(node, start, end, l, r): number {
  if (...) return 0;
  if (...) return this.tree[node];
  this.pushDown(node, start, end); // MUST DO THIS FIRST
  const mid = ...;
  return this.queryHelper(left, ...) + this.queryHelper(right, ...);
}

Pitfall 4: Out-of-Range Query Identity Element

Return identity element khi query falls completely outside range:

Sum → return 0

Min → return Infinity

Max → return -Infinity

Product → return 1

GCD → return 0 (gcd(x, 0) = x)

Pitfall 5: Non-Commutative Operations

Range sum: order doesn’t matter. a + b = b + a. Lazy propagation works fine.

Một số operations không commutative (matrix multiplication, range assignment + range multiply): → Order of lazy application matters. → Need to store multiple lazy values or use a more complex pushDown. Trong interviews, stick với commutative operations (sum, min, max, gcd).

7. Pattern Recognition

Nhận Diện Segment Tree Pattern

Dấu hiệu rõ ràng:

“Range sum/min/max queries” + “point updates” → Basic Segment Tree
“Range add value” + “range sum query” → Lazy Propagation Segment Tree
“Count elements less than X in range [l, r]” → Segment Tree on sorted values (coordinate compression)

Dấu hiệu tinh tế:

N, Q đều = 10^5 → O(N) per query sẽ TLE → cần O(log N) structure
“Dynamic” prefix sum — prefix sum thay đổi → Segment Tree thay vì static prefix sum
“Sliding window with updates” → có thể cần Segment Tree

Segment Tree vs Fenwick Tree (BIT):

	Segment Tree	Fenwick Tree (BIT)
Sum query/update	✓	✓
Min/Max query	✓	✗ (not directly)
Range update	✓ (với lazy)	✓ (với difference array trick)
Implementation complexity	Medium-High	Low
Constant factor	Larger	Smaller

Rule of thumb: nếu cần min/max range query → Segment Tree. Nếu chỉ cần sum → BIT thường dễ code hơn.

Related Patterns:

Coordinate Compression + Segment Tree → Count elements in value range
Sweep Line + Segment Tree → Rectangle area union (#850)
Offline queries + Segment Tree → Range mode query, etc.

8. Top LeetCode Problems

#	Problem	Difficulty	Pattern	Key Insight
#307	Range Sum Query Mutable	Medium	Basic Segment Tree	Entry-level implementation
#315	Count Smaller Numbers After Self	Hard	Seg Tree + Coord Compress	Process right-to-left, count smaller
#327	Count of Range Sum	Hard	Seg Tree + Merge Sort	Prefix sum + count in range
#493	Reverse Pairs	Hard	Seg Tree / Merge Sort	Count pairs (i,j) where nums[i] > 2*nums[j]
#715	Range Module	Hard	Segment Tree (intervals)	Track covered/uncovered ranges
#850	Rectangle Area II	Hard	Sweep Line + Seg Tree	Coordinate compress y, sweep x
#2179	Count Good Triplets in Array	Hard	Seg Tree + Coordinate Compress	Count with dual constraints

Complete Solution: Lazy Propagation Segment Tree

// Full LazySegTree — supports range add + range sum query
class LazySegTree {
  private tree: number[];
  private lazy: number[];
  private n: number;
 
  constructor(nums: number[]) {
    this.n = nums.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.lazy = new Array(4 * this.n).fill(0);
    this.build(nums, 0, 0, this.n - 1);
  }
 
  private build(nums: number[], node: number, s: number, e: number): void {
    if (s === e) { this.tree[node] = nums[s]; return; }
    const m = (s + e) >> 1;
    this.build(nums, 2*node+1, s, m);
    this.build(nums, 2*node+2, m+1, e);
    this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
  }
 
  private push(node: number, s: number, e: number): void {
    if (this.lazy[node]) {
      const m = (s + e) >> 1;
      const l = 2*node+1, r = 2*node+2;
      this.tree[l] += this.lazy[node] * (m - s + 1);
      this.tree[r] += this.lazy[node] * (e - m);
      this.lazy[l] += this.lazy[node];
      this.lazy[r] += this.lazy[node];
      this.lazy[node] = 0;
    }
  }
 
  add(l: number, r: number, val: number): void {
    this.addHelper(0, 0, this.n-1, l, r, val);
  }
 
  private addHelper(node: number, s: number, e: number, l: number, r: number, v: number): void {
    if (r < s || e < l) return;
    if (l <= s && e <= r) {
      this.tree[node] += v * (e - s + 1);
      this.lazy[node] += v;
      return;
    }
    this.push(node, s, e);
    const m = (s + e) >> 1;
    this.addHelper(2*node+1, s, m, l, r, v);
    this.addHelper(2*node+2, m+1, e, l, r, v);
    this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
  }
 
  sum(l: number, r: number): number {
    return this.sumHelper(0, 0, this.n-1, l, r);
  }
 
  private sumHelper(node: number, s: number, e: number, l: number, r: number): number {
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) return this.tree[node];
    this.push(node, s, e);
    const m = (s + e) >> 1;
    return this.sumHelper(2*node+1, s, m, l, r) + this.sumHelper(2*node+2, m+1, e, l, r);
  }
}

Complete Solution: #307 Range Sum Query Mutable (Final Clean Version)

class NumArray {
  private tree: number[];
  private n: number;
 
  constructor(private nums: number[]) {
    this.n = nums.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(0, 0, this.n - 1);
  }
 
  private build(node: number, s: number, e: number): void {
    if (s === e) { this.tree[node] = this.nums[s]; return; }
    const m = (s + e) >> 1;
    this.build(2*node+1, s, m);
    this.build(2*node+2, m+1, e);
    this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
  }
 
  update(index: number, val: number): void {
    this.upd(0, 0, this.n-1, index, val);
  }
 
  private upd(node: number, s: number, e: number, i: number, v: number): void {
    if (s === e) { this.tree[node] = v; return; }
    const m = (s + e) >> 1;
    if (i <= m) this.upd(2*node+1, s, m, i, v);
    else this.upd(2*node+2, m+1, e, i, v);
    this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
  }
 
  sumRange(left: number, right: number): number {
    return this.qry(0, 0, this.n-1, left, right);
  }
 
  private qry(node: number, s: number, e: number, l: number, r: number): number {
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) return this.tree[node];
    const m = (s + e) >> 1;
    return this.qry(2*node+1, s, m, l, r) + this.qry(2*node+2, m+1, e, l, r);
  }
}
// Time: build O(N), update O(log N), sumRange O(log N)
// Space: O(N) for tree (4N nodes)

9. Self-Assessment Checklist

Checklist — Segment Tree

Concept Understanding:

Giải thích được tại sao tree array cần size 4N (không phải 2N)
Giải thích được 3 cases trong query: outside, fully inside, partial
Giải thích được lazy propagation và khi nào cần pushDown
So sánh được Segment Tree vs Fenwick Tree (khi dùng cái nào)

Implementation:

Implement SegmentTree sum từ đầu (không nhìn gợi ý) trong < 20 phút
Implement point update đúng (recompute parent nodes)
Implement range query với 3 cases đúng
Implement lazy propagation (range add + range sum) trong < 35 phút

Problem Solving:

Solve #307 Range Sum Query Mutable trong < 15 phút
Explain approach cho #315 Count Smaller After Self
Biết khi nào dùng coordinate compression với Segment Tree

FAANG Interview Readiness

Code Segment Tree sum từ scratch trong 20 phút với zero bugs
Code Lazy Propagation trong 35 phút
Solve #315 với Seg Tree approach trong < 40 phút
Explain trade-offs: Segment Tree vs BIT vs Sqrt Decomposition

Next Steps

12-Practice-FAANG-1 — Mock FAANG Problems Kết hợp DP (09-Dynamic-Programming, 10-Advanced-DP) + Segment Tree để giải các bài Hard FAANG tổng hợp.

lthieu's notes

Explorer

11-Segment-Tree

Buổi 11 — Segment Tree

1. Analogy & Context

2. The FAANG Standard

3. Visual Thinking (Mermaid)

3.1 Segment Tree Structure — Array [1, 3, 5, 7, 9, 11]

3.2 Query(1, 4) — Which Nodes Are Combined

3.3 Update(2, 6) — Which Nodes Are Recomputed

4. TypeScript Template

4.1 Segment Tree — Sum (Complete Implementation)

4.2 Segment Tree — Min Variant

4.3 Lazy Propagation — Range Update + Range Query

4.4 Count Smaller Numbers After Self (#315) — Coordinate Compression + Segment Tree

4.5 #307 Range Sum Query Mutable — Clean Final Solution

5. Complexity Deep-dive

6. Edge Cases & Pitfalls

7. Pattern Recognition

8. Top LeetCode Problems

Complete Solution: Lazy Propagation Segment Tree

Complete Solution: #307 Range Sum Query Mutable (Final Clean Version)

9. Self-Assessment Checklist

Graph View

Table of Contents

Backlinks