Khóa học CTDL và GT

Bài 30.3. Lazy Propagation trên Segment Tree

Chào mừng các bạn quay trở lại với chuỗi bài về Cấu trúc dữ liệu và Giải thuật!

Ở các bài trước, chúng ta đã tìm hiểu về Segment Tree - một cấu trúc dữ liệu mạnh mẽ cho phép thực hiện các phép truy vấn trên đoạn (range queries) và cập nhật điểm (point updates) trên một mảng trong thời gian O(log N). Tuy nhiên, một vấn đề phát sinh khi chúng ta cần thực hiện các phép cập nhật trên đoạn (range updates) một cách hiệu quả. Nếu áp dụng phương pháp "ngây thơ" (naive approach) bằng cách cập nhật từng phần tử trong đoạn, độ phức tạp của một phép cập nhật đoạn có thể lên tới O(N), hoặc O(N log N) nếu cập nhật từng điểm trong đoạn bằng Segment Tree cơ bản.

Lúc này, Lazy Propagation (Lan truyền lười biếng) xuất hiện như một vị cứu tinh, giúp chúng ta thực hiện các phép cập nhật trên đoạn cũng chỉ trong O(log N).

Vấn Đề Với Cập Nhật Đoạn "Ngây Thơ"

Hãy hình dung bạn có một mảng và cần thực hiện phép cộng một giá trị X cho tất cả các phần tử trong đoạn từ chỉ số L đến R.

Với một Segment Tree cơ bản, mỗi nút lưu trữ thông tin tổng (hoặc min, max,...) của đoạn mà nó đại diện. Để cập nhật tất cả phần tử trong [L, R] bằng cách cộng X, bạn có thể làm như sau:

1. Duyệt qua từng chỉ số i từ L đến R.
2. Với mỗi i, thực hiện một phép cập nhật điểm (point update) tại chỉ số i với giá trị X.

Một phép cập nhật điểm trên Segment Tree mất O(log N). Nếu đoạn [L, R] có kích thước k, tổng cộng bạn sẽ mất O(k log N) cho một lần cập nhật đoạn. Trong trường hợp xấu nhất, k có thể gần bằng N, dẫn đến độ phức tạp O(N log N), rõ ràng là không hiệu quả cho các bài toán yêu cầu nhiều truy vấn cập nhật đoạn.

Làm thế nào để giải quyết vấn đề này? Lazy Propagation cung cấp một ý tưởng thiên tài: hoãn việc cập nhật xuống các nút con cho đến khi thực sự cần thiết!

Lazy Propagation: Ý Tưởng Cốt Lõi

Thay vì ngay lập tức đi sâu vào cây để cập nhật tất cả các lá hoặc các nút con bị ảnh hưởng bởi phép cập nhật đoạn, chúng ta sẽ:

1. Áp dụng phép cập nhật cho nút hiện tại nếu đoạn mà nút đó đại diện nằm hoàn toàn trong đoạn cập nhật [L, R].
2. Đánh dấu (mark) nút này, ghi nhớ rằng nó có một phép cập nhật "đang chờ xử lý" (pending) cần được truyền xuống các con của nó sau này. Đây chính là phần "Lazy" - lười biếng, trì hoãn việc lan truyền.
3. Khi một phép truy vấn hoặc một phép cập nhật khác cần đi xuống các nút con của nút đã được đánh dấu, chúng ta mới thực hiện việc "đẩy" (push) phép cập nhật đang chờ xử lý đó xuống các con trước khi tiếp tục.

Để làm được điều này, chúng ta cần thêm một mảng phụ (thường gọi là mảng lazy) hoặc thêm một trường vào cấu trúc nút của Segment Tree. Mỗi phần tử lazy[v] sẽ lưu trữ thông tin về phép cập nhật đang chờ xử lý tại nút v. Giá trị cụ thể của lazy[v] phụ thuộc vào loại phép cập nhật (cộng, gán, nhân, v.v.).

Cơ Chế Hoạt Động Chi Tiết: Hàm push

Trọng tâm của Lazy Propagation chính là hàm push(v, tl, tr) (hoặc tên tương tự). Hàm này có nhiệm vụ đẩy thông tin cập nhật đang chờ xử lý từ nút v xuống hai nút con của nó.

Giả sử nút v đại diện cho đoạn [tl, tr] và nó có một giá trị lazy[v] khác 0 (hoặc giá trị đặc biệt nào đó biểu thị có cập nhật chờ xử lý). Hàm push sẽ làm những việc sau:

1. Áp dụng lazy[v] cho nút hiện tại v: Cập nhật giá trị trong tree[v] dựa trên lazy[v] và đoạn [tl, tr] mà nút v đại diện. Ví dụ, nếu lazy[v] là giá trị cần cộng cho mỗi phần tử trong đoạn, thì tổng của đoạn [tl, tr] sẽ tăng thêm lazy[v] * (tr - tl + 1).
2. Nếu v không phải là nút lá (leaf node):
   • Thêm giá trị lazy[v] vào lazy[2*v] (con trái) và lazy[2*v+1] (con phải). Điều này có nghĩa là các nút con cũng thừa hưởng phép cập nhật đang chờ xử lý này. Lưu ý: Cách kết hợp giá trị lazy (ví dụ: cộng dồn hay gán đè) phụ thuộc vào loại phép cập nhật.
3. Xóa giá trị lazy[v]: Đặt lại lazy[v] về giá trị mặc định (thường là 0 hoặc giá trị đặc biệt biểu thị không có cập nhật chờ xử lý) sau khi đã đẩy nó xuống các con.

