Segment Tree — Vua truy vấn đoạn

Một hệ thống giám sát mạng cần trả lời liên tục: "Tổng lưu lượng từ giây thứ L đến giây thứ R là bao nhiêu?" — đồng thời dữ liệu mới đổ về mỗi mili-giây. Prefix sum trả lời query O(1) nhưng mỗi lần cập nhật phải rebuild O(n). Mảng thô update O(1) nhưng mỗi query quét O(n). Với 10⁵ query trên 10⁵ phần tử, cả hai đều timeout.

Segment Tree phá vỡ thế bế tắc đó bằng cách chia mảng thành các đoạn con theo cấu trúc cây nhị phân, mỗi node lưu sẵn kết quả aggregate của đoạn nó quản lý. Cả query lẫn update đều chạy trong O(log n). Khi cần update nguyên một đoạn, lazy propagation giữ chi phí amortized ở O(log n) cho mỗi thao tác.

Bức tranh tư duy

Hình dung một công ty có cấu trúc phòng ban hình cây. Mỗi trưởng phòng nắm tổng doanh thu của phòng mình. Khi CEO cần biết doanh thu từ phòng 3 đến phòng 7, thay vì hỏi từng nhân viên, CEO hỏi vài trưởng phòng — mỗi người đã tổng hợp sẵn. Khi một nhân viên thay đổi doanh thu, chỉ cần cập nhật các cấp quản lý trực tiếp phía trên.

Mảng gốc: [1, 3, 5, 7, 9, 11]

                    [36]              ← tổng toàn bộ
                   /    \
               [9]        [27]        ← tổng nửa trái / phải
              /   \       /   \
           [4]    [5]  [16]   [11]    ← chia tiếp
           / \         /  \
         [1] [3]     [7]  [9]        ← lá = phần tử gốc

Mỗi node lưu aggregate (tổng, min, max, gcd...) của đoạn con nó phụ trách. Query đoạn [L, R] chỉ cần ghé thăm O(log n) node. Update một phần tử chỉ ảnh hưởng O(log n) node trên đường từ lá đến gốc.

Phép so sánh này bắt đầu "vỡ" khi cần lazy propagation — lúc đó mỗi trưởng phòng có thể "ghi nợ" thông tin xuống cấp dưới thay vì cập nhật ngay. Nhưng bản chất vẫn là: chia để trị trên mảng, lưu kết quả trung gian tại mỗi cấp.

Cốt lõi kỹ thuật

Cấu trúc dữ liệu

Segment Tree là cây nhị phân đầy đủ lưu trong mảng phẳng. Node gốc ở vị trí 1, con trái của node i ở 2*i, con phải ở 2*i + 1. Mảng cần kích thước 4n để đảm bảo đủ chỗ cho mọi trường hợp.

Thuộc tính	Giá trị
Chiều cao	⌈log₂ n⌉
Số node tối đa	2 × 2^⌈log₂ n⌉ − 1
Bộ nhớ cần cấp	4n (an toàn)
Mỗi node lưu	Aggregate của đoạn [l, r]

Build — O(n)

Dựng cây từ dưới lên: lá mang giá trị gốc, mỗi node cha kết hợp hai con.

C++PythonJavaGo

cpp

const int MAXN = 100005;
int tree[4 * MAXN], a[MAXN];

