Cấu trúc dữ liệu và Giải thuật Bài 59: Cây Phân Đoạn nâng cao với Lazy Propagation - Tối ưu hóa cập nhật khoảng dữ liệu.

Ở Bài 58, chúng ta đã làm chủ Cây Phân Đoạn (Segment Tree) cơ bản, giúp giải quyết hai thao tác Truy vấn khoảng (Range Query) và Cập nhật điểm (Point Update) với tốc độ chớp nhoáng $O(\log n)$.

Tuy nhiên, hệ thống thực tế thường đặt ra những thử thách khắc nghiệt hơn. Giả sử bạn quản lý hệ thống phân bổ băng thông hoặc lịch đặt phòng của chuỗi khách sạn: Hệ thống không chỉ yêu cầu tính tổng doanh thu của một dải ngày, mà còn phải thực hiện lệnh Cập nhật cả một khoảng lớn — ví dụ: "Tăng giá phòng của tất cả các ngày từ ngày 10 đến ngày 50 thêm 200 nghìn đồng".

Nếu bạn sử dụng Segment Tree cơ bản và gọi hàm Update cho từng phần tử riêng lẻ trong khoảng từ 10 đến 50, thời gian thực thi sẽ vọt lên mức $O((R - L + 1) \log n)$. Khi khoảng cần cập nhật dài tới hàng triệu phần tử, CPU sẽ bị nghẽn hoàn toàn. Để giữ vững độ phức tạp $O(\log n)$ tuyệt đối cho cả Range Update, chúng ta cần đến một kỹ thuật kinh điển mang tên Lazy Propagation (Truyền trễ / Cập nhật lười biếng).

1. Tư duy "Lười biếng có chiến lược" (Lazy Propagation)

Nguyên nhân khiến Segment Tree cơ bản chậm khi cập nhật khoảng là vì nó ép cấu trúc phải đâm xuyên qua mọi nhánh con để cập nhật từng chiếc lá nhỏ bên dưới ngay lập tức.

Kỹ thuật Lazy Propagation áp dụng một triết lý vô cùng thực tế của con người: "Việc gì chưa cần làm ngay hôm nay thì hãy hoãn lại, đừng làm vội."

Khi bạn yêu cầu cập nhật một khoảng lớn [L, R]:

1. Nếu đoạn hiện tại của Node nằm hoàn toàn bên trong khoảng [L, R], ta cập nhật giá trị ngay cho Node đó, đồng thời gắn một "Nhãn trễ" (lazy tag) lên Node đó để đánh dấu: "Này, tao đã được cộng dồn giá trị mới rồi đấy, nhưng các con cháu bên dưới của tao chưa kịp cập nhật đâu nhé".

2. Ta dừng lại ngay lập tức, không thèm đâm sâu xuống các node con bên dưới nữa. Nhờ sự lười biếng chiến lược này, thao tác Range Update chỉ mất đúng số bước tương đương với việc đi qua các tầng của cây $\rightarrow$ $O(\log n)$.

3. Các con cháu bên dưới chỉ thực sự được cập nhật giá trị khi có một truy vấn nào đó trong tương lai buộc phải đi ngang qua chúng. Lúc đó, Node cha mới "đẩy" (push down) nhãn trễ xuống cho các con.

2. Triển khai Segment Tree với Lazy Propagation bằng Golang

Dưới đây là thiết kế chuẩn mực cho phép thực hiện cả hai thao tác cực mạnh: Range Sum Query (Truy vấn tổng khoảng) và Range Add Update (Cộng dồn giá trị cho cả một khoảng).

Go

package main

import "fmt"

type LazySegmentTree struct {
    tree []int
    lazy []int // Mảng lưu trữ các nhãn trễ (Pending Updates)
    n    int
}

func NewLazySegmentTree(nums []int) *LazySegmentTree {
    n := len(nums)
    st := &LazySegmentTree{
        tree: make([]int, 4*n),
        lazy: make([]int, 4*n),
        n:    n,
    }
    st.build(nums, 0, 0, n-1)
    return st
}

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