Hàm push này sẽ được gọi ở đầu hàm updateRange và queryRange trước khi đệ quy xuống các nút con, đảm bảo rằng thông tin cập nhật luôn được truyền xuống kịp thời khi cần truy cập các nút sâu hơn.

Cài Đặt Lazy Propagation: Ví dụ 1 - Cập nhật Cộng và Truy vấn Tổng

Đây là ví dụ phổ biến nhất và tương đối dễ hiểu. Chúng ta sẽ có một mảng, cần hỗ trợ hai thao tác:

1. Cộng một giá trị add_val vào tất cả các phần tử trong đoạn [L, R].
2. Truy vấn tổng của tất cả các phần tử trong đoạn [L, R].

Mảng tree sẽ lưu tổng của đoạn tương ứng. Mảng lazy sẽ lưu giá trị cần cộng thêm cho mỗi phần tử trong đoạn tương ứng của nút, đang chờ được đẩy xuống.

#include <iostream>
#include <vector>

const int INF = 1e9; // Dùng cho ví dụ min/max, không dùng ở ví dụ này

int arr[100005]; // Mảng ban đầu
long long tree[4 * 100005]; // Mảng Segment Tree, lưu tổng
long long lazy[4 * 100005]; // Mảng Lazy, lưu giá trị cần cộng thêm

// Hàm build: Xây dựng Segment Tree ban đầu
// v: chỉ số nút hiện tại trong mảng tree và lazy
// tl, tr: đoạn mà nút v đại diện trong mảng ban đầu arr
void build(int v, int tl, int tr) {
    lazy[v] = 0; // Ban đầu không có cập nhật nào chờ xử lý
    if (tl == tr) {
        tree[v] = arr[tl]; // Nút lá, lưu giá trị của phần tử mảng
    } else {
        int tm = (tl + tr) / 2; // Trung điểm
        build(2 * v, tl, tm); // Xây dựng cây con trái
        build(2 * v + 1, tm + 1, tr); // Xây dựng cây con phải
        tree[v] = tree[2 * v] + tree[2 * v + 1]; // Nút cha lưu tổng của hai nút con
    }
}

// Hàm push: Đẩy thông tin lazy từ nút v xuống con
// v: chỉ số nút hiện tại
// tl, tr: đoạn mà nút v đại diện
void push(int v, int tl, int tr) {
    if (lazy[v] != 0) { // Chỉ xử lý nếu có cập nhật lazy chờ xử lý
        // Áp dụng lazy[v] cho nút hiện tại tree[v]
        // tree[v] lưu tổng, nên cần cộng lazy[v] * kích thước đoạn
        tree[v] += lazy[v] * (tr - tl + 1);

        // Nếu không phải nút lá, đẩy lazy xuống con
        if (tl != tr) {
            lazy[2 * v] += lazy[v]; // Con trái nhận lazy
            lazy[2 * v + 1] += lazy[v]; // Con phải nhận lazy
        }

        // Xóa lazy ở nút hiện tại sau khi đã đẩy xuống
        lazy[v] = 0;
    }
}

