Các cấu trúc dữ liệu đặc biệt

- Các cấu trúc dữ liệu đặc biệt Các cấu trúc dữ liệu đặc biệt Chỉ cần qua câu nói "Algorithms+Data Structures = Program" của Niklaus Wirth ta đã có thể thấy được tầm quan trọng của các loại cấu trúc dữ liệu [data structures] trong giải các bài toán tin.
- Ứng dụng 1 cách thuần thục hiệu quả các loại cấu trúc sẽ đem đến những thuận lợi vô cùng lớn cho các lập trình viên.
- Ngoài những cấu trúc dữ liệu chuẩn, quen thuộc như array, record, queue.
- còn có 1 số cấu trúc dữ liệu khác có hiệu quả đặc biệt trong 1 số dạng bài tập.
- Mặc dù vậy, tài liệu tiếng việt về những cấu trúc này lại khá ít, đặc biệt là Interval Tree, Binary Indexed Tree và Range minimum Query.
- Trong chuyên đề này sẽ đề cập tới 1 số loại cấu trúc thường xuyên được sử dụng: Interval tree, Binary Indexed Tree, Heap.
- Interval Tree.
- Interval Tree là 1 cấu trúc vô cùng hữu dụng, được sử dụng rất nhiều trong các bài toán về dãy số.
- Ngoài ra Interval Tree còn được sử dụng trong 1 số bài toán hình học.
- Có thể nói nếu nắm rõ Interval Tree bạn đã làm được 1 nửa số bài toán về dãy số rồi đấy!.
- Xin nói thêm thực ra Interval Tree tên gọi chính xác là Segment Tree nhưng cái tên Interval Tree được sử dụng nhiều hơn ở Việt Nam.
- Nếu tìm trong “Introduction to Algorithms 2nd Edition” thì bạn sẽ thấy 1 cấu trúc mang tên Interval tree nhưng với nội dung khác so với những gì sẽ được trình bày ở dưới đây.
- Ta sẽ xem xét 1 bài toán đơn giản sau để hiểu thế nào là cây Interval Tree: Bài toán: Cho 1 dãy số gồm N phần tử (NL) and (V>R.
- Như vậy thao tác GET thay vì thực hiện trong O(N) nay đã có thể thực hiện trong O(logN).
- Còn thao tác INC thì sao? Rõ ràng thao tác INC không chỉ đơn giản là cập nhật lại phần tử thứ I như trước mà ta còn phải điều chỉnh cả cây Interval Tree sao cho đúng với mô tả.
- Để update lại cây Interval Tree với mỗi thao tác tăng giá trị phần tử thứ I ta phải tăng mỗi nút của cây mà quản lý I lên 1 giá trị gtr.
- Như vậy độ phức tạp của thao tác INC mặc dù tăng từ O(1) lên O(logN) nhưng độ phức tạp chung của bài toán chỉ còn lại là O(MlogN) nhanh hơn hẳn so với thuật toán thô sơ ban đầu.
- Qua ví dụ trên ta cũng có thể hiểu qua phần nào về cấu trúc và ý nghĩa sử dụng của Interval tree: Gốc là nút lưu toàn bộ thông tin (mà trong ví dụ là tổng) từ 1 tới N, từ gốc thông tin 1 nút được chia nhỏ ra quản lý ở 2 nút con trái và phải cho tới khi mỗi nút chỉ lưu thông tin của 1 phần tử.
- Lợi ích trong phương pháp sử dụng interval tree là với 1 số đoạn con ta có thể lấy trực tiếp được thông tin trong đoạn con đó mà không phải đi lấy thông tin trong từng phần tử nhỏ trong đoạn, việc này giúp giảm độ phức tạp trong các thao tác từ O(N) xuống O(logN).
- 2 Các cấu trúc dữ liệu đặc biệt Tư tưởng của Interval tree là dùng “chia để trị”: “chia” đoạn lớn thành các đoạn nhỏ hơn để có thể “trị” nhanh chóng.
- 1 câu hỏi khác được đặt ra là lưu trữ interval tree trong thực tế như thế nào, vì ta không thể hầu như không thể bỏ ra N^2 đoạn để lưu các đoạn từ L..R được, quá tốn bộ nhớ với N lớn.
- Câu trả lời là ta sẽ dùng 1 mảng 1 chiều để lưu trữ interval tree: Data for Interval Tree 1.
- Root lưu đoạn 1..N, được lưu trữ ở A[1].
- Nếu Node I lưu đoạn [L..R] và L 3.
- Độ cao của interval tree luôn nhỏ hơn hoặc bằng logN.
- Như vậy bộ nhớ dùng cho interval tree là O(2^(logN+1).
- Trong thực tế có thể khai báo mảng O(N*3) hoặc O(N*4) là đủ.
- (Tất nhiên cũng có thể dùng Linklist – danh sách động để lưu interval tree nhưng cách này tốn bộ nhớ hơn và không tiện bằng, không hay được dùng).
- Các thông tin được lưu trong 1 node của interval tree là thông tin tổng hợp của đoạn mà nó quản lý, bởi vậy thông tin này phải là dạng tích luỹ được, ví dụ như tổng, hiệu, min hoặc max.
- Từ sau đây ta gọi chung các thao tác sửa cây Interval là các thao tác UPDATE, các thao tác lấy thông tin từ cây là thao tác GET.
- Ứng dụng của cây Interval tree đa dạng, phong phú vô cùng.
- Mỗi ví dụ sẽ mô tả 1 cách sử dụng interval tree tương đối khác nhau và thường gặp trong giải toán.
- Ví dụ 1.
- Các bài toán cơ bản ứng dụng Interval Tree: a.
- Cho dãy số, có 1 số yêu cầu thuộc 2 loại thay đổi (tăng/gán lại) giá trị 1 phần tử hoặc tìm min, max các đoạn liên tiếp của dãy số: mỗi nút interval tree sẽ lưu giá trị min/max các phần tử nó quản lý.
- Cho dãy số, có 1 số yêu cầu gán thuộc 2 loại lại giá trị của 1 phần tử hoặc tìm tổng 1 số phần tử liên tiếp của dãy.
- Bài toán tương tự như ví dụ.
- Tóm tắt đề bài: Có N tấm poster chiều cao 1.
- Theo thứ tự các tấm poster được dán lên 1 đoạn tường cũng có chiều cao 1.
- Các tấm poster sẽ phủ 1 đoạn liên tiếp từ viên gạch Li tới viên gạch Ri, tấm poster được dán sau sẽ phủ lên tấm poster được dán trước.
- Vì vậy, sau khi dán xong cả N tấm poster thì có thể có những tấm poster không thể được nhìn thấy.
- Yêu cầu: Đếm số loại poster khác nhau có thể nhìn thấy được từ ngoài vào.
- Input: Dòng đầu ghi N là số tấm poster.
- Trong N dòng tiếp theo mỗi dòng chứa 2 số Li và Ri thể hiện đầu trái và đầu phải của tấm poster thứ i.
- Output: Duy nhất 1 dòng ghi số loại poster có thể nhìn thấy được