Bài 6: Segment Tree / Fenwick Tree — Truy Vấn Đoạn Con O(log n)

Ở Bài 5 chúng ta trả lời câu hỏi "2 node có cùng nhóm không?" cực nhanh bằng Union-Find. Bài này giải một bài toán truy vấn khác cũng rất phổ biến: tổng của một đoạn con trong mảng — nhưng mảng đó liên tục bị cập nhật giá trị theo thời gian thực.

1. Bài toán: Truy vấn tổng đoạn con động

Cho mảng $n$ số, bạn cần trả lời liên tục 2 loại truy vấn xen kẽ: "tổng các phần tử từ chỉ số $l$ đến $r$ là bao nhiêu?" và "cập nhật giá trị tại chỉ số $i$ thành $v$". Nếu dùng mảng tổng tiền tố (prefix sum) quen thuộc, truy vấn tổng đoạn chỉ tốn $O(1)$ — cực nhanh. Nhưng mỗi lần cập nhật một phần tử, toàn bộ mảng tổng tiền tố phía sau nó phải tính lại — tốn $O(n)$. Với hàng chục nghìn lượt cập nhật xen kẽ hàng chục nghìn truy vấn, cách này quá chậm.

Segment Tree và Fenwick Tree giải quyết đúng vấn đề này: cả truy vấn và cập nhật đều chỉ tốn $O(\log n)$ — đánh đổi một chút so với $O(1)$ của prefix sum để đổi lấy khả năng cập nhật nhanh.

2. Segment Tree: Cây nhị phân chia đôi đoạn

Segment Tree biểu diễn mảng dưới dạng cây nhị phân: node gốc đại diện cho toàn bộ đoạn $[0, n{-}1]$, mỗi node con chia đôi đoạn của node cha, tới khi mỗi lá chỉ còn 1 phần tử. Mỗi node lưu sẵn tổng của đoạn nó đại diện:

class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0); // đủ chỗ cho mọi node
    this.build(arr, 1, 0, this.n - 1);
  }

  build(arr, node, l, r) {
    if (l === r) {
      this.tree[node] = arr[l];
      return;
    }
    const mid = Math.floor((l + r) / 2);
    this.build(arr, 2 * node, l, mid);       // con trái: nửa đầu đoạn
    this.build(arr, 2 * node + 1, mid + 1, r); // con phải: nửa sau đoạn
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }
}

Truy vấn tổng đoạn $[ql, qr]$ chỉ cần xét node nào chồng lấn với đoạn cần hỏi:

SegmentTree.prototype.query = function (node, l, r, ql, qr) {
  if (qr < l || r < ql) return 0; // không chồng lấn — bỏ qua nhánh này

  if (ql <= l && r <= qr) return this.tree[node]; // node nằm HOÀN TOÀN trong đoạn hỏi

  // chồng lấn một phần — phải xét cả 2 con
  const mid = Math.floor((l + r) / 2);
  return (
    this.query(2 * node, l, mid, ql, qr) +
    this.query(2 * node + 1, mid + 1, r, ql, qr)
  );
};

Cập nhật giá trị tại 1 chỉ số chỉ cần đi theo đúng 1 đường từ gốc xuống lá rồi cập nhật ngược lên:

SegmentTree.prototype.update = function (node, l, r, idx, val) {
  if (l === r) {
    this.tree[node] = val; // tới đúng lá cần sửa
    return;
  }
  const mid = Math.floor((l + r) / 2);
  if (idx <= mid) this.update(2 * node, l, mid, idx, val);
  else this.update(2 * node + 1, mid + 1, r, idx, val);

  // cập nhật lại tổng của node cha sau khi con đã đổi
  this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
};

3. Fenwick Tree (Binary Indexed Tree): Nén gọn bằng bit

Fenwick Tree (Peter Fenwick, 1994) làm đúng việc tương tự nhưng chỉ cần một mảng kích thước $n{+}1$ — không cần cây tường minh. Bí quyết nằm ở hàm lowbit(x) = x \& (-x), tách ra bit "1" thấp nhất của $x$ trong biểu diễn nhị phân, dùng để nhảy giữa các node cha/con ngầm định:

class FenwickTree {
  constructor(n) {
    this.n = n;
    this.tree = new Array(n + 1).fill(0); // 1-indexed
  }

  // Cộng thêm delta vào chỉ số i (1-indexed)
  update(i, delta) {
    for (; i <= this.n; i += i & -i) { // nhảy TỚI node cha chứa i
      this.tree[i] += delta;
    }
  }

  // Tổng tiền tố từ 1 tới i
  prefixSum(i) {
    let sum = 0;
    for (; i > 0; i -= i & -i) { // nhảy XUỐNG các đoạn con hợp thành
      sum += this.tree[i];
    }
    return sum;
  }

  // Tổng đoạn [l, r] (1-indexed)
  rangeSum(l, r) {
    return this.prefixSum(r) - this.prefixSum(l - 1);
  }
}

4. So sánh Segment Tree, Fenwick Tree và Prefix Sum

Sân chơi tương tác: Segment Tree Visualizer

Cập nhật một ô trong mảng để xem đường đi từ lá lên gốc được tô sáng và giá trị các node cha tự cập nhật lại, hoặc truy vấn một đoạn để xem chính xác những node nào được kết hợp để ra kết quả.