// Hàm updateRange: Cập nhật cộng add_val cho đoạn [l, r]
// v: chỉ số nút hiện tại
// tl, tr: đoạn mà nút v đại diện
// l, r: đoạn cần cập nhật
// add_val: giá trị cần cộng
void updateRange(int v, int tl, int tr, int l, int r, int add_val) {
    // Bước 1: Đẩy thông tin lazy trước khi xử lý nút v
    push(v, tl, tr);

    // Bước 2: Kiểm tra mối quan hệ giữa đoạn của nút v [tl, tr] và đoạn cần cập nhật [l, r]
    if (l > r) { // Đoạn cập nhật không hợp lệ hoặc đã xử lý xong
        return;
    }
    if (l == tl && r == tr) { // Đoạn của nút v nằm hoàn toàn trong đoạn cập nhật
        // Áp dụng add_val cho nút v
        tree[v] += (long long)add_val * (tr - tl + 1);
        // Ghi nhận add_val vào lazy của nút v để đẩy xuống sau
        // Chỉ đẩy nếu không phải nút lá, vì nút lá không có con để đẩy
        if (tl != tr) {
            lazy[2 * v] += add_val;
            lazy[2 * v + 1] += add_val;
        }
        // Tại đây lazy[v] đã được đẩy xuống ở push(v, tl, tr) nên không cần set lazy[v]=add_val nữa.
        // Tuy nhiên, logic chuẩn hơn là: Nếu FULL OVERLAP -> apply lazy[v] = add_val VÀO BẢN THÂN NÓ, KHÔNG CẦN ĐẨY XUỐNG NGAY LẬP TỨC. Push sẽ lo việc đẩy.
        // Sửa lại logic cho chuẩn:
        // tree[v] += (long long)add_val * (tr - tl + 1); // Áp dụng ngay cho nút hiện tại
        // if (tl != tr) { lazy[2*v] += add_val; lazy[2*v+1] += add_val; } // Đẩy xuống con
        // Đây là cách hiểu SAI về lazy propagation.
        // CÁCH HIỂU ĐÚNG: Khi full overlap, ta CHỈ cập nhật tree[v] dựa vào add_val *và* lazy[v] HIỆN TẠI. Sau đó, ta cập nhật lazy[v] = lazy[v] + add_val MỚI. Push sẽ lo việc áp dụng lazy[v] này LẦN SAU.

        // Logic chuẩn hơn khi full overlap:
        tree[v] += (long long)add_val * (tr - tl + 1); // Cập nhật giá trị của nút V dựa trên add_val
        if (tl != tr) { // Nếu không phải nút lá
             lazy[2 * v] += add_val; // Thêm add_val vào lazy của con trái
             lazy[2 * v + 1] += add_val; // Thêm add_val vào lazy của con phải
        }
        // IMPORTANT: lazy[v] for node v is NOT reset here.
        // It was used in push(v, tl, tr) at the beginning of the function call.
        // The new add_val is applied to children's lazy array.
        // This means the lazy value on a node accumulates updates.
        // This logic is correct for range ADDITION.

        // Correct logic re-revisited:
        // When full overlap [tl, tr] <= [l, r]:
        // Apply the current lazy[v] (if any) to tree[v] and propagate to children's lazy.
        // THEN apply the *new* add_val to tree[v] and add to children's lazy.
        // The initial push(v, tl, tr) at the top handles the *existing* lazy[v].
        // After push, lazy[v] is 0. Now we apply the *new* add_val.
        // So the correct step for full overlap *after* push is:
        tree[v] += (long long)add_val * (tr - tl + 1); // Apply new add_val to current node's value
        if (tl != tr) { // If not a leaf
             lazy[2 * v] += add_val; // Add new add_val to children's lazy
             lazy[2 * v + 1] += add_val;
        }
        // Lazy[v] is now 0 due to the push at the start. This is correct.
        // We just update the value and propagate the NEW lazy to children.
        return; // Đã xử lý xong đoạn này
    }

    // Bước 3: Xử lý trường hợp partial overlap (đoạn cần cập nhật chỉ giao một phần với đoạn của nút v)
    int tm = (tl + tr) / 2;
    // Đệ quy xuống cây con trái
    updateRange(2 * v, tl, tm, l, std::min(r, tm), add_val);
    // Đệ quy xuống cây con phải
    updateRange(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r, add_val);

    // Bước 4: Cập nhật lại giá trị của nút v sau khi các con đã được (hoặc sẽ được) cập nhật
    // Giá trị của nút cha là tổng của các con
    tree[v] = tree[2 * v] + tree[2 * v + 1];
    // Lưu ý: Sau khi đệ quy, các nút con có thể vẫn còn lazy values.
    // Khi chúng ta truy vấn hoặc update đi qua các con đó, hàm push của chúng sẽ được gọi.
    // tree[v] chỉ cần là tổng giá trị HIỆN TẠI của các con (có thể chưa hoàn toàn chính xác nếu con còn lazy).
    // Nhưng nhờ push, giá trị này sẽ được sửa đúng khi ta đi xuống.
    // Tuy nhiên, trong ví dụ Range Add/Sum này, giá trị của nút cha sau khi các con được cập nhật *một phần*
    // sẽ là tổng các giá trị đã được áp dụng lazy ở các con (hoặc sẽ được áp dụng sau).
    // Tổng của các con SAU KHI recursive calls sẽ LÀ TỔNG ĐÚNG của đoạn [tl, tm] và [tm+1, tr] sau khi
    // phần cập nhật [l, r] được xử lý ở các con (bao gồm cả việc để lại lazy ở đó).
    // Vì vậy, tree[v] = tree[2*v] + tree[2*v+1] là đúng.
}

// Hàm queryRange: Truy vấn tổng của đoạn [l, r]
// v: chỉ số nút hiện tại
// tl, tr: đoạn mà nút v đại diện
// l, r: đoạn cần truy vấn
long long queryRange(int v, int tl, int tr, int l, int r) {
    // Bước 1: Đẩy thông tin lazy trước khi xử lý nút v
    push(v, tl, tr);

    // Bước 2: Kiểm tra mối quan hệ giữa đoạn của nút v [tl, tr] và đoạn cần truy vấn [l, r]
    if (l > r) { // Đoạn truy vấn không hợp lệ hoặc không giao nhau
        return 0; // Tổng của đoạn rỗng là 0
    }
    if (l == tl && r == tr) { // Đoạn của nút v nằm hoàn toàn trong đoạn truy vấn
        return tree[v]; // Trả về giá trị đã được cập nhật (nhờ push ở trên)
    }

    // Bước 3: Xử lý trường hợp partial overlap
    int tm = (tl + tr) / 2;
    // Đệ quy xuống cây con trái và cây con phải
    long long sum_left = queryRange(2 * v, tl, tm, l, std::min(r, tm));
    long long sum_right = queryRange(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r);

    // Bước 4: Kết hợp kết quả từ các cây con
    return sum_left + sum_right;
}

int main() {
    int n; // Kích thước mảng
    std::cout << "Nhap kich thuoc mang: ";
    std::cin >> n;

    std::cout << "Nhap cac phan tu mang: ";
    for (int i = 1; i <= n; ++i) { // Sử dụng chỉ số 1-based cho dễ làm quen với Segment Tree
        std::cin >> arr[i];
    }

    build(1, 1, n); // Xây dựng cây, bắt đầu từ nút gốc 1, đại diện cho đoạn [1, n]

    std::cout << "\nSegment Tree ban dau duoc xay dung.\n";

    // Ví dụ 1: Cập nhật và truy vấn
    int type;
    while (true) {
        std::cout << "\nChon thao tac:\n";
        std::cout << "1. Cap nhat cong tren doan [L, R] (add_val)\n";
        std::cout << "2. Truy van tong tren doan [L, R]\n";
        std::cout << "0. Thoat\n";
        std::cout << "Nhap lua chon: ";
        std::cin >> type;

        if (type == 0) break;

        int l, r;
        std::cout << "Nhap doan [L, R]: ";
        std::cin >> l >> r;

        if (l < 1 || r > n || l > r) {
            std::cout << "Doan khong hop le!\n";
            continue;
        }

        if (type == 1) {
            int add_val;
            std::cout << "Nhap gia tri can cong them: ";
            std::cin >> add_val;
            updateRange(1, 1, n, l, r, add_val);
            std::cout << "Da cap nhat cong " << add_val << " cho doan [" << l << ", " << r << "]\n";
        } else if (type == 2) {
            long long result = queryRange(1, 1, n, l, r);
            std::cout << "Tong tren doan [" << l << ", " << r << "] la: " << result << "\n";
        } else {
             std::cout << "Lua chon khong hop le!\n";
        }
    }


    return 0;
}

