Mình có góp ý là nếu bạn để tựa bài là "Interval tree (IT) trên tập đoạn thẳng" thì sẽ làm tăng cơ hội để người khác tìm kiếm ra bài viết của bạn sau này. Cũng tức là bài viết của bạn sẽ được đọc nhiều hơn :)

Cảm ơn anh đã góp ý, em sửa rồi ạ :D

Bài viết rất hay , rất bổ ích , mặc dù xem qua không hiểu gì nhưng vẫn thấy hay :) . 

Anh nên suggest một số bài tập để áp dụng 

_{Bạn có thể sử dụng IT đoạn thẳng để làm bài VMPIZZA của VNOI Marathon vừa rồi :)}

Bạn có thể viết to lên được không ạ mình nhìn không rõ :)

Ý chipchip là bạn viết to quá đấy. Bạn viết to quá nhìn như đang hét vào mặt người khác vậy :) Bạn có thể edit chỉnh lại cho mấy bài viết của bạn nhỏ hơn ko :)

bài viết rất hay và hữu ích, tks anh :D

Bạn có thể làm bài này

http://vn.spoj.com/problems/JEWELNB/

Theo mình hiểu thì đây chính là "cây chứa đoạn" - Segment Tree, phân biệt với Interval tree là cây chứa khoảng. Hình vẽ cây sẽ có dạng giống như trong tài liệu phân biệt của trường Tsing Hua, page 10 - 11: http://3glab.cs.nthu.edu.tw/~spoon/courses/CS631100/Lecture05_handout.pdf

Theo tài liệu của trường Tsing Hua thì mỗi node sẽ lưu 1 danh sách (list) các đoạn thẳng. Như vậy với bài toán đếm số giao điểm của các đoạn thẳng với 1 đường thẳng vuông góc với trục Ox thì thời gian thực hiện thuật toán sẽ là O(K + logMAXX), với K là số giao điểm.

Theo bài viết này thì với truy vấn tìm Ymax, mỗi node sẽ chỉ lưu 1 đoạn thẳng, như vậy khi đi từ nút gốc tới nút lá sẽ duyệt qua tối đa H = chiều cao cây = logMAXX đoạn thẳng. Vấn đề là nếu như có nhiều hơn logMAXX đoạn cắt nhau trong khoảng mà nút lá quản lý thì thông tin cần lưu ở nút lá sẽ trở thành danh sách đoạn chứ không chỉ là một đoạn ?

Cụ thể là ở các trường hợp update 3, 4, 5, 6 với low[node] == high[node] thì các node thứ 2 * node và 2 * node + 1 sẽ không tồn tại.

Vậy lúc này phải xử lý thế nào để đpt vẫn là O(logMAXX) nhỉ :D

Nếu có nhiều đoạn cắt nhau trong cùng một khoảng, như mình nói thì chỉ lưu lại một đoạn và down một nửa đoạn kia xuống. Nó chỉ rơi vào 6 trường hợp trên thôi bạn, mà vì bài toán là tìm y max nên có những phần của đoạn thẳng sẽ không cần thiết do nó hoàn toàn nằm dưới một đoạn nào đó.

Còn ở nút lá, bạn không cần xử lí gì đâu vì chắc chắn nó sẽ rơi vào trường hợp 1 hoặc 2 . Thực tế nút lá là xét tại đúng một điểm trên trục x, điểm đó chỉ cần biết đoạn cao nhất thôi.

IT đoạn thẳng trong bài viết của mình chỉ có thể tìm max hoặc min tại một điểm nào đó, không thể tìm được mấy đoạn giữa giữa đâu :) Mà vì chỉ tìm max nên không cần phải lưu tập đoạn thẳng, chỉ cần lưu một đoạn cao nhất, những đoạn thấp hơn hẳn thì bỏ, thấp hơn một nửa thì down xuống dưới.

Thanks bạn, lúc đầu mình nghĩ là thông thường tất cả các node đều phải có thông tin nên mới nhầm lẫn sang cách chia đoạn của  cây Segment Tree không theo khoảng X mà theo khoảng Index của end points (giống như trong tài liệu của trường Tsing Hua). Khi lá trùng với mỗi tọa độ X thì mỗi node có thể không có thông tin gì cả vì có thể không có đoạn thẳng nào bao hết khoảng (l,r) mà node quản lý. Mình đã AC bài JEWELNB theo cách này.

Một ưu điểm nữa của cách lưu đoạn trên cây IT có thể mở rộng ra lưu cả trên cây BIT, và không chỉ lưu đoạn mà còn lưu được các hàm tổng nói chung có dạng \(f(x) = \sum k_{i}x^i\) (hàm bậc 2, 3, 4, ....). Một ví dụ sử dụng BIT lưu hàm bậc 2 là bài Bể Cá - spoj PTIT: http://www.spoj.com/PTIT/problems/PTIT133B/

Code các hàm chính:

http://ideone.com/0VFGaP

Trên codeforces cũng có bài đã AC bằng BIT lưu hàm số bậc 2 nhưng giờ không nhớ bài nào :D

a có thể chỉ rõ ứng dụng của cái này trong bài VMPIZZA đc k ạ? e k hiểu lắm.

cho mình hỏi đoạn update 

Nửa bên trái của it[node] hoàn toàn nằm trên nửa bên trái của val. Vậy val chắc chắn không bao giờ đạt max tại nửa trái của khoảng node, ta giữ lại it[node] tại node và down val xuống con phải (node * 2 + 1).

Sao lại update bên phải mà không update bên trái, nó đâu có giao hai đoạn thẳng tại giữa đâu nhỉ

Hai đoạn giao ở giữa đấy bạn =)) Vì 2 trường hợp mà đoạn này nằm hoàn toàn trên đoạn kia đã được xét rồi, nếu 1 đoạn không nằm hoàn toàn trên đoạn kia thì rõ ràng phải giao nhau.

Chỉ update bên phải mà không update bên trái, vì ở phần ở bên trái của 1 đoạn nằm hoàn toàn trên phần bên trái của đoạn kia, mình chỉ giữ lại cái cao hơn thôi và xóa cái thấp đi. Còn bên phải thì điểm giao của hai đoạn nằm ở đó, không thể loại đoạn nào đi được, vì mình đã giữ lại đoạn cao hơn ở bên trái (tính cả nó khi query phần bên phải) nên sẽ down đoạn thấp hơn xuống con phải, để bảo tồn đoạn đó.

Xin lỗi vì bạn đã hỏi từ lâu rồi nhưng giờ mình mới thấy =)) Bài VMPIZZA bạn làm O(N^2) bằng cách QHĐ, sẽ ra được công thức f[i] = f[j] + ... gì đấy. Bạn biến đổi công thức này, sao cho thành dạng f[i] = a(j) * x(i) + b(j), với a(j), x(i), b(j) là một công thức nào đó lấy tham số là i, j. Khi đó bài toán đưa về dạng truy vấn đường thẳng cao nhất tại vị trí x(i) và có thể sử dụng IT đoạn thẳng để giải.

Đây là code của mình, bạn có thể tham khảo: http://ideone.com/ba6ShL

anh có thể cho em thêm 1 số bài tập dùng phương pháp này ko ạ :D

rip 

Hay