Segment Tree và Fenwick Tree (Binary Indexed Tree) là gì? Giải thích dễ hiểu kèm demo range query trên mảng số

Trong rất nhiều bài toán thực tế, ta có một mảng số và cần liên tục:

• Query: tính tổng đoạn (range sum) A[l..r], hoặc min/max trên đoạn.
• Update: thay đổi một phần tử A[i].

Nếu làm kiểu “ngây thơ” (duyệt từ l đến r) thì mỗi query tốn O(n), rất chậm khi mảng lớn và số lần query/update nhiều. Khi đó, hai cấu trúc dữ liệu kinh điển bước vào sân:

• Segment Tree: cây phân đoạn, lưu thông tin cho từng đoạn con của mảng.
• Fenwick Tree (Binary Indexed Tree – BIT): cấu trúc gọn hơn, chuyên cho các phép cộng prefix và update điểm.

Cả hai đều cho phép query và update trong O(log n), cực kỳ hữu ích trong competitive programming, xử lý log, analytics, game, v.v.

Bài toán: Range Sum trên mảng số

Giả sử ta có mảng A[0..n-1] và muốn hỗ trợ hai thao tác:

• UpdateSet(i, x): gán A[i] = x.
• QuerySum(l, r): tính tổng A[l] + A[l+1] + … + A[r].

Mục tiêu: xử lý rất nhiều query/update nhanh, thay vì mỗi lần lại duyệt cả đoạn.

Segment Tree: ý tưởng cơ bản

Segment Tree là một cây nhị phân trong đó:

• Mỗi node đại diện cho một đoạn con [L, R] trong mảng.
• Node gốc đại diện cho đoạn [0, n-1].
• Node con trái đại diện cho [L, mid], node con phải đại diện cho [mid+1, R].
• Mỗi node lưu thông tin (ở đây là tổng trên đoạn đó).

Khi cần query [l, r], ta chia nhỏ đoạn này thành một số ít đoạn con trùng với node trong cây, cộng lại kết quả. Khi update A[i], ta chỉ cần cập nhật các node trên đường từ lá (đại diện cho A[i]) lên tới gốc → mỗi thao tác O(log n).

Fenwick Tree (Binary Indexed Tree): ý tưởng cơ bản

Fenwick Tree là một mảng phụ BIT[1..n], trong đó mỗi ô BIT[i] lưu tổng của một đoạn “có dạng đặc biệt” kết thúc tại i. Độ dài đoạn này được quyết định bởi i & -i (bit thấp nhất của i).

• Để tính tổng prefix sum(1..i), ta cộng các BIT[i], BIT[i – (i&-i)], … cho tới khi về 0.
• Để update tại vị trí i, ta đi theo các index i, i + (i&-i), … và cộng dồn delta.

Nhìn hơi “bit trick” nhưng thực ra chỉ là cách nén một Segment Tree 1 chiều thành một mảng.

Mô hình demo: Segment Tree & Fenwick Tree cho range sum

Demo dưới đây cho phép:

• Xem một mảng nhỏ (8 phần tử) và các cấu trúc tương ứng.
• Chọn Segment Tree hoặc Fenwick Tree để minh họa.
• Random mảng giá trị nhỏ.
• Cập nhật A[i] bằng một giá trị mới.
• Query [l, r] để tính tổng trên đoạn.
• Visual:
  • Mảng A hiển thị ở hàng dưới cùng.
  • Segment Tree vẽ phía trên (các node thể hiện đoạn [L, R]).
  • Fenwick Tree highlight các index BIT được truy cập khi tính prefix sum.
• Log chi tiết các node / index được truy cập trong mỗi thao tác.

Demo Segment Tree & Fenwick Tree bằng JavaScript

Giải thích nhanh cấu trúc code

• arr[i]: mảng gốc A[0..n-1] mà ta muốn xử lý range sum.
• seg[]: mảng Segment Tree, mỗi node lưu tổng trên một đoạn con [L, R] của mảng.
• bit[]: mảng Fenwick Tree (Binary Indexed Tree), hỗ trợ prefix sum và update điểm.
• Segment Tree:
  • build(node, L, R): xây cây từ mảng ban đầu.
  • segUpdate(node, L, R, idx, val): cập nhật A[idx] = val và chỉnh lại các node liên quan.
  • segQuery(node, L, R, ql, qr): tính tổng A[ql..qr] bằng cách chia đoạn thành các node phù hợp.
• Fenwick Tree:
  • bitAdd(i, delta): cộng thêm delta vào A[i] trong BIT.
  • bitPrefix(i): tính tổng A[0..i] bằng cách đi lùi theo i & -i.
  • bitRange(l, r): tính tổng A[l..r] = prefix(r) – prefix(l-1).
• Khi thay đổi mảng (random/reset/update), ta cập nhật cả Segment Tree và Fenwick Tree để hai cấu trúc luôn “sync” với nhau.
• Khi query, demo highlight các node / index được truy cập và log lại đường đi để dễ hình dung.