2.18 ✅ Cây đoạn (Segment Tree)

• Cách hiện thực cây đoạn bằng mảng (array-based segment tree): trừu tượng hoá phần pushUp (gộp 2 node) để có thể áp dụng cho nhiều phép toán (cộng, max, min, ...). Bài 218, 303, 307, 699.
• Cách viết kinh điển của cây đoạn đếm (counting segment tree). Bài 315, 327, 493.
• Hiện thực cây đoạn dạng cây (tree-based segment tree). Bài 715, 732.
• Lazy propagation (cập nhật lười theo đoạn). Bài 218, 699.
• Rời rạc hoá (discretization). Cần chú ý trường hợp đặc biệt: giả sử có 3 đoạn $[1,10]$, $[1,4]$, $[6,10]$. Nếu rời rạc hoá thành x[1]=1,x[2]=4,x[3]=6,x[4]=10 thì:
  • đoạn 1 thành $[1,4]$
  • đoạn 2 thành $[1,2]$
  • đoạn 3 thành $[3,4]$ Khi đó “đoạn 1 = đoạn 2 + đoạn 3” (trong không gian rời rạc), nhưng trước khi rời rạc hoá thì rõ ràng đoạn 1 > đoạn 2 + đoạn 3. Cách đúng: chèn thêm 1 điểm khi khoảng cách > 1, ví dụ giữa 1 4 6 10 chèn 5 → x[1]=1,x[2]=4,x[3]=5,x[4]=6,x[5]=10. Khi đó đoạn 1 là 1-5, đoạn 2 là 1-2, đoạn 3 là 4-5.
• Xây dựng cây đoạn linh hoạt: mỗi node có thể lưu nhiều thông tin, pushUp cũng có thể đa dạng. Bài 850, 1157.

Cây đoạn – các dạng bài từ dễ đến khó:

1. Cập nhật điểm (single point update):
   HDU 1166 敌兵布阵 update: tăng/giảm 1 điểm, query: tổng đoạn
   HDU 1754 I Hate It update: thay thế 1 điểm, query: giá trị lớn nhất/nhỏ nhất trên đoạn
   HDU 1394 Minimum Inversion Number update: tăng/giảm 1 điểm, query: tổng đoạn
   HDU 2795 Billboard query: tìm vị trí có giá trị lớn nhất trong đoạn (thực hiện update ngay trong query)
2. Cập nhật đoạn (range update):
   HDU 1698 Just a Hook update: thay thế theo đoạn (vì chỉ query 1 lần toàn đoạn nên có thể in trực tiếp thông tin node gốc)
   POJ 3468 A Simple Problem with Integers update: tăng/giảm theo đoạn, query: tổng đoạn
   POJ 2528 Mayor’s posters rời rạc hoá + update: thay thế theo đoạn, query: hash đơn giản
   POJ 3225 Help with Intervals update: thay thế theo đoạn, XOR theo đoạn, query: hash đơn giản
3. Gộp đoạn (range merge) — loại bài hỏi “đoạn liên tiếp dài nhất thỏa điều kiện”, nên pushUp phải gộp thông tin của 2 con trái/phải:
   POJ 3667 Hotel update: thay thế theo đoạn, query: điểm trái nhất thỏa điều kiện
4. Scanline (đường quét) — cần sắp xếp các thao tác và quét từ trái sang phải; kinh điển là hợp diện tích/chu vi hình chữ nhật:
   HDU 1542 Atlantis update: tăng/giảm theo đoạn, query: lấy trực tiếp giá trị ở node gốc
   HDU 1828 Picture update: tăng/giảm theo đoạn, query: lấy trực tiếp giá trị ở node gốc

---