Giải thích Code (Ví dụ 1):

1. Mảng tree và lazy: tree lưu trữ kết quả tổng của đoạn (hoặc các thông tin khác tùy bài toán), lazy lưu trữ giá trị cần cộng thêm cho mỗi phần tử trong đoạn đó. Kích thước 4*N là an toàn cho Segment Tree biểu diễn mảng N phần tử.
2. Hàm build: Giống như Segment Tree cơ bản, xây dựng cây từ mảng ban đầu. Khởi tạo lazy của tất cả các nút bằng 0.
3. Hàm push(v, tl, tr):
   • Kiểm tra if (lazy[v] != 0): Chỉ thực hiện lan truyền nếu có giá trị lazy đang chờ xử lý tại nút v.
   • tree[v] += lazy[v] * (tr - tl + 1): Áp dụng giá trị lazy[v] cho nút v. Vì lazy[v] là giá trị cần cộng cho mỗi phần tử trong đoạn [tl, tr], tổng của đoạn này sẽ tăng thêm lazy[v] * (tr - tl + 1).
   • if (tl != tr): Nếu không phải nút lá, đẩy giá trị lazy xuống hai con. lazy[2*v] += lazy[v] và lazy[2*v+1] += lazy[v]. Giá trị lazy của con được cộng dồn thêm giá trị lazy của cha.
   • lazy[v] = 0: Reset giá trị lazy của nút v sau khi đã áp dụng và đẩy xuống con.
4. Hàm updateRange(v, tl, tr, l, r, add_val):
   • push(v, tl, tr): Rất quan trọng! Luôn gọi push ở đầu hàm để đảm bảo nút hiện tại v đã xử lý xong các lazy update từ các nút cha trước đó trước khi xem xét áp dụng cập nhật mới add_val.
   • Trường hợp không giao nhau (l > r): Dừng.
   • Trường hợp giao nhau hoàn toàn (l == tl && r == tr): Đoạn của nút v nằm trọn trong đoạn cần cập nhật.
     • Áp dụng add_val cho tree[v].
     • Thêm add_val vào lazy của hai con (nếu có). Chúng ta không đi sâu xuống nữa, chỉ cập nhật nút hiện tại và đánh dấu cho con. Việc push ở đầu hàm sau này sẽ lo việc áp dụng lazy đó khi cần.
   • Trường hợp giao nhau một phần:
     • Tìm trung điểm tm.
     • Đệ quy xuống cây con trái (updateRange(2*v, tl, tm, l, std::min(r, tm), add_val)). std::min(r, tm) đảm bảo chúng ta chỉ xử lý phần giao giữa [l, r] và [tl, tm].
     • Đệ quy xuống cây con phải (updateRange(2*v + 1, tm + 1, tr, std::max(l, tm + 1), r, add_val)). std::max(l, tm + 1) đảm bảo chúng ta chỉ xử lý phần giao giữa [l, r] và [tm+1, tr].
     • tree[v] = tree[2*v] + tree[2*v + 1]: Sau khi đệ quy, cập nhật lại giá trị của nút cha bằng tổng của hai con. Lưu ý rằng các giá trị của con có thể đã được (hoặc sẽ được) cập nhật nhờ lazy.
5. Hàm queryRange(v, tl, tr, l, r):
   • push(v, tl, tr): Rất quan trọng! Luôn gọi push ở đầu hàm để đảm bảo nút hiện tại v đã xử lý xong các lazy update từ các nút cha trước đó trước khi sử dụng giá trị tree[v] hoặc đi sâu xuống.
   • Trường hợp không giao nhau (l > r): Trả về giá trị identity element (0 cho phép tổng).
   • Trường hợp giao nhau hoàn toàn (l == tl && r == tr): Đoạn của nút v nằm trọn trong đoạn cần truy vấn. Trả về tree[v]. Giá trị này đã được đảm bảo là đúng nhờ push ở đầu hàm.
   • Trường hợp giao nhau một phần:
     • Tìm trung điểm tm.
     • Đệ quy xuống cây con trái và cây con phải.
     • Kết hợp kết quả (sum_left + sum_right).

Cài Đặt Lazy Propagation: Ví dụ 2 - Cập nhật Gán và Truy vấn Min

Ví dụ này phức tạp hơn một chút vì phép gán (assignment) có thể ghi đè lên các phép cập nhật trước đó. Chúng ta sẽ cần một cách đặc biệt để đánh dấu trạng thái lazy (ví dụ: sử dụng một giá trị đặc biệt cho biết không có cập nhật gán nào đang chờ).

Chúng ta sẽ hỗ trợ hai thao tác:

1. Gán một giá trị assign_val cho tất cả các phần tử trong đoạn [L, R].
2. Truy vấn giá trị nhỏ nhất (minimum) của tất cả các phần tử trong đoạn [L, R].

