Làm thế nào để xây dựng một cấu trúc dữ liệu Segment Tree hỗ trợ cập nhật đoạn và truy vấn khoảng (Range Update with Range Query) sử dụng kỹ thuật Lazy Propagation trong các bài toán thực chiến?

Question

Accepted Answer

Bản chất vấn đề Khi làm việc với các bài toán yêu cầu cập nhật giá trị trên một đoạn lớn (ví dụ: cộng thêm $x$ vào tất cả các phần tử từ vị trí $L$ đến $R$) và truy vấn trên khoảng (ví dụ: tìm tổng hoặc giá trị lớn nhất từ $L$ đến $R$), việc cập nhật từng phần tử sẽ làm độ phức tạp thời gian tăng lên $O(N)$ cho mỗi lần cập nhật, dẫn đến Time Limit Exceeded trong các hệ thống quy mô lớn. Giải pháp sử dụng Segment Tree với Lazy Propagation Lazy Propagation là một kỹ thuật tối ưu hóa giúp trì hoãn việc cập nhật các nút con cho đến khi thực sự cần thiết. Thay vì cập nhật toàn bộ các nút lá trong khoảng $[L, R]$, ta lưu trữ giá trị cần cập nhật vào một mảng phụ gọi là lazy tại nút hiện tại và chỉ đẩy (push down) giá trị này xuống các nút con khi có truy vấn đi qua nút đó. Triển khai mã nguồn mẫu (C++) #include using namespace std; class SegmentTreeLazy { int n; vector tree, lazy; public: SegmentTreeLazy(int size) { n = size; tree.assign(4 * n, 0); lazy.assign(4 * n, 0); } void push(int node, int start, int end) { if (lazy[node] != 0) { int mid = (start + end) / 2; // Cập nhật cho con trái tree[2 * node] += lazy[node] * (mid - start + 1); lazy[2 * node] += lazy[node]; // Cập nhật cho con phải tree[2 * node + 1] += lazy[node] * (end - mid); lazy[2 * node + 1] += lazy[node]; // Reset lazy của nút hiện tại lazy[node] = 0; } } void updateRange(int node, int start, int end, int l, int r, long long val) { if (l > end || r < start) return; if (l <= start && end <= r) { tree[node] += val * (end - start + 1); lazy[node] += val; return; } push(node, start, end); int mid = (start + end) / 2; updateRange(2 * node, start, mid, l, r, val); updateRange(2 * node + 1, mid + 1, end, l, r, val); tree[node] = tree[2 * node] + tree[2 * node + 1]; } long long queryRange(int node, int start, int end, int l, int r) { if (l > end || r < start) return 0; if (l <= start && end <= r) return tree[node]; push(node, start, end); int mid = (start + end) / 2; return queryRange(2 * node, start, mid, l, r) + queryRange(2 * node + 1, mid + 1, end, l, r); } }; Đánh giá hiệu năng Độ phức tạp thời gian: $O(\log N)$ cho mỗi thao tác cập nhật (Range Update) và truy vấn (Range Query). Độ phức tạp không gian: $O(N)$ để lưu trữ cây và mảng lazy. Kinh nghiệm thực chiến Enterprise Kỹ thuật này thường được ứng dụng trong các hệ thống phân bổ tài nguyên, tính cước viễn thông theo khoảng thời gian, hoặc các bài toán xử lý chuỗi không gian trong GIS (Geographic Information System). Cần chú ý kích thước mảng cấp phát cho cây luôn phải là $4 imes N$ để tránh tràn bộ nhớ khi cây không phải là cây nhị phân hoàn chỉnh.

Làm thế nào để xây dựng một cấu trúc dữ liệu Segment Tree hỗ trợ cập nhật đoạn và truy vấn khoảng (Range Update with Range Query) sử dụng kỹ thuật Lazy Propagation trong các bài toán thực chiến?

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi trees liên quan cùng chủ đề