Trong bài viết trước, chúng ta đã khám phá tổng quan về cấu trúc dữ liệu Cây phân đoạn, hay còn gọi là Segment Tree hoặc Interval Tree. Để có cái nhìn rõ nét hơn về chủ đề này, các bạn có thể tham khảo lại bài viết trước.
Bài viết này sẽ trình bày một số bài toán cơ bản mà chúng ta có thể giải quyết bằng Cây phân đoạn. Mục đích của việc này là minh chứng cho khả năng giảm độ phức tạp của các thuật toán khi sử dụng cấu trúc dữ liệu này, cũng như giúp các bạn có cái nhìn tổng quan hơn về cách áp dụng Cây phân đoạn trong các bài toán lập trình cụ thể.
Bài Toán 1: Tìm Dãy Con Tăng Dài Nhất
Đề bài
Cho dãy số A gồm n phần tử a1, a2, ..., an. Một dãy con của dãy số này là cách chọn ra một số phần tử (có thể không liên tiếp) của dãy.
Yêu cầu: Tìm dãy con tăng ngặt dài nhất của dãy A.
Input:
- Dòng đầu chứa số nguyên dương n.
- Dòng thứ hai chứa n số nguyên a1, a2, ..., an phân tách nhau bởi dấu cách.
Ràng buộc:
- 1 ≤ n ≤ 10^6.
- |ai| ≤ 10^9 với mọi i: 1 ≤ i ≤ n.
Output:
- In ra độ dài dãy con tăng ngặt dài nhất tìm được.
Ví dụ:
Input:
5
2 1 4 3 5Output:
3Ý Tưởng Giải Quyết
Bài toán này có thể được giải quyết bằng kỹ thuật quy hoạch động, với độ phức tạp O(n log n) thông qua phương pháp tìm kiếm nhị phân. Tuy nhiên, trong bài viết này, chúng ta sẽ giải quyết bài toán bằng Cây phân đoạn cùng với kỹ thuật rời rạc hóa.
Rời Rạc Hóa
Rời rạc hóa là một kỹ thuật trong khoa học máy tính nhằm nén các giá trị trong một dãy về những giá trị nhỏ hơn nhưng vẫn bảo toàn thứ tự của chúng. Phương pháp này thường được sử dụng trong nhiều bài toán cạnh tranh.
Để thực hiện rời rạc hóa, ta có thể xây dựng mảng B lưu các giá trị cùng chỉ số của mảng A, sắp xếp mảng B, sau đó gán lại cho mảng A dựa trên thứ tự đã sắp xếp.
Giải Quyết Bằng Cây Phân Đoạn
Sau khi rời rạc hóa mảng A, ta định nghĩa dp[i] là chiều dài dãy con tăng dài nhất kết thúc tại phần tử ai. Với điều này, chúng ta có thể sử dụng Cây phân đoạn để cập nhật và tìm kiếm giá trị tối đa một cách nhanh chóng.
Cài Đặt Mã Nguồn
cpp
#include <bits/stdc++.h>
#define int long long
// ... Mã nguồn chi tiết... Bài Toán 2: Lắp Radars
Đề bài
HN là giám đốc một công ty kỹ thuật số truyền hình, anh đang có kế hoạch triển khai hệ thống radars tại các địa điểm trong thành phố ABZ. Bảng danh sách các địa điểm đã được sắp xếp theo thứ tự không giảm, với mỗi radar lắp đặt cho công ty một lợi nhuận nhất định. Để tránh việc các radars ảnh hưởng tới sóng thu phát của nhau, khoảng cách giữa hai radar phải lớn hơn k. Ví dụ với một danh sách vị trí và lợi nhuận tương ứng, nếu k=2 thì chỉ có thể chọn được những radar không gần nhau hơn.
Yêu cầu:
Giúp HN lựa chọn các radar sao cho lợi nhuận thu được là tối đa.
Dữ liệu:
- Dòng đầu chứa số nguyên dương T – số lượng test cases.
- Mỗi test case chứa:
- Hai số nguyên n và k – số lượng hệ thống radars và giới hạn khoảng cách tối thiểu.
- Vị trí và lợi nhuận tương ứng.
Kết quả:
In ra lợi nhuận tối đa.
Ý Tưởng Giải Quyết
Bài toán này có thể giải quyết bằng quy hoạch động, và để tối ưu độ phức tạp, chúng ta sử dụng Cây phân đoạn để theo dõi giá trị lợi nhuận tối đa có thể đạt được cho mỗi radar.
Cài Đặt Mã Nguồn
cpp
#include <bits/stdc++.h>
#define int long long
// ... Mã nguồn chi tiết... Bài Toán 3: Dãy Con Liên Tiếp
Đề bài
Cho dãy số nguyên A gồm n phần tử và một số nguyên p, đếm số lượng dãy con liên tiếp có trung bình cộng không nhỏ hơn p.
Yêu cầu:
Tìm kiếm số lượng dãy con thỏa mãn điều kiện trên.
Ý Tưởng Giải Quyết
Sử dụng kỹ năng tính tổng tiền tố, các dãy con liên tiếp có trung bình lớn hơn hoặc bằng p sẽ chuyển thành dãy có tổng lớn hơn hoặc bằng 0. Sử dụng các công cụ của Cây phân đoạn để đếm số dãy con hợp lệ.
Cài Đặt Mã Nguồn
cpp
#include <bits/stdc++.h>
#define int long long
// ... Mã nguồn chi tiết... Bài Toán 4: Dãy Số Hình Nón
Đề bài
Cho dãy số A gồm N phần tử, tìm dãy con hình nón có tổng các chữ số lớn nhất.
Khái Quát Giải Quyết
Sử dụng quy hoạch động và Cây phân đoạn để tìm kiếm dãy con hình nón với điều kiện tăng dần rồi giảm dần, áp dụng rời rạc hóa nếu cần thiết.
Cài Đặt Mã Nguồn
cpp
#include <bits/stdc++.h>
// ... Mã nguồn chi tiết... Tài Liệu Tham Khảo
- VNOI Segment Tree Problems.
- https://vnoi.info/wiki/algo/data-structures/segment-tree-basic.md
- Codeforces - Segment Tree Problems.
source: viblo