Mảng tree sẽ lưu giá trị nhỏ nhất của đoạn tương ứng. Mảng lazy sẽ lưu giá trị cần gán, nếu có. Chúng ta dùng giá trị -1 trong mảng lazy để biểu thị không có phép gán nào đang chờ xử lý cho nút đó (giả sử giá trị trong mảng ban đầu không bao giờ là -1, hoặc chọn một giá trị đặc biệt khác).

#include <iostream>
#include <vector>
#include <algorithm> // For std::min, std::max

const int INF = 1e9 + 7; // Sử dụng cho giá trị vô cực cho phép tìm min
const int NO_LAZY_ASSIGNMENT = -1; // Giá trị đặc biệt cho biết không có lazy assignment

int arr[100005]; // Mảng ban đầu
int tree_min[4 * 100005]; // Mảng Segment Tree, lưu min
int lazy_assign[4 * 100005]; // Mảng Lazy, lưu giá trị cần gán

// Hàm build: Xây dựng Segment Tree ban đầu
// v: chỉ số nút hiện tại
// tl, tr: đoạn mà nút v đại diện
void build_min(int v, int tl, int tr) {
    lazy_assign[v] = NO_LAZY_ASSIGNMENT; // Ban đầu không có lazy assignment
    if (tl == tr) {
        tree_min[v] = arr[tl]; // Nút lá, lưu giá trị
    } else {
        int tm = (tl + tr) / 2;
        build_min(2 * v, tl, tm);
        build_min(2 * v + 1, tm + 1, tr);
        tree_min[v] = std::min(tree_min[2 * v], tree_min[2 * v + 1]); // Nút cha lưu min của các con
    }
}

// Hàm push: Đẩy thông tin lazy assignment từ nút v xuống con
// v: chỉ số nút hiện tại
// tl, tr: đoạn mà nút v đại diện
void push_min(int v, int tl, int tr) {
    if (lazy_assign[v] != NO_LAZY_ASSIGNMENT) { // Nếu có lazy assignment chờ xử lý
        // Áp dụng lazy_assign[v] cho nút hiện tại tree_min[v]
        // tree_min[v] lưu min, nên gán tree_min[v] = lazy_assign[v]
        tree_min[v] = lazy_assign[v];

        // Nếu không phải nút lá, đẩy lazy_assign xuống con
        if (tl != tr) {
            lazy_assign[2 * v] = lazy_assign[v]; // Con trái nhận lazy assignment
            lazy_assign[2 * v + 1] = lazy_assign[v]; // Con phải nhận lazy assignment
        }

        // Xóa lazy_assign ở nút hiện tại sau khi đã đẩy xuống
        lazy_assign[v] = NO_LAZY_ASSIGNMENT;
    }
}

// Hàm updateRange_assign: Gán assign_val cho đoạn [l, r]
// v: chỉ số nút hiện tại
// tl, tr: đoạn mà nút v đại diện
// l, r: đoạn cần cập nhật
// assign_val: giá trị cần gán
void updateRange_assign(int v, int tl, int tr, int l, int r, int assign_val) {
    // Bước 1: Đẩy thông tin lazy assignment trước khi xử lý nút v
    push_min(v, tl, tr);

    // Bước 2: Kiểm tra mối quan hệ giữa đoạn của nút v [tl, tr] và đoạn cần cập nhật [l, r]
    if (l > r || tl > r || tr < l) { // Đoạn cập nhật không giao nhau
        return;
    }
    if (l <= tl && tr <= r) { // Đoạn của nút v nằm hoàn toàn trong đoạn cập nhật
        // Áp dụng assign_val cho nút v
        tree_min[v] = assign_val;
        // Ghi nhận assign_val vào lazy_assign của nút v để đẩy xuống sau
        // Chỉ ghi nhận lazy nếu không phải nút lá, vì nút lá không có con để đẩy
        if (tl != tr) {
            lazy_assign[2 * v] = assign_val;
            lazy_assign[2 * v + 1] = assign_val;
        }
        return; // Đã xử lý xong đoạn này
    }

    // Bước 3: Xử lý trường hợp partial overlap
    int tm = (tl + tr) / 2;
    // Đệ quy xuống cây con trái và cây con phải
    updateRange_assign(2 * v, tl, tm, l, r, assign_val); // Không cần min/max ranh giới ở đây nữa vì đã kiểm tra ở trên
    updateRange_assign(2 * v + 1, tm + 1, tr, l, r, assign_val);

    // Bước 4: Cập nhật lại giá trị min của nút v sau khi các con đã được (hoặc sẽ được) cập nhật
    tree_min[v] = std::min(tree_min[2 * v], tree_min[2 * v + 1]);
}

// Hàm queryRange_min: Truy vấn min của đoạn [l, r]
// v: chỉ số nút hiện tại
// tl, tr: đoạn mà nút v đại diện
// l, r: đoạn cần truy vấn
int queryRange_min(int v, int tl, int tr, int l, int r) {
    // Bước 1: Đẩy thông tin lazy assignment trước khi xử lý nút v
    push_min(v, tl, tr);

    // Bước 2: Kiểm tra mối quan hệ giữa đoạn của nút v [tl, tr] và đoạn cần truy vấn [l, r]
    if (l > r || tl > r || tr < l) { // Đoạn truy vấn không giao nhau
        return INF; // Giá trị vô cực cho min
    }
    if (l <= tl && tr <= r) { // Đoạn của nút v nằm hoàn toàn trong đoạn truy vấn
        return tree_min[v]; // Trả về giá trị min đã được cập nhật (nhờ push ở trên)
    }

    // Bước 3: Xử lý trường hợp partial overlap
    int tm = (tl + tr) / 2;
    // Đệ quy xuống cây con trái và cây con phải
    int min_left = queryRange_min(2 * v, tl, tm, l, r); // Không cần min/max ranh giới ở đây nữa vì đã kiểm tra ở trên
    int min_right = queryRange_min(2 * v + 1, tm + 1, tr, l, r);

    // Bước 4: Kết hợp kết quả từ các cây con
    return std::min(min_left, min_right);
}