void build(int node, int start, int end) {
    if (start == end) {
        tree[node] = a[start];
        return;
    }
    int mid = (start + end) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

python

def build(node: int, start: int, end: int) -> None:
    if start == end:
        tree[node] = a[start]
        return
    mid = (start + end) // 2
    build(2 * node, start, mid)
    build(2 * node + 1, mid + 1, end)
    tree[node] = tree[2 * node] + tree[2 * node + 1]

java

int[] tree, a;

void build(int node, int start, int end) {
    if (start == end) {
        tree[node] = a[start];
        return;
    }
    int mid = (start + end) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

func build(tree, a []int, node, start, end int) {
    if start == end {
        tree[node] = a[start]
        return
    }
    mid := (start + end) / 2
    build(tree, a, 2*node, start, mid)
    build(tree, a, 2*node+1, mid+1, end)
    tree[node] = tree[2*node] + tree[2*node+1]
}

Range Query — O(log n)

Truy vấn đoạn [L, R] rơi vào ba trường hợp tại mỗi node quản lý đoạn [start, end]:

Hoàn toàn ngoài [L, R] → trả về phần tử đơn vị (0 cho sum, +∞ cho min).
Hoàn toàn trong [L, R] → trả về giá trị node ngay lập tức.
Giao nhau một phần → đệ quy cả hai con, kết hợp kết quả.

C++PythonJavaGo

cpp

int query(int node, int start, int end, int L, int R) {
    if (R < start || end < L) return 0;
    if (L <= start && end <= R) return tree[node];
    int mid = (start + end) / 2;
    return query(2 * node, start, mid, L, R)
         + query(2 * node + 1, mid + 1, end, L, R);
}

python

def query(node: int, start: int, end: int, L: int, R: int) -> int:
    if R < start or end < L:
        return 0
    if L <= start and end <= R:
        return tree[node]
    mid = (start + end) // 2
    return (query(2 * node, start, mid, L, R)
          + query(2 * node + 1, mid + 1, end, L, R))

java

int query(int node, int start, int end, int L, int R) {
    if (R < start || end < L) return 0;
    if (L <= start && end <= R) return tree[node];
    int mid = (start + end) / 2;
    return query(2 * node, start, mid, L, R)
         + query(2 * node + 1, mid + 1, end, L, R);
}

func query(tree []int, node, start, end, L, R int) int {
    if R < start || end < L {
        return 0
    }
    if L <= start && end <= R {
        return tree[node]
    }
    mid := (start + end) / 2
    return query(tree, 2*node, start, mid, L, R) +
           query(tree, 2*node+1, mid+1, end, L, R)
}

Point Update — O(log n)

Cập nhật a[idx] = val: đi từ gốc xuống lá chứa idx, cập nhật ngược lên.

C++PythonJavaGo

cpp

void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        tree[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid)
        update(2 * node, start, mid, idx, val);
    else
        update(2 * node + 1, mid + 1, end, idx, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

python

def update(node: int, start: int, end: int, idx: int, val: int) -> None:
    if start == end:
        tree[node] = val
        return
    mid = (start + end) // 2
    if idx <= mid:
        update(2 * node, start, mid, idx, val)
    else:
        update(2 * node + 1, mid + 1, end, idx, val)
    tree[node] = tree[2 * node] + tree[2 * node + 1]

java

void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        tree[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid)
        update(2 * node, start, mid, idx, val);
    else
        update(2 * node + 1, mid + 1, end, idx, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

func update(tree []int, node, start, end, idx, val int) {
    if start == end {
        tree[node] = val
        return
    }
    mid := (start + end) / 2
    if idx <= mid {
        update(tree, 2*node, start, mid, idx, val)
    } else {
        update(tree, 2*node+1, mid+1, end, idx, val)
    }
    tree[node] = tree[2*node] + tree[2*node+1]
}

Lazy Propagation — Range Update O(log n)

Khi cần cộng val vào toàn bộ đoạn [L, R], point update từng phần tử tốn O(n log n). Lazy propagation "ghi nợ": đánh dấu node cần cập nhật nhưng chưa lan xuống con, chỉ push down khi thực sự truy cập node con.

C++PythonJavaGo

cpp

int lazy[4 * MAXN];

void pushDown(int node, int start, int end) {
    if (lazy[node] != 0) {
        int mid = (start + end) / 2;
        tree[2 * node] += lazy[node] * (mid - start + 1);
        tree[2 * node + 1] += lazy[node] * (end - mid);
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
        lazy[node] = 0;
    }
}

void rangeUpdate(int node, int start, int end, int L, int R, int val) {
    if (R < start || end < L) return;
    if (L <= start && end <= R) {
        tree[node] += val * (end - start + 1);
        lazy[node] += val;
        return;
    }
    pushDown(node, start, end);
    int mid = (start + end) / 2;
    rangeUpdate(2 * node, start, mid, L, R, val);
    rangeUpdate(2 * node + 1, mid + 1, end, L, R, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

python

lazy = [0] * (4 * MAXN)

def push_down(node: int, start: int, end: int) -> None:
    if lazy[node] != 0:
        mid = (start + end) // 2
        tree[2 * node] += lazy[node] * (mid - start + 1)
        tree[2 * node + 1] += lazy[node] * (end - mid)
        lazy[2 * node] += lazy[node]
        lazy[2 * node + 1] += lazy[node]
        lazy[node] = 0

def range_update(node: int, start: int, end: int,
                 L: int, R: int, val: int) -> None:
    if R < start or end < L:
        return
    if L <= start and end <= R:
        tree[node] += val * (end - start + 1)
        lazy[node] += val
        return
    push_down(node, start, end)
    mid = (start + end) // 2
    range_update(2 * node, start, mid, L, R, val)
    range_update(2 * node + 1, mid + 1, end, L, R, val)
    tree[node] = tree[2 * node] + tree[2 * node + 1]

java

int[] lazy = new int[4 * MAXN];

void pushDown(int node, int start, int end) {
    if (lazy[node] != 0) {
        int mid = (start + end) / 2;
        tree[2 * node] += lazy[node] * (mid - start + 1);
        tree[2 * node + 1] += lazy[node] * (end - mid);
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
        lazy[node] = 0;
    }
}

void rangeUpdate(int node, int start, int end, int L, int R, int val) {
    if (R < start || end < L) return;
    if (L <= start && end <= R) {
        tree[node] += val * (end - start + 1);
        lazy[node] += val;
        return;
    }
    pushDown(node, start, end);
    int mid = (start + end) / 2;
    rangeUpdate(2 * node, start, mid, L, R, val);
    rangeUpdate(2 * node + 1, mid + 1, end, L, R, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

func pushDown(tree, lazy []int, node, start, end int) {
    if lazy[node] != 0 {
        mid := (start + end) / 2
        tree[2*node] += lazy[node] * (mid - start + 1)
        tree[2*node+1] += lazy[node] * (end - mid)
        lazy[2*node] += lazy[node]
        lazy[2*node+1] += lazy[node]
        lazy[node] = 0
    }
}

func rangeUpdate(tree, lazy []int, node, start, end, L, R, val int) {
    if R < start || end < L {
        return
    }
    if L <= start && end <= R {
        tree[node] += val * (end - start + 1)
        lazy[node] += val
        return
    }
    pushDown(tree, lazy, node, start, end)
    mid := (start + end) / 2
    rangeUpdate(tree, lazy, 2*node, start, mid, L, R, val)
    rangeUpdate(tree, lazy, 2*node+1, mid+1, end, L, R, val)
    tree[node] = tree[2*node] + tree[2*node+1]
}

Bảng phép toán hỗ trợ

Phép toán	Hàm kết hợp	Phần tử đơn vị	Lazy tương thích
Tổng	`a + b`	0	✅
Min	`min(a, b)`	+∞	✅
Max	`max(a, b)`	−∞	✅
GCD	`gcd(a, b)`	0	⚠️ phức tạp
XOR	`a ^ b`	0	✅
Tích	`a * b`	1	✅

Thực chiến

Tình huống: Hệ thống giám sát lưu lượng mạng

Bối cảnh: Hệ thống NOC ghi nhận lưu lượng theo từng giây. Operator truy vấn tổng lưu lượng trong khoảng [L, R] và cập nhật dữ liệu khi có điều chỉnh. Mảng 10⁶ phần tử, 10⁵ query/giây.

Mục tiêu: Trả lời range sum query và point update trong O(log n).

C++PythonJavaGo

cpp

#include <vector>
#include <stdexcept>

class NetworkMonitor {
    std::vector<long long> tree_;
    int n_;

    void build(const std::vector<int>& data, int nd, int s, int e) {
        if (s == e) { tree_[nd] = data[s]; return; }
        int mid = (s + e) / 2;
        build(data, 2*nd, s, mid);
        build(data, 2*nd+1, mid+1, e);
        tree_[nd] = tree_[2*nd] + tree_[2*nd+1];
    }

    long long qry(int nd, int s, int e, int L, int R) {
        if (R < s || e < L) return 0;
        if (L <= s && e <= R) return tree_[nd];
        int mid = (s + e) / 2;
        return qry(2*nd, s, mid, L, R) + qry(2*nd+1, mid+1, e, L, R);
    }

    void upd(int nd, int s, int e, int idx, int val) {
        if (s == e) { tree_[nd] = val; return; }
        int mid = (s + e) / 2;
        if (idx <= mid) upd(2*nd, s, mid, idx, val);
        else upd(2*nd+1, mid+1, e, idx, val);
        tree_[nd] = tree_[2*nd] + tree_[2*nd+1];
    }

public:
    explicit NetworkMonitor(const std::vector<int>& traffic)
        : n_(traffic.size()), tree_(4 * traffic.size(), 0) {
        if (n_ > 0) build(traffic, 1, 0, n_ - 1);
    }

    long long getTraffic(int L, int R) {
        if (L < 0 || R >= n_ || L > R)
            throw std::out_of_range("Invalid range");
        return qry(1, 0, n_ - 1, L, R);
    }

    void setTraffic(int idx, int val) {
        if (idx < 0 || idx >= n_)
            throw std::out_of_range("Invalid index");
        upd(1, 0, n_ - 1, idx, val);
    }
};

python

class NetworkMonitor:
    # Giám sát lưu lượng mạng với Segment Tree

    def __init__(self, traffic: list[int]) -> None:
        self.n = len(traffic)
        self.tree = [0] * (4 * self.n)
        if self.n > 0:
            self._build(traffic, 1, 0, self.n - 1)

    def _build(self, data: list[int], nd: int, s: int, e: int) -> None:
        if s == e:
            self.tree[nd] = data[s]
            return
        mid = (s + e) // 2
        self._build(data, 2 * nd, s, mid)
        self._build(data, 2 * nd + 1, mid + 1, e)
        self.tree[nd] = self.tree[2 * nd] + self.tree[2 * nd + 1]

    def get_traffic(self, L: int, R: int) -> int:
        if L < 0 or R >= self.n or L > R:
            raise ValueError(f"Invalid range [{L}, {R}]")
        return self._query(1, 0, self.n - 1, L, R)

    def _query(self, nd: int, s: int, e: int, L: int, R: int) -> int:
        if R < s or e < L:
            return 0
        if L <= s and e <= R:
            return self.tree[nd]
        mid = (s + e) // 2
        return (self._query(2 * nd, s, mid, L, R)
              + self._query(2 * nd + 1, mid + 1, e, L, R))

    def set_traffic(self, idx: int, val: int) -> None:
        if idx < 0 or idx >= self.n:
            raise ValueError(f"Invalid index {idx}")
        self._update(1, 0, self.n - 1, idx, val)

    def _update(self, nd: int, s: int, e: int, idx: int, val: int) -> None:
        if s == e:
            self.tree[nd] = val
            return
        mid = (s + e) // 2
        if idx <= mid:
            self._update(2 * nd, s, mid, idx, val)
        else:
            self._update(2 * nd + 1, mid + 1, e, idx, val)
        self.tree[nd] = self.tree[2 * nd] + self.tree[2 * nd + 1]

java

public class NetworkMonitor {
    private long[] tree;
    private int n;

    public NetworkMonitor(int[] traffic) {
        this.n = traffic.length;
        this.tree = new long[4 * n];
        if (n > 0) build(traffic, 1, 0, n - 1);
    }

    private void build(int[] data, int nd, int s, int e) {
        if (s == e) { tree[nd] = data[s]; return; }
        int mid = (s + e) / 2;
        build(data, 2 * nd, s, mid);
        build(data, 2 * nd + 1, mid + 1, e);
        tree[nd] = tree[2 * nd] + tree[2 * nd + 1];
    }

    public long getTraffic(int L, int R) {
        if (L < 0 || R >= n || L > R)
            throw new IllegalArgumentException("Invalid range");
        return query(1, 0, n - 1, L, R);
    }

    private long query(int nd, int s, int e, int L, int R) {
        if (R < s || e < L) return 0;
        if (L <= s && e <= R) return tree[nd];
        int mid = (s + e) / 2;
        return query(2*nd, s, mid, L, R) + query(2*nd+1, mid+1, e, L, R);
    }

    public void setTraffic(int idx, int val) {
        if (idx < 0 || idx >= n)
            throw new IllegalArgumentException("Invalid index");
        update(1, 0, n - 1, idx, val);
    }

    private void update(int nd, int s, int e, int idx, int val) {
        if (s == e) { tree[nd] = val; return; }
        int mid = (s + e) / 2;
        if (idx <= mid) update(2*nd, s, mid, idx, val);
        else update(2*nd+1, mid+1, e, idx, val);
        tree[nd] = tree[2*nd] + tree[2*nd+1];
    }
}

type NetworkMonitor struct {
    tree []int64
    n    int
}

func NewNetworkMonitor(traffic []int) *NetworkMonitor {
    n := len(traffic)
    nm := &NetworkMonitor{tree: make([]int64, 4*n), n: n}
    if n > 0 {
        nm.build(traffic, 1, 0, n-1)
    }
    return nm
}

func (nm *NetworkMonitor) build(data []int, nd, s, e int) {
    if s == e {
        nm.tree[nd] = int64(data[s])
        return
    }
    mid := (s + e) / 2
    nm.build(data, 2*nd, s, mid)
    nm.build(data, 2*nd+1, mid+1, e)
    nm.tree[nd] = nm.tree[2*nd] + nm.tree[2*nd+1]
}

func (nm *NetworkMonitor) GetTraffic(L, R int) (int64, error) {
    if L < 0 || R >= nm.n || L > R {
        return 0, fmt.Errorf("invalid range [%d, %d]", L, R)
    }
    return nm.query(1, 0, nm.n-1, L, R), nil
}

func (nm *NetworkMonitor) query(nd, s, e, L, R int) int64 {
    if R < s || e < L { return 0 }
    if L <= s && e <= R { return nm.tree[nd] }
    mid := (s + e) / 2
    return nm.query(2*nd, s, mid, L, R) + nm.query(2*nd+1, mid+1, e, L, R)
}

func (nm *NetworkMonitor) SetTraffic(idx, val int) {
    nm.update(1, 0, nm.n-1, idx, val)
}

func (nm *NetworkMonitor) update(nd, s, e, idx, val int) {
    if s == e { nm.tree[nd] = int64(val); return }
    mid := (s + e) / 2
    if idx <= mid { nm.update(2*nd, s, mid, idx, val) } else {
        nm.update(2*nd+1, mid+1, e, idx, val)
    }
    nm.tree[nd] = nm.tree[2*nd] + nm.tree[2*nd+1]
}

Phân tích:

Build O(n) chạy một lần khi khởi tạo.
Mỗi query/update O(log n) ≈ 20 bước cho n = 10⁶ — đáp ứng 10⁵ query/giây.
Validation input tại API boundary ngăn truy cập ngoài phạm vi.

Sai lầm điển hình

❌ Sai lầm 1: Cấp phát mảng tree kích thước 2n thay vì 4n

Vấn đề: Nhiều tài liệu viết "Segment Tree có khoảng 2n node" và lập trình viên cấp phát đúng 2n.

cpp

// SAI: thiếu bộ nhớ khi n không phải lũy thừa 2
int tree[2 * n];

Tại sao sai: Khi n không phải lũy thừa của 2, cây cần nhiều hơn 2n slot. Với n = 5, node cuối trong mảng phẳng có thể ở vị trí > 2n. Kết quả: buffer overflow hoặc kết quả sai im lặng — loại bug nguy hiểm nhất.

cpp

// ĐÚNG: luôn dùng 4n
int tree[4 * n];

❌ Sai lầm 2: Nhầm phần tử đơn vị (identity element)

Vấn đề: Dùng 0 làm giá trị trả về khi node nằm ngoài range, nhưng phép toán là min.

python

# SAI: identity cho min phải là +inf, không phải 0
def query_min(node, start, end, L, R):
    if R < start or end < L:
        return 0  # bug!

Tại sao sai: min(5, 0) = 0 — giá trị 0 "nuốt" mọi kết quả thực. Mọi range min query đều trả về 0 bất kể dữ liệu. Lỗi này không crash, chỉ cho kết quả sai — rất khó phát hiện bằng test nhỏ.

python

# ĐÚNG: dùng identity phù hợp với phép toán
def query_min(node, start, end, L, R):
    if R < start or end < L:
        return float('inf')

❌ Sai lầm 3: Quên push down lazy trước khi query

Vấn đề: Range update với lazy propagation nhưng quên gọi push_down trong hàm query.

Tại sao sai: Node con vẫn mang giá trị cũ vì lazy chưa lan xuống. Query trả về kết quả outdated. Lỗi khó phát hiện trong test nhỏ, bùng nổ khi dữ liệu lớn vì xác suất query trúng node "bẩn" tăng.

cpp

// ĐÚNG: luôn push_down trước khi đệ quy vào con
long long queryLazy(int node, int start, int end, int L, int R) {
    if (R < start || end < L) return 0;
    if (L <= start && end <= R) return tree[node];
    pushDown(node, start, end);  // BẮT BUỘC
    int mid = (start + end) / 2;
    return queryLazy(2*node, start, mid, L, R)
         + queryLazy(2*node+1, mid+1, end, L, R);
}

❌ Sai lầm 4: Trộn convention index 0-based và 1-based

Vấn đề: Gốc ở index 0 thì con trái = 2*i + 1, con phải = 2*i + 2. Gốc ở index 1 thì con trái = 2*i, con phải = 2*i + 1. Trộn lẫn hai convention dẫn đến truy cập sai node.

Tại sao sai: Code "gần đúng" — chạy đúng với test nhỏ, sai với test lớn do truy cập chéo vùng nhớ. Chọn 1-based (phổ biến nhất) và giữ nhất quán xuyên suốt.

Under the Hood

Hiệu năng

Thao tác	Time	Space	Ghi chú
Build	O(n)	O(n)	Mỗi node tính đúng 1 lần
Query	O(log n)	O(log n) stack	Tối đa 4⌈log₂ n⌉ node được thăm
Point Update	O(log n)	O(log n) stack	Đúng 1 đường từ lá đến gốc
Range Update (lazy)	O(log n) amortized	O(n) cho lazy array	Push down chỉ khi cần

Nội bộ triển khai

Biểu diễn mảng phẳng: Node i có con trái 2i, con phải 2i+1, cha i/2. Bitwise shift: 2*i = i << 1, 2*i+1 = i << 1 | 1. Cache-friendly hơn pointer-based tree vì dữ liệu nằm liền kề trong bộ nhớ.

Tại sao cần 4n? Chiều cao h = ⌈log₂ n⌉. Số node tối đa = 2^(h+1) − 1. Khi n không phải lũy thừa 2, con số này vượt 2n. Cấp phát 4n đảm bảo an toàn cho mọi giá trị n mà không cần tính chính xác.

Lazy propagation — phân tích amortized: Mỗi node chỉ push down khi bị truy cập. Một range update chạm O(log n) node, mỗi push down O(1). Q thao tác tổng cộng O(Q log n). Chi phí bộ nhớ: thêm mảng lazy cùng kích thước mảng tree.

Trade-offs

Tiêu chí	Segment Tree	Fenwick Tree	Sparse Table
Linh hoạt phép toán	Mọi associative op	Chỉ invertible op	Mọi idempotent op
Range update	✅ (lazy)	⚠️ hạn chế	❌
Bộ nhớ	4n	n	n log n
Hằng số thời gian	Lớn hơn	Nhỏ hơn	Nhỏ nhất
Độ phức tạp code	Cao	Thấp	Trung bình

Segment Tree là lựa chọn mặc định khi cần cả query lẫn update trên đoạn. Chỉ cần prefix sum + point update thì Fenwick Tree gọn hơn. Dữ liệu tĩnh thì Sparse Table cho query O(1).

Checklist ghi nhớ

✅ Checklist triển khai

Khởi tạo

[ ] Cấp phát mảng tree kích thước 4n, không phải 2n
[ ] Chọn convention index (0-based hay 1-based) và giữ nhất quán
[ ] Xác định phần tử đơn vị đúng cho phép toán (0 cho sum, ∞ cho min, −∞ cho max)

Query & Update

[ ] Kiểm tra ba trường hợp: ngoài hoàn toàn, trong hoàn toàn, giao nhau
[ ] Validate input L, R trước khi gọi query
[ ] Point update cập nhật ngược từ lá lên gốc

Lazy Propagation

[ ] Luôn push_down trước khi đệ quy vào node con — cả query lẫn update
[ ] Mảng lazy khởi tạo = 0 (hoặc giá trị "không thay đổi")
[ ] Range update: node value += val × (end − start + 1) cho sum

Production

[ ] Test với n = 1 (edge case nhỏ nhất)
[ ] Test với n không phải lũy thừa 2
[ ] Kiểm tra overflow: tổng n phần tử có thể vượt int32

Bài tập luyện tập

Bài 1: Range Sum cơ bản — Intermediate

Đề bài: Cho mảng n phần tử và q query. Mỗi query:

1 i val: gán a[i] = val
2 L R: in ra tổng a[L..R]

Ràng buộc: 1 ≤ n, q ≤ 10⁵, |a[i]| ≤ 10⁹.

🧠 Quiz

Câu hỏi: Với mảng [2, 4, 6, 8, 10], sau update(2, 1), giá trị query(1, 3) là bao nhiêu?

[ ] A. 18
[x] B. 13
[ ] C. 12
[ ] D. 15 Giải thích: Mảng sau update: [2, 4, 1, 8, 10]. Tổng [1..3] = 4 + 1 + 8 = 13. Đáp án A (18) là tổng trước update.

💡 Gợi ý

Build Segment Tree chuẩn với sum operation.
Nếu bài cho 1-indexed, chuyển về 0-indexed trước khi gọi tree.

✅ Lời giải

python

import sys
input = sys.stdin.readline

def solve():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    tree = [0] * (4 * n)

    def build(nd, s, e):
        if s == e:
            tree[nd] = a[s]; return
        mid = (s + e) // 2
        build(2*nd, s, mid); build(2*nd+1, mid+1, e)
        tree[nd] = tree[2*nd] + tree[2*nd+1]

    def update(nd, s, e, idx, val):
        if s == e:
            tree[nd] = val; return
        mid = (s + e) // 2
        if idx <= mid: update(2*nd, s, mid, idx, val)
        else: update(2*nd+1, mid+1, e, idx, val)
        tree[nd] = tree[2*nd] + tree[2*nd+1]

    def query(nd, s, e, L, R):
        if R < s or e < L: return 0
        if L <= s and e <= R: return tree[nd]
        mid = (s + e) // 2
        return query(2*nd, s, mid, L, R) + query(2*nd+1, mid+1, e, L, R)

    build(1, 0, n - 1)
    out = []
    for _ in range(q):
        t, x, y = map(int, input().split())
        if t == 1: update(1, 0, n-1, x, y)
        else: out.append(str(query(1, 0, n-1, x, y)))
    print('\n'.join(out))

Phân tích: Time O((n + q) log n), Space O(n).

Bài 2: Range Min với Lazy Update — Advanced

Đề bài: Cho mảng n phần tử và q query:

1 L R val: cộng val vào mọi phần tử trong [L, R]
2 L R: in ra min của [L, R]

Ràng buộc: 1 ≤ n, q ≤ 10⁵.

💡 Gợi ý

Segment Tree + lazy propagation.
Identity cho min: INT_MAX hoặc 10^18.
Push down cập nhật cả min value lẫn lazy value của node con.

✅ Lời giải

cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const long long INF = 1e18;
long long tree[4*MAXN], lazy[4*MAXN];

void build(int nd, int s, int e, int a[]) {
    lazy[nd] = 0;
    if (s == e) { tree[nd] = a[s]; return; }
    int mid = (s + e) / 2;
    build(2*nd, s, mid, a);
    build(2*nd+1, mid+1, e, a);
    tree[nd] = min(tree[2*nd], tree[2*nd+1]);
}

void pushDown(int nd) {
    if (lazy[nd]) {
        for (int c : {2*nd, 2*nd+1}) {
            tree[c] += lazy[nd];
            lazy[c] += lazy[nd];
        }
        lazy[nd] = 0;
    }
}

void rangeAdd(int nd, int s, int e, int L, int R, long long val) {
    if (R < s || e < L) return;
    if (L <= s && e <= R) { tree[nd] += val; lazy[nd] += val; return; }
    pushDown(nd);
    int mid = (s + e) / 2;
    rangeAdd(2*nd, s, mid, L, R, val);
    rangeAdd(2*nd+1, mid+1, e, L, R, val);
    tree[nd] = min(tree[2*nd], tree[2*nd+1]);
}

long long queryMin(int nd, int s, int e, int L, int R) {
    if (R < s || e < L) return INF;
    if (L <= s && e <= R) return tree[nd];
    pushDown(nd);
    int mid = (s + e) / 2;
    return min(queryMin(2*nd, s, mid, L, R),
               queryMin(2*nd+1, mid+1, e, L, R));
}

Phân tích: Time O(q log n), Space O(n). Lazy cho phép range update O(log n) amortized.

Liên kết học tiếp

Từ khóa glossary: Segment Tree, cây đoạn, range query, lazy propagation, point update, range update, identity element

Tìm kiếm liên quan: cây phân đoạn, truy vấn đoạn, cập nhật lười, interval tree

Segment Tree — Vua truy vấn đoạn ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Cấu trúc dữ liệu ​

Build — O(n) ​

Range Query — O(log n) ​

Point Update — O(log n) ​

Lazy Propagation — Range Update O(log n) ​

Bảng phép toán hỗ trợ ​

Thực chiến ​

Tình huống: Hệ thống giám sát lưu lượng mạng ​

Sai lầm điển hình ​

❌ Sai lầm 1: Cấp phát mảng tree kích thước 2n thay vì 4n ​

❌ Sai lầm 2: Nhầm phần tử đơn vị (identity element) ​

❌ Sai lầm 3: Quên push down lazy trước khi query ​

❌ Sai lầm 4: Trộn convention index 0-based và 1-based ​

Under the Hood ​

Hiệu năng ​

Nội bộ triển khai ​

Trade-offs ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Range Sum cơ bản — Intermediate ​

Bài 2: Range Min với Lazy Update — Advanced ​

Liên kết học tiếp ​

Segment Tree — Vua truy vấn đoạn

Bức tranh tư duy

Cốt lõi kỹ thuật

Cấu trúc dữ liệu

Build — O(n)

Range Query — O(log n)

Point Update — O(log n)

Lazy Propagation — Range Update O(log n)

Bảng phép toán hỗ trợ

Thực chiến

Tình huống: Hệ thống giám sát lưu lượng mạng

Sai lầm điển hình

❌ Sai lầm 1: Cấp phát mảng tree kích thước 2n thay vì 4n

❌ Sai lầm 2: Nhầm phần tử đơn vị (identity element)

❌ Sai lầm 3: Quên push down lazy trước khi query

❌ Sai lầm 4: Trộn convention index 0-based và 1-based

Under the Hood

Hiệu năng

Nội bộ triển khai

Trade-offs

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Range Sum cơ bản — Intermediate

Bài 2: Range Min với Lazy Update — Advanced

Liên kết học tiếp