Segment tree và Fenwick tree (BIT) hỗ trợ truy vấn khoảng nhanh như thế nào?

Question

Accepted Answer

Một **segment tree** và một **Fenwick tree** (Binary Indexed Tree, BIT) đều trả lời **truy vấn khoảng (range query)** (ví dụ tổng trên `[l, r]`) và **cập nhật điểm (point update)** trong **O(log n)**, so với O(n) cho một lần quét ngây thơ hoặc O(n) cập nhật cho một array prefix-sum.

## Bài toán chúng giải quyết

```text
Array + nhiều lời gọi "tổng của khoảng [l,r]" và "cập nhật index i":
  prefix sum ngây thơ: truy vấn O(1) nhưng CẬP NHẬT là O(n)
  segment/Fenwick:     truy vấn O(log n) VÀ cập nhật O(log n)
```

## Fenwick tree (BIT) — gọn gàng và thanh lịch

```python
class Fenwick:
    def __init__(self, n):
        self.t = [0]*(n+1)
    def update(self, i, delta):        # O(log n)
        i += 1
        while i < len(self.t):
            self.t[i] += delta
            i += i & (-i)              # nhảy tới node chịu trách nhiệm tiếp theo
    def prefix(self, i):               # tổng của [0..i], O(log n)
        i += 1; s = 0
        while i > 0:
            s += self.t[i]
            i -= i & (-i)
        return s
    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l-1)
```

## Segment tree — tổng quát hơn

Một segment tree lưu một giá trị tổng hợp (aggregate) cho mỗi đoạn array trong một binary tree, hỗ trợ **bất kỳ phép kết hợp (associative) nào** (sum, min, max, gcd) và, với lazy propagation, cả **cập nhật khoảng (range update)**.

```text
        [0..7] sum
       /          \
   [0..3]         [4..7]
   /    \         /    \
 [0..1][2..3]  [4..5][6..7]   ... xuống tới từng phần tử đơn lẻ
```

## So sánh

| | Fenwick (BIT) | Segment tree |
|---|---|---|
| Truy vấn / cập nhật | O(log n) | O(log n) |
| Không gian | O(n) | O(2n) |
| Thao tác | tổng (khả nghịch) | bất kỳ phép kết hợp nào |
| Cập nhật khoảng | khó hơn | dễ (lazy propagation) |
| Kích thước code | nhỏ xíu | lớn hơn |

## Tại sao điều này quan trọng

Những cấu trúc này khiến "cập nhật một giá trị, rồi truy vấn một tổng hợp trên một khoảng" trở nên nhanh — thiết yếu cho lập trình thi đấu, cửa sổ phân tích (analytics window), và các bài toán khoảng.

Lựa chọn giữa chúng là một đánh đổi: một Fenwick tree nhỏ xíu và nhanh cho các tổng, trong khi một segment tree linh hoạt hơn cho các workload min/max/cập nhật khoảng.

	Fenwick (BIT)	Segment tree
Truy vấn / cập nhật	O(log n)	O(log n)
Không gian	O(n)	O(2n)
Thao tác	tổng (khả nghịch)	bất kỳ phép kết hợp nào
Cập nhật khoảng	khó hơn	dễ (lazy propagation)
Kích thước code	nhỏ xíu	lớn hơn