int main() {
    int n; // Kích thước mảng
    std::cout << "Nhap kich thuoc mang: ";
    std::cin >> n;

    std::cout << "Nhap cac phan tu mang: ";
    for (int i = 1; i <= n; ++i) { // Sử dụng chỉ số 1-based cho dễ làm quen với Segment Tree
        std::cin >> arr[i];
    }

    build_min(1, 1, n); // Xây dựng cây cho min, bắt đầu từ nút gốc 1, đại diện cho đoạn [1, n]

    std::cout << "\nSegment Tree cho Min ban dau duoc xay dung.\n";

    // Ví dụ 2: Cập nhật gán và truy vấn min
    int type;
    while (true) {
        std::cout << "\nChon thao tac:\n";
        std::cout << "1. Cap nhat gan tren doan [L, R] (assign_val)\n";
        std::cout << "2. Truy van min tren doan [L, R]\n";
        std::cout << "0. Thoat\n";
        std::cout << "Nhap lua chon: ";
        std::cin >> type;

        if (type == 0) break;

        int l, r;
        std::cout << "Nhap doan [L, R]: ";
        std::cin >> l >> r;

        if (l < 1 || r > n || l > r) {
            std::cout << "Doan khong hop le!\n";
            continue;
        }

        if (type == 1) {
            int assign_val;
            std::cout << "Nhap gia tri can gan: ";
            std::cin >> assign_val;
            updateRange_assign(1, 1, n, l, r, assign_val);
            std::cout << "Da cap nhat gan " << assign_val << " cho doan [" << l << ", " << r << "]\n";
        } else if (type == 2) {
            int result = queryRange_min(1, 1, n, l, r);
            if (result == INF) {
                 std::cout << "Doan truy van khong hop le hoac rong.\n";
            } else {
                 std::cout << "Gia tri nho nhat tren doan [" << l << ", " << r << "] la: " << result << "\n";
            }
        } else {
             std::cout << "Lua chon khong hop le!\n";
        }
    }


    return 0;
}

Giải thích Code (Ví dụ 2 - Phép Gán):

1. Mảng tree_min và lazy_assign: tree_min lưu giá trị nhỏ nhất, lazy_assign lưu giá trị cần gán. NO_LAZY_ASSIGNMENT (-1) được dùng để đánh dấu không có phép gán chờ xử lý.
2. Hàm build_min: Tương tự, xây dựng cây cho min. Khởi tạo lazy_assign là NO_LAZY_ASSIGNMENT.
3. Hàm push_min(v, tl, tr):
   • Kiểm tra if (lazy_assign[v] != NO_LAZY_ASSIGNMENT): Chỉ xử lý nếu có lazy assignment.
   • tree_min[v] = lazy_assign[v]: Áp dụng phép gán cho nút hiện tại. Giá trị nhỏ nhất của đoạn trở thành giá trị gán.
   • if (tl != tr): Nếu không phải nút lá, gán giá trị lazy_assign[v] cho lazy_assign của hai con. Lưu ý sự khác biệt với phép cộng: lazy assignment ghi đè lazy assignment trước đó.
   • lazy_assign[v] = NO_LAZY_ASSIGNMENT: Reset lazy của nút v.
4. Hàm updateRange_assign(v, tl, tr, l, r, assign_val):
   • push_min(v, tl, tr): Luôn gọi push trước.
   • Trường hợp không giao nhau: Dừng.
   • Trường hợp giao nhau hoàn toàn:
     • Áp dụng assign_val cho tree_min[v].
     • Gán assign_val vào lazy_assign của hai con (nếu có).
     • Dừng, không đi sâu xuống.
   • Trường hợp giao nhau một phần:
     • Đệ quy xuống hai con.
     • Cập nhật lại tree_min[v] = std::min(tree_min[2*v], tree_min[2*v+1]).
5. Hàm queryRange_min(v, tl, tr, l, r):
   • push_min(v, tl, tr): Luôn gọi push trước.
   • Trường hợp không giao nhau: Trả về INF (identity element cho min).
   • Trường hợp giao nhau hoàn toàn: Trả về tree_min[v] (đã được làm đúng nhờ push).
   • Trường hợp giao nhau một phần: Đệ quy và kết hợp kết quả (min).

Phân Tích Độ Phức Tạp

Với Lazy Propagation, cả hai phép cập nhật đoạn và truy vấn đoạn đều có độ phức tạp O(log N).