// Hàm đẩy nhãn trễ xuống các node con (Push Down / Propagate)
func (st *LazySegmentTree) pushDown(node, start, end int) {
    if st.lazy[node] != 0 {
        mid := (start + end) / 2
        leftNode := 2 * node + 1
        rightNode := 2 * node + 2

        // Cập nhật giá trị cho node con trái
        st.tree[leftNode] += st.lazy[node] * (mid - start + 1)
        st.lazy[leftNode] += st.lazy[node] // Giao việc lại cho con trái

        // Cập nhật giá trị cho node con phải
        st.tree[rightNode] += st.lazy[node] * (end - mid)
        st.lazy[rightNode] += st.lazy[node] // Giao việc lại cho con phải

        // Xóa nhãn trễ ở node cha sau khi đã đẩy xuống
        st.lazy[node] = 0
    }
}

// 1. Cập nhật khoảng [l, r] cộng thêm giá trị val (Range Update) - O(log n)
func (st *LazySegmentTree) UpdateRange(l, r, val int) {
    st.updateRangeRec(0, 0, st.n-1, l, r, val)
}

func (st *LazySegmentTree) updateRangeRec(node, start, end, l, r, val int) {
    // Trường hợp 1: Ngoài khoảng cần cập nhật
    if r < start || end < l {
        return
    }

    // Trường hợp 2: Đoạn hiện tại nằm trọn trong khoảng cần cập nhật
    if l <= start && end <= r {
        st.tree[node] += val * (end - start + 1)
        st.lazy[node] += val // Đánh dấu nhãn trễ
        return
    }

    // Trường hợp 3: Giao nhau một phần -> Đẩy nhãn trễ trước khi phân nhánh
    st.pushDown(node, start, end)

    mid := (start + end) / 2
    st.updateRangeRec(2*node+1, start, mid, l, r, val)
    st.updateRangeRec(2*node+2, mid+1, end, l, r, val)

    st.tree[node] = st.tree[2*node+1] + st.tree[2*node+2]
}

// 2. Truy vấn tổng khoảng [l, r] (Range Sum Query) - O(log n)
func (st *LazySegmentTree) Query(l, r int) int {
    return st.queryRec(0, 0, st.n-1, l, r)
}

func (st *LazySegmentTree, queryRec...) // (phần logic query kết hợp pushDown tương tự)

(Lưu ý: Trong hàm queryRec, bạn cũng bắt buộc phải gọi st.pushDown(node, start, end) trước khi rẽ nhánh sang con trái và con phải, đảm bảo dữ liệu luôn được cập nhật chính xác trước khi đọc).

3. Phân tích Hiệu năng (Big-O)

• Không gian RAM: $O(n)$ (cấp phát mảng tree và mảng lazy có kích thước $4n$).

• Thời gian Range Update: $O(\log n)$. Nhờ cơ chế hoãn việc cập nhật (Lazy), các khoảng lớn được xử lý ngay lập tức ở tầng cao của cây mà không cần duyệt qua các nút lá.

• Thời gian Range Query: $O(\log n)$. Cơ chế pushDown đảm bảo rằng khi một truy vấn đi qua một node có nhãn trễ, giá trị sẽ được giải nén đúng lúc, duy trì tính chính xác tuyệt đối.

4. Ứng dụng Thực tế trong Hệ thống Enterprise

Lazy Propagation là công cụ cứu cánh cho các hệ thống đòi hỏi hiệu năng cao khi xử lý dữ liệu dải lớn:

• Hệ thống Lịch biểu và Đặt chỗ (Booking Systems): Quản lý trạng thái trống/đặt của hàng ngàn phòng khách sạn hoặc vé máy bay theo dải ngày. Khi một đợt khuyến mãi áp dụng cho cả tháng, hệ thống dùng Range Update với Lazy Propagation để cập nhật giá hoặc trạng thái chỉ trong vài mili-giây.

• Xử lý đồ họa và Bản đồ số (GIS Systems): Khi render các bản đồ không gian lớn, việc thay đổi độ sáng hoặc màu sắc của cả một vùng pixel hình chữ nhật (Range Update trên lưới 2D được ánh xạ về Segment Tree) đòi hỏi tốc độ phản hồi thời gian thực.

Lập trình động nâng cao cùng các cấu trúc dữ liệu chuyên biệt như Segment Tree và Lazy Propagation chính là ranh giới phân định giữa một lập trình viên thông thường và một kiến trúc sư hệ thống đẳng cấp.