I. Giới thiệu

Trong phần 3 của chuỗi bài viết về Cây phân đoạn, chúng ta sẽ khám phá kỹ thuật Cập nhật lười (Lazy Propagation). Đây là một phương pháp quan trọng trong việc tối ưu hóa cây phân đoạn, giúp xử lý các truy vấn cập nhật một cách nhanh chóng và hiệu quả hơn.

1. Tổng quan về Cây phân đoạn

Cây phân đoạn là một cấu trúc dữ liệu mạnh mẽ, cho phép chúng ta thực hiện các thao tác như xây dựng, cập nhật và truy vấn trên mảng một cách hiệu quả. Trong các bài viết trước, chúng ta đã đề cập đến những vấn đề cơ bản như:

• Cách xây dựng cây phân đoạn.
• Các thao tác cập nhật.
• Cách lấy kết quả từ cây.
• Một số bài toán ứng dụng.

2. Các truy vấn trên mảng

Trong phần này, chúng ta sẽ xem xét hai loại truy vấn khi làm việc với một mảng gồm n phần tử:

• Loại 1: Tăng giá trị của tất cả các phần tử từ chỉ số l đến r lên một giá trị val.
• Loại 2: Trả về giá trị nhỏ nhất trong khoảng từ chỉ số l đến r.

Ví dụ về các truy vấn:

3
1 2 3
7
1 1 3 1
1 2 3 4
2 1 3
1 1 1 5
2 1 2
1 1 2 2
2 2 3

Và kết quả sẽ là:

8
7
9

3. Kỹ thuật Cập Nhật Lười (Lazy Propagation)

Khi thực hiện các thao tác cập nhật trên dãy số, nếu ta trực tiếp cập nhật từng phần tử trong một đoạn lớn, độ phức tạp của thuật toán sẽ rất cao. Để giải quyết vấn đề này, chúng ta sẽ sử dụng kỹ thuật Cập nhật lười:

Ý tưởng chính: Thay vì cập nhật từng phần tử trên đoạn từ l đến r, chúng ta chỉ cần lưu lại thông tin về đoạn cần cập nhật tại các nút của cây phân đoạn. Khi cần truy cập hoặc cập nhật, chúng ta sẽ thực hiện việc cập nhật ghi chú này, gọi là giá trị lazy.

Khi cần thực hiện cập nhật cho một nút, chúng ta thực hiện các bước sau:

1. Cập nhật giá trị của nút đó theo giá trị của lazy.
2. Đẩy giá trị lazy xuống cho các con của nó nếu nút không phải là nút lá.
3. Gán lại giá trị lazy cho nút đó về 0 để tránh ảnh hưởng đến các lần cập nhật sau.

4. Cài đặt

Khi xây dựng cây phân đoạn, chúng ta cần thực hiện các chức năng cập nhật và lấy giá trị với việc sử dụng Lazy Propagation. Đoạn mã sau đây minh họa cho quá trình này:

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

void build_tree(int id, int u, int v, vector < int > &a, vector < int > &st) {
    if (u == v) {
        st[id] = a[u];
        return;
    }
    int mid = (u + v) >> 1;
    build_tree(2 * id, u, mid, a, st);
    build_tree(2 * id + 1, mid + 1, v, a, st);
    st[id] = max(st[2 * id], st[2 * id + 1]);
}

// Cập nhật giá trị đầu vào cho các nút con.
void lazy_update(int id, int u, int v, vector < int > &st, vector < int > &lazy) {
    if (!lazy[id]) return;
    st[id] += lazy[id];
    if (u != v) {
        lazy[2 * id] += lazy[id];
        lazy[2 * id + 1] += lazy[id];
    }
    lazy[id] = 0;
}
// Các hàm khác ...

5. Đánh giá hiệu suất

Sử dụng kỹ thuật Cập nhật lười, độ phức tạp của các thao tác cập nhật giảm về O(log n), giúp cho thuật toán có thể xử lý nhanh chóng ngay cả đối với số lượng truy vấn lớn.

II. Các bài toán ứng dụng

Một số bài toán có thể áp dụng kỹ thuật Lazy Propagation bao gồm:

• Bài toán A simple task từ Codeforces Round 312
• Bài toán Búp bê Nga

III. Kết luận

Kỹ thuật Cập nhật lười là một trong những cải tiến quan trọng giúp tối ưu hóa hiệu suất của cây phân đoạn. Việc áp dụng thành công kỹ thuật này sẽ giúp các lập trình viên giải quyết các bài toán phức tạp một cách hiệu quả hơn.
source: viblo