• Hàm push: Mất thời gian hằng số O(1) (thực hiện vài phép tính và cập nhật cho nút hiện tại và hai con).
• Hàm updateRange và queryRange: Khi traversing cây, ở mỗi cấp độ, chúng ta chỉ đi xuống tối đa hai nhánh (trừ khi gặp trường hợp full overlap). Khi gặp full overlap, chúng ta dừng đệ quy và chỉ cập nhật nút hiện tại cùng lazy của các con (O(1) hoặc O(log N) để tìm đến nút đó + O(1) cho logic tại nút). Tổng số nút được duyệt và áp dụng push trên đường đi xuống (đến các nút giao nhau một phần hoặc bắt đầu/kết thúc đoạn) là O(log N). Số nút full overlap được xử lý trực tiếp (không đi sâu xuống) cũng nằm trên O(log N) đường đi. Do đó, tổng số thao tác trên mỗi lần gọi updateRange hoặc queryRange là O(log N) * O(1) (cho mỗi nút được xử lý) = O(log N).

Điều này mang lại hiệu quả vượt trội so với cách tiếp cận ngây thơ O(N) hoặc O(N log N) cho cập nhật đoạn.

Khi Nào Nên Sử Dụng Lazy Propagation?

Lazy Propagation phát huy sức mạnh khi bạn cần thực hiện nhiều phép cập nhật trên đoạn trên một mảng cố định, xen kẽ với các phép truy vấn trên đoạn.

Các bài toán điển hình bao gồm:

• Cập nhật cộng/trừ trên đoạn và truy vấn tổng/min/max trên đoạn.
• Cập nhật gán giá trị trên đoạn và truy vấn tổng/min/max trên đoạn.
• Các bài toán phức tạp hơn kết hợp nhiều loại cập nhật (ví dụ: vừa cộng vừa gán), lúc này logic trong hàm push và cách kết hợp giá trị lazy trở nên phức tạp hơn.

Bài tập ví dụ:

Ma Trận XOR

Trong một buổi dạo chơi ở quảng trường, FullHouse Dev bắt gặp một bài toán thú vị về ma trận. Họ được yêu cầu tìm ma trận vuông đẹp lớn nhất trong một ma trận cho trước, với điều kiện XOR của mọi cặp ô liền kề phải bằng \(1\).

Bài toán

Một ma trận vuông kích thước \(n\) được gọi là đẹp nếu phép XOR của mọi cặp ô liền kề bằng \(1\). Hai ô được coi là liền kề nếu chúng có chung cạnh. Với ô \((i,j)\), các ô \((i-1,j)\), \((i+1,j)\), \((i,j-1)\), và \((i,j+1)\) được coi là liền kề (nếu tồn tại trong ma trận).

Cho ma trận \(A\) kích thước \(n × n\), mỗi ô chứa giá trị \(0\) hoặc \(1\). Với \(Q\) truy vấn, mỗi truy vấn cho biết ô trái trên \((x_1,y_1)\) và ô phải dưới \((x_2,y_2)\) của một ma trận con, hãy tìm kích thước cạnh của ma trận vuông đẹp lớn nhất nằm trong ma trận con đó.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Dòng đầu của mỗi test case chứa một số nguyên \(n\) - kích thước ma trận
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên (0 hoặc 1) mô tả ma trận
• Dòng tiếp theo chứa số nguyên \(Q\) - số lượng truy vấn
• \(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\), \(y_2\)

OUTPUT FORMAT:

• Với mỗi truy vấn, in ra một dòng duy nhất là kích thước cạnh của ma trận vuông đẹp lớn nhất có thể tìm được

Ràng buộc:

• \(1 ≤ T ≤ 10\)
• \(1 ≤ n ≤ 1000\)
• \(1 ≤ Q ≤ 10^5\)
• \(1 ≤ x_1 ≤ x_2 ≤ n\)
• \(1 ≤ y_1 ≤ y_2 ≤ n\)

Ví dụ

INPUT

1
6
1 0 1 0 0 0
0 0 0 0 1 1
1 0 1 0 1 1
1 1 0 1 0 0
0 0 1 0 1 1
1 1 0 0 1 0
2
2 2 6 6
3 5 5 6

OUTPUT

3
1

Giải thích

• Ở truy vấn thứ nhất, ma trận vuông đẹp lớn nhất có kích thước 3×3
• Ở truy vấn thứ hai, ma trận vuông đẹp lớn nhất có kích thước 1×1 Tuyệt vời, đây là bài toán kết hợp nhiều kỹ thuật. Dưới đây là hướng giải ngắn gọn, tập trung vào các ý chính:

1. Phân tích điều kiện "Ma trận đẹp": Điều kiện XOR của mọi cặp ô liền kề bằng 1 (tức là giá trị khác nhau) tạo ra một mẫu ô xen kẽ. Một ma trận vuông con đẹp phải theo một trong hai mẫu bàn cờ vua (checkerboard pattern):

   • Mẫu 1: Ô (0,0) là 0, (0,1) là 1, (1,0) là 1, (1,1) là 0, v.v. (giá trị (i+j) % 2)
   • Mẫu 2: Ô (0,0) là 1, (0,1) là 0, (1,0) là 0, (1,1) là 1, v.v. (giá trị (i+j+1) % 2 hoặc 1 - ((i+j) % 2)) Một ma trận con A[r..r+k-1][c..c+k-1] là đẹp nếu tất cả các ô trong ma trận con đó khớp với một trong hai mẫu trên, bắt đầu từ vị trí tương ứng của nó trong ma trận lớn A.

2. Chuyển đổi bài toán:

   • Tạo hai ma trận nhị phân M1 và M2 cùng kích thước n x n.
   • M1[i][j] = 1 nếu A[i][j] khớp với mẫu 1 tại vị trí (i, j) của ma trận lớn (tức A[i][j] == ((i+j)%2)). Ngược lại M1[i][j] = 0.
   • M2[i][j] = 1 nếu A[i][j] khớp với mẫu 2 tại vị trí (i, j) của ma trận lớn (tức A[i][j] == (1 - ((i+j)%2))). Ngược lại M2[i][j] = 0.
   • Bây giờ, một ma trận con A[r..r+k-1][c..c+k-1] là đẹp nếu và chỉ nếu ma trận con M1[r..r+k-1][c..c+k-1] chỉ chứa toàn số 1 HOẶC ma trận con M2[r..r+k-1][c..c+k-1] chỉ chứa toàn số 1.

3. Bài toán phụ: Tìm ma trận vuông toàn 1 lớn nhất: Bài toán đã được chuyển thành: Với một ma trận nhị phân (M1 hoặc M2), tìm kích thước cạnh của ma trận vuông toàn 1 lớn nhất nằm trong một vùng truy vấn cho trước.

   • Đây là bài toán kinh điển. Ta có thể dùng Dynamic Programming để tính cho toàn bộ ma trận. Định nghĩa DP[i][j] là kích thước cạnh của ma trận vuông toàn 1 lớn nhất kết thúc ở ô (i, j).
   • Nếu M[i][j] == 0, thì DP[i][j] = 0.
   • Nếu M[i][j] == 1, thì DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1.
   • Áp dụng DP này cho cả M1 và M2 để thu được hai ma trận DP1 và DP2. Mỗi ô DP1[i][j] (hoặc DP2[i][j]) cho biết kích thước cạnh của ma trận vuông toàn 1 lớn nhất trong M1 (hoặc M2) kết thúc tại (i, j).

4. Xử lý truy vấn hiệu quả:

   • Đối với một truy vấn (x1, y1) đến (x2, y2) (chuyển sang 0-indexed là (r1, c1) đến (r2, c2)), ta cần tìm kích thước k lớn nhất sao cho tồn tại một vị trí (r, c) với r1 <= r, r+k-1 <= r2, c1 <= c, c+k-1 <= c2, và (M1[r..r+k-1][c..c+k-1] toàn 1) HOẶC (M2[r..r+k-1][c..c+k-1] toàn 1).
   • Điều kiện M[r..r+k-1][c..c+k-1] toàn 1 tương đương với việc ma trận vuông toàn 1 kích thước k x k kết thúc tại (r+k-1, c+k-1) trong ma trận M đó. Điều này xảy ra khi DP[r+k-1][c+k-1] >= k.
   • Vậy, ta cần tìm k lớn nhất sao cho tồn tại (i, j) với r1+k-1 <= i <= r2, c1+k-1 <= j <= c2, và (DP1[i][j] >= k HOẶC DP2[i][j] >= k).

5. Tối ưu hóa truy vấn với Binary Search và 2D Range Maximum Query (RMQ):

   • Giá trị của kích thước cạnh k có thể nằm trong khoảng từ 1 đến min(r2-r1+1, c2-c1+1). Ta có thể dùng chặt nhị phân (binary search) trên k.
   • Với một giá trị k được thử (ví dụ: mid), ta cần kiểm tra xem có tồn tại (i, j) trong vùng [r1+mid-1..r2] x [c1+mid-1..c2] sao cho DP1[i][j] >= mid HOẶC DP2[i][j] >= mid.
   • Điều này tương đương với việc kiểm tra xem giá trị lớn nhất trong ma trận con DP1[r1+mid-1..r2][c1+mid-1..c2] có lớn hơn hoặc bằng mid hay không, HOẶC giá trị lớn nhất trong ma trận con DP2[r1+mid-1..r2][c1+mid-1..c2] có lớn hơn hoặc bằng mid hay không.
   • Bài toán tìm giá trị lớn nhất trong một vùng chữ nhật trên ma trận là 2D Range Maximum Query. Ta có thể tiền xử lý bằng 2D Sparse Table trên DP1 và DP2.
   • 2D Sparse Table cho phép trả lời truy vấn RMQ trong O(1) sau khi tiền xử lý O(N^2 log N log N).

6. Các bước thực hiện:

   • Đọc ma trận A.
   • Xây dựng ma trận M1 và M2.
   • Tính ma trận DP1 và DP2 từ M1 và M2 bằng DP.
   • Xây dựng 2D Sparse Table trên DP1 và DP2.
   • Đối với mỗi truy vấn x1, y1, x2, y2:
     • Chuyển sang 0-indexed r1, c1, r2, c2.
     • Thực hiện chặt nhị phân cho k từ 1 đến min(r2-r1+1, c2-c1+1).
     • Trong hàm kiểm tra của binary search với giá trị mid: Xác định vùng truy vấn trên ma trận DP là [r1+mid-1..r2] x [c1+mid-1..c2]. Chú ý xử lý khi vùng này rỗng.
     • Sử dụng 2D Sparse Table để tìm max trong vùng này cho cả DP1 và DP2.
     • Nếu max(DP1 vùng) >= mid hoặc max(DP2 vùng) >= mid, thì mid là có thể, thử giá trị lớn hơn. Ngược lại, thử giá trị nhỏ hơn.
     • Kết quả binary search là kích thước cạnh lớn nhất tìm được.

Lưu ý: Kích thước Sparse Table là O(N^2 log^2 N), có thể cần bộ nhớ lớn. Kiểm tra giới hạn bộ nhớ của hệ thống chấm bài. Thời gian tiền xử lý là O(N^2 log^2 N), thời gian truy vấn là O(Q log N). Tổng thời gian O(N^2 log^2 N + Q log N) là phù hợp với ràng buộc N=1000, Q=10^5.

Làm thêm nhiều bài tập miễn phí tại đây