Du Hành Thời Gian Cùng Persistent Segment Tree!

Nếu anh em thấy hay thì ủng hộ mình 1 follow + 1 upvote + 1 bookmark + 1 comment cho bài viết này tại Mayfest 2025 nhé, cảm ơn anh em!

Xin chào anh em, tôi - Jim đây! Hôm nay, tôi sẽ chia sẻ với anh em một chủ đề cực "chất" trong giới lập trình thi đấu: Cây Phân Đoạn Bất Biến (Persistent Segment Tree - PST). Nghe tên có vẻ "nguy hiểm" nhưng tin tôi đi, sau bài viết này, anh em sẽ thấy nó "thân thiện" và "quyền năng" đến bất ngờ!

1. Giải Mã Siêu Năng Lực!

Đã bao giờ anh em ước ao sở hữu một cỗ máy thời gian, không phải để thay đổi quá khứ hay nhìn trộm tương lai, mà đơn giản là để quay lại một "phiên bản" cũ của mình chưa? Chẳng hạn, khi đang phân tích một bảng số liệu khổng lồ, một ai đó vô tình cập nhật nhầm một giá trị, và toàn bộ kết quả phân tích trước đó bỗng chốc "bay màu". Hoặc có thể, trong một hệ thống quản lý kho, người quản lý muốn biết chính xác số lượng tồn kho của một mặt hàng cụ thể trước đợt khuyến mãi lớn tháng trước. Những tình huống "dở khóc dở cười" như vậy không hề hiếm, và chúng thường dẫn đến một ước muốn cháy bỏng: "Giá mà có cách nào xem lại dữ liệu cũ một cách dễ dàng!". Nhu cầu "du hành thời gian" với dữ liệu này không chỉ xuất hiện trong các bài toán chuyên ngành mà còn rất gần gũi với trải nghiệm hàng ngày của nhiều người, từ việc xem lại lịch sử chỉnh sửa văn bản đến việc kiểm tra các giao dịch ngân hàng cũ.

Và rồi, giữa những lúc "tiến thoái lưỡng nan" ấy, một "siêu anh hùng" trong thế giới cấu trúc dữ liệu xuất hiện: Cây Phân Đoạn Bất Biến (Persistent Segment Tree – PST). Đây không chỉ là một cái tên nghe "kêu" mà còn là một giải pháp mạnh mẽ, một "pháp sư thời gian" thực thụ, cho phép không chỉ truy vấn hiệu quả trên các đoạn dữ liệu mà còn "nhìn trộm" bất kỳ trạng thái nào của dữ liệu trong quá khứ.

Trong cuộc phiêu lưu khám phá Cây Phân Đoạn Bất Biến này, chúng ta sẽ cùng nhau:

• Gặp lại người bạn quen thuộc Segment Tree, một "chiến mã" mạnh mẽ nhưng có phần "đãng trí".
• Giải mã khái niệm "bất biến" (persistence) – thứ "bùa hộ mệnh" giúp lưu giữ lịch sử.
• Chứng kiến sự kết hợp kỳ diệu giữa Segment Tree và tính bất biến để tạo nên PST.
• Học bí thuật "Path Copying" – nghệ thuật sao chép thông minh để tiết kiệm tài nguyên.
• Xem PST trình diễn sức mạnh qua các ví dụ cụ thể.
• Và cuối cùng, khám phá những ứng dụng thực tế đầy ấn tượng của "bảo bối" này.

2. Segment Tree: "Chiến Mã" Thân Quen (Ôn Bài Siêu Tốc)

Đọc thêm chi tiết tại: Cây Phân Đoạn (Segment Tree) "Vỡ Lòng"

Trước khi khám phá những điều kỳ diệu của Cây Phân Đoạn Bất Biến, hãy cùng "ôn bài" một chút về người anh em của nó: Cây Phân Đoạn (Segment Tree - ST) thông thường. Đây là một cấu trúc dữ liệu quen thuộc, một "chiến mã" đáng tin cậy trong việc xử lý các truy vấn trên một đoạn của mảng.

Segment Tree hoạt động dựa trên nguyên lý "chia để trị" (divide and conquer). Nó phân chia một vấn đề lớn (ví dụ, tính tổng một đoạn dài trong mảng) thành các vấn đề con nhỏ hơn, dễ giải quyết hơn, sau đó tổng hợp kết quả của các vấn đề con đó để đưa ra câu trả lời cuối cùng. Hãy hình dung việc này giống như khi anh em muốn sắp xếp một thư viện khổng lồ. Thay vì tự mình làm tất cả, anh em chia thư viện thành các khu vực nhỏ hơn, rồi mỗi khu vực lại chia thành các kệ sách, và cứ thế cho đến khi mỗi phần công việc trở nên cực kỳ đơn giản.

Mỗi nút trong Segment Tree đại diện cho một "phần" (segment) của mảng ban đầu. Nút gốc bao quát toàn bộ mảng, trong khi các nút lá chỉ đại diện cho một phần tử duy nhất của mảng.

2.1. "Tuyệt Chiêu" Cốt Lõi: Các Thao Tác Chính

Một Segment Tree thường hỗ trợ ba thao tác chính:

• Build (Xây dựng): Thao tác này khởi tạo cây Segment Tree từ một mảng dữ liệu cho trước. Quá trình này bắt đầu từ các nút lá (tương ứng với các phần tử của mảng) và đệ quy lên trên, tính toán giá trị cho các nút cha dựa trên giá trị của các nút con, cho đến khi nút gốc được hình thành.
• Update (Cập nhật): Khi một phần tử trong mảng cơ sở thay đổi, Segment Tree cũng cần được cập nhật để phản ánh sự thay đổi đó. Thao tác update thường bắt đầu bằng việc cập nhật giá trị của nút lá tương ứng, sau đó lan truyền sự thay đổi này lên các nút cha dọc theo đường đi từ nút lá đó lên nút gốc.
• Query (Truy vấn): Đây là thao tác để lấy thông tin tổng hợp (ví dụ: tổng, giá trị nhỏ nhất, giá trị lớn nhất) trên một đoạn [L, R] bất kỳ của mảng. Segment Tree cho phép thực hiện truy vấn này một cách hiệu quả bằng cách kết hợp thông tin từ một số lượng nhỏ các nút trên cây.

Để dễ hình dung hơn, có thể tưởng tượng Segment Tree như một "Kệ Sách Thần Kỳ". Mỗi kệ sách (nút) có một tấm thẻ ghi tóm tắt thông tin (ví dụ: tổng số trang, cuốn sách dày nhất) của một dãy sách cụ thể mà kệ đó quản lý. Kệ cao nhất (nút gốc) tóm tắt toàn bộ thư viện. Các kệ thấp hơn chia nhỏ thư viện thành các khu vực, rồi các dãy sách nhỏ hơn. Khi muốn biết tổng số trang của một dãy sách từ kệ X đến kệ Y (query), thủ thư không cần lật giở từng cuốn sách. Thay vào đó, họ chỉ cần xem xét thông tin trên một vài tấm thẻ tóm tắt ở các kệ phù hợp là có thể đưa ra câu trả lời nhanh chóng. Khi một cuốn sách được thêm vào hoặc có sự thay đổi về số trang (update), các tấm thẻ tóm tắt trên các kệ liên quan cũng sẽ được cập nhật tương ứng.

2.2. Tại Sao Lại "Hot" Đến Vậy?

Sở dĩ Segment Tree được ưa chuộng là vì hiệu năng vượt trội của nó. Cả thao tác truy vấn đoạn và cập nhật một phần tử đều có độ phức tạp thời gian là $O(log N)$, trong đó N là kích thước của mảng. Điều này nhanh hơn rất nhiều so với việc duyệt toàn bộ mảng (độ phức tạp $O(N)$) cho mỗi truy vấn hoặc cập nhật, đặc biệt khi N lớn. Hiệu quả này đạt được nhờ vào cấu trúc phân cấp của cây và nguyên lý "chia để trị" vốn có. Độ cao của cây là $O(log N)$, và các thao tác chỉ cần duyệt qua một số lượng nút tương ứng với độ cao này.

2.3. Ví Dụ "Nhỏ Mà Có Võ":

Xét mảng A = [1, 2, 3, 4, 5]. Một cây Segment Tree được xây dựng để tính tổng các đoạn. Truy vấn tổng đoạn [1, 3] (tức là các phần tử A[1], A[2], A[3], tương ứng với giá trị 2, 3, 4). Cây ST sẽ trả về 2+3+4=9. Giả sử cập nhật A[2] = 10. Mảng trở thành [1, 2, 10, 4, 5]. Truy vấn lại tổng đoạn [1, 3]. Cây ST (đã được cập nhật) sẽ trả về 2+10+4=16.

Tuy nhiên, một cây Segment Tree thông thường sẽ "quên" mất rằng tổng của đoạn [1, 3] trước đó là 9. Nó chỉ lưu giữ trạng thái hiện tại của dữ liệu. Đây chính là lúc tính "bất biến" và Cây Phân Đoạn Bất Biến phát huy tác dụng.

3. Tính Bất Biến: Nghệ Thuật "Không Bao Giờ Quên" (Mà Không Cần Tích Trữ Cả Kho!)

Trong thế giới của cấu trúc dữ liệu, "bất biến" (persistent) là một khái niệm vô cùng thú vị. Một cấu trúc dữ liệu được gọi là bất biến nếu như sau mỗi thao tác "sửa đổi", phiên bản cũ của nó vẫn được bảo toàn nguyên vẹn. Thay vì thay đổi trực tiếp lên cấu trúc hiện có, một phiên bản mới sẽ được tạo ra, mang theo những thay đổi đó, trong khi phiên bản gốc vẫn "trơ gan cùng tuế nguyệt".

Phép Tương Đồng "Git Thần Thánh": Nếu đã từng làm việc với hệ thống quản lý phiên bản Git, anh em sẽ thấy ý tưởng này rất quen thuộc. Mỗi lần thực hiện commit, một "ảnh chụp" (snapshot) mới của mã nguồn được tạo ra. Quan trọng hơn, anh em hoàn toàn có thể "du hành thời gian" bằng cách checkout về bất kỳ commit nào trong quá khứ để xem lại trạng thái cũ của dự án. Tính bất biến trong cấu trúc dữ liệu cũng hoạt động với một tinh thần tương tự.

Phép Tương Đồng "Cuốn Sổ Ma Thuật Không Tẩy Xóa": Hãy hình dung một cuốn sổ ghi chép đặc biệt. Mỗi khi muốn sửa đổi một thông tin đã viết, thay vì dùng tẩy để xóa đi (làm mất dấu vết cũ), người viết sẽ lấy một trang giấy mới. Họ sao chép lại những phần không thay đổi từ trang cũ, bổ sung hoặc sửa đổi những thông tin cần thiết, rồi kẹp trang mới này vào sau trang cũ, kèm theo một ghi chú kiểu "Đây là phiên bản cập nhật của trang X, lúc Y giờ". Cứ như vậy, cuốn sổ ngày một dày thêm với các trang ghi lại từng phiên bản thay đổi, và anh em luôn có thể lật lại bất kỳ trang cũ nào để xem chính xác nội dung của nó tại thời điểm đó.

3.1. Sao Lại Cần Đến Nó? (Du Hành Thời Gian Có Lợi Gì?)

Khả năng "không bao giờ quên" này mang lại nhiều lợi ích thiết thực:

• Truy Vấn Lịch Sử: Trả lời các câu hỏi về trạng thái dữ liệu tại một thời điểm cụ thể trong quá khứ. Ví dụ, "Lượng truy cập website vào ngày X tháng Y năm Z là bao nhiêu?" hoặc "Số dư tài khoản của khách hàng A vào cuối quý trước là bao nhiêu?".
• Chức Năng Undo/Redo "Thần Chưởng": Trong nhiều ứng dụng, như trình soạn thảo văn bản hoặc phần mềm đồ họa, khả năng hoàn tác (undo) hoặc làm lại (redo) một thao tác là cực kỳ quan trọng. Tính bất biến là nền tảng cho việc hiện thực hóa chức năng này một cách hiệu quả.
• Debug "Như Thám Tử": Khi một lỗi phát sinh trong chương trình, việc có thể xem lại trạng thái của dữ liệu qua từng bước thực thi trước đó là một công cụ vô giá giúp các nhà phát triển khoanh vùng và tìm ra nguyên nhân gây lỗi.
• Phân Tích Xu Hướng: So sánh dữ liệu ở các thời điểm khác nhau giúp phát hiện các mẫu, xu hướng thay đổi, từ đó đưa ra các dự đoán hoặc quyết định kinh doanh.
• Trong Lập Trình Thi Đấu (Competitive Programming): Rất nhiều bài toán yêu cầu xử lý các truy vấn trên các phiên bản khác nhau của một tập dữ liệu sau một loạt các cập nhật.

3.2. Cách "Cùi Bắp": Sao Chép Toàn Bộ (Ctrl+C, Ctrl+V Đến Vô Tận!)

Một cách tiếp cận đơn giản nhất để lưu trữ nhiều phiên bản là mỗi khi có sự thay đổi, chúng ta tạo một bản sao hoàn chỉnh của toàn bộ cấu trúc dữ liệu. Nếu cấu trúc dữ liệu là một mảng gồm N phần tử, mỗi lần cập nhật sẽ tốn $O(N)$ thời gian và $O(N)$ không gian bộ nhớ để sao chép. Nếu có M lượt cập nhật, tổng chi phí sẽ lên tới $O(M \times N)$. Với lượng dữ liệu lớn và số lần cập nhật thường xuyên, phương pháp này nhanh chóng trở nên không khả thi, khiến hệ thống trở nên chậm chạp và tiêu tốn một lượng lớn bộ nhớ.

Rõ ràng, nhu cầu truy cập các phiên bản lịch sử của dữ liệu là rất thực tế và quan trọng. Tuy nhiên, việc sao chép toàn bộ dữ liệu sau mỗi lần thay đổi là một giải pháp quá tốn kém, cả về thời gian xử lý lẫn không gian lưu trữ. Điều này đặt ra một thách thức: làm thế nào để có được khả năng "du hành thời gian" mà không phải trả một cái giá quá đắt? Đây chính là lúc các kỹ thuật xây dựng cấu trúc dữ liệu bất biến một cách hiệu quả, như kỹ thuật "sao chép đường dẫn" (path copying) được sử dụng trong Cây Phân Đoạn Bất Biến, trở nên vô cùng giá trị. Chúng giải quyết bài toán "muốn cả hai": vừa có khả năng truy cập lịch sử, vừa đảm bảo hiệu suất hoạt động.

4. Cây Phân Đoạn Bất Biến (PST): Song Kiếm Hợp Bích! (Thư Viện Thời Gian Di Động Của Chúng Ta)

Cây Phân Đoạn Bất Biến (PST) chính là "đứa con lai" tuyệt vời, kết tinh từ sức mạnh truy vấn đoạn hiệu quả của Segment Tree và khả năng lưu trữ lịch sử "bất diệt" của tính bất biến. Nó cho phép thực hiện các thao tác quen thuộc như build, update, và query trên một cấu trúc giống Segment Tree, nhưng với một điểm khác biệt then chốt: mỗi thao tác update không ghi đè lên dữ liệu cũ mà sẽ tạo ra một "phiên bản" (version) hoàn toàn mới của cây. Điều quan trọng là các phiên bản cũ vẫn được bảo toàn nguyên vẹn và sẵn sàng để truy cập bất cứ lúc nào.

4.1. "Bí Kíp" Thượng Thừa: Sao Chép Đường Dẫn (Path Copying) – "Nghệ Thuật Photocopy Thông Minh"

Đây chính là "trái tim" của PST, là bí thuật giúp nó đạt được tính bất biến mà không gây lãng phí tài nguyên một cách khủng khiếp.

Ý Tưởng Chủ Đạo: Khi một phần tử trong mảng cơ sở được cập nhật, chỉ có một số lượng nhỏ các nút trong Segment Tree bị ảnh hưởng trực tiếp. Cụ thể, đó là các nút nằm trên đường đi từ nút lá chứa phần tử đó ngược lên đến nút gốc. Số lượng các nút này chỉ khoảng $O(log N)$. Thay vì tạo ra một bản sao hoàn chỉnh của toàn bộ cây (với $O(N)$ nút), kỹ thuật Path Copying chỉ tạo mới đúng $O(log N)$ nút bị ảnh hưởng này. Các nút còn lại, những nút không nằm trên đường đi cập nhật, sẽ được "tái sử dụng" hoặc "chia sẻ" từ phiên bản trước đó của cây.

Phép Tương Đồng "Cuốn Sổ Ma Thuật Tiến Hóa" (Chi Tiết Hơn): Hãy tưởng tượng anh em đang quản lý một "Biên Niên Sử Hoàng Gia" khổng lồ (đây là phiên bản 0 của cây PST). Mỗi trang trong cuốn biên niên sử này (một nút trong cây) ghi lại thông tin tổng hợp về một giai đoạn lịch sử nhất định của vương quốc (một đoạn của mảng dữ liệu). Khi một sự kiện lịch sử quan trọng xảy ra (tức là có một update lên một phần tử dữ liệu), thay vì gạch xóa hay viết đè lên cuốn biên niên sử cũ kỹ, vị "Sử Quan Thời Gian" (chính là thuật toán update của PST) sẽ tạo ra một "Phụ Lục" mới cho biên niên sử (đây là phiên bản mới của cây).

Điều đặc biệt là trong Phụ Lục này, chỉ những trang ghi chép về các giai đoạn bị ảnh hưởng trực tiếp bởi sự kiện mới (tức là các nút trên đường đi từ lá lên gốc trong Segment Tree) mới được viết lại hoàn toàn mới. Những trang này sẽ chứa thông tin đã được cập nhật. Còn những trang ghi chép về các giai đoạn lịch sử không hề liên quan đến sự kiện vừa xảy ra thì sao? Vị Sử Quan sẽ không tốn công chép lại toàn bộ chúng. Thay vào đó, trong Phụ Lục mới, tại vị trí của những trang "không đổi" này, sẽ có một "chỉ dẫn ma thuật" (thực chất là con trỏ hoặc tham chiếu) trỏ thẳng về trang tương ứng trong cuốn Biên Niên Sử gốc (hoặc các Phụ Lục cũ hơn nếu có). Đây chính là bản chất của "structural sharing" (chia sẻ cấu trúc) hay "path copying" (sao chép đường dẫn).

Kết quả là, mỗi Phụ Lục mới (mỗi phiên bản mới của cây) chỉ dày thêm một vài trang ($O(log N)$ nút mới), nhưng khi "đọc" Phụ Lục này, anh em vẫn có cảm giác như đang xem một cuốn biên niên sử hoàn chỉnh và cập nhật nhất. Các chỉ dẫn ma thuật sẽ tự động dẫn đến những phần không đổi từ các phiên bản cũ hơn. Mỗi cuốn Biên Niên Sử gốc và mỗi Phụ Lục đều có một "dấu triện" riêng ở trang bìa (con trỏ trỏ đến nút gốc của phiên bản đó), giúp anh em dễ dàng tìm lại đúng "dòng thời gian" mà mình muốn tham khảo.

Minh Họa Trực Quan (Path Copying): Để dễ hình dung hơn, hãy tưởng tượng cây Segment Tree ban đầu (Version 0) có các nút được tô màu xanh lá. Khi một phần tử ở nút lá X được cập nhật, một phiên bản mới (Version 1) được tạo ra. Một nút gốc mới (ví dụ, tô màu đỏ) cho Version 1 sẽ được tạo. Nếu nhánh con bên trái của nút gốc cũ không bị ảnh hưởng bởi việc cập nhật X (ví dụ, X nằm ở nhánh phải), thì con trỏ trái của nút gốc đỏ mới sẽ trỏ thẳng vào nút con trái màu xanh lá của gốc cũ. Nhánh con bên phải (nơi chứa X) bị ảnh hưởng, do đó một nút con phải mới (màu đỏ) sẽ được tạo cho nút gốc đỏ. Quá trình này tiếp tục đi xuống. Chỉ những nút nằm trên đường đi từ gốc mới đến vị trí của X, và các nút tổ tiên của X trên đường đi đó, mới được tạo mới (màu đỏ). Tất cả các nhánh và nút con khác không nằm trên đường đi này sẽ được "vay mượn" bằng cách trỏ trực tiếp đến các nút tương ứng (màu xanh lá) của Version 0. Kết quả là Version 1 có một đường dẫn các nút "màu đỏ" mới, còn lại là các liên kết đến các phần "màu xanh lá" không đổi của Version 0.

4.2. Cấu Trúc Nút (Node): Bên Trong "Viên Ngọc" Node Của Chúng Ta Có Gì?

Cấu trúc của một nút trong PST thường rất đơn giản, tương tự như nút trong Segment Tree thông thường. Mỗi nút thường bao gồm:

• value: Lưu trữ giá trị tổng hợp cho đoạn mà nút đó quản lý (ví dụ: tổng các phần tử, giá trị nhỏ nhất, giá trị lớn nhất).
• left: Một con trỏ (hoặc tham chiếu) đến nút con trái, đại diện cho nửa đầu của đoạn.
• right: Một con trỏ (hoặc tham chiếu) đến nút con phải, đại diện cho nửa sau của đoạn.

4.3. Quản Lý "Các Phiên Bản": Làm Sao Để Theo Dõi Các "Dòng Thời Gian" Khác Nhau?

Việc quản lý nhiều phiên bản của PST nghe có vẻ phức tạp, nhưng thực tế lại khá thanh lịch. Cách phổ biến nhất là sử dụng một mảng (hoặc danh sách) để lưu trữ các con trỏ đến nút gốc của mỗi phiên bản cây.

Ví dụ, roots[0] sẽ trỏ đến nút gốc của cây ban đầu (Version 0). Sau lần cập nhật đầu tiên, một nút gốc mới cho Version 1 được tạo ra, và roots[1] sẽ trỏ đến nút gốc này. Cứ như vậy, roots[v] sẽ là "cánh cổng" dẫn vào trạng thái của dữ liệu sau v lần cập nhật. Khi muốn thực hiện một truy vấn trên phiên bản thứ v, chỉ cần lấy nút gốc từ roots[v] và bắt đầu quá trình truy vấn từ đó.

Sự phức tạp của việc tạo ra các phiên bản này (thông qua path copying) được đóng gói gọn gàng trong hàm update, trong khi việc truy cập một phiên bản cụ thể lại rất trực tiếp. Điều này cho thấy một thiết kế tốt giúp che giấu sự phức tạp bên trong, mang lại sự đơn giản cho người sử dụng.

Kỹ thuật "path copying" thực chất là một dạng của "structural sharing" (chia sẻ cấu trúc). Thay vì sao chép toàn bộ cấu trúc cho mỗi phiên bản mới, các phiên bản khác nhau của PST chia sẻ các phần không thay đổi của cây. Điều này tương tự như cách các cấu trúc dữ liệu bất biến trong lập trình hàm hoạt động; ví dụ, khi thêm một phần tử vào đầu một danh sách liên kết bất biến, phần đuôi của danh sách cũ được "tái sử dụng" bởi danh sách mới. Sự chia sẻ thông minh này chính là chìa khóa mang lại hiệu quả về bộ nhớ cho Cây Phân Đoạn Bất Biến.

5. PST "Tung Chưởng": Xem Vài Chiêu Thức Nhé! (Các Thao Tác Kèm Ví Dụ "Cháy")

Giờ là lúc chúng ta xem Cây Phân Đoạn Bất Biến (PST) "ra chiêu" như thế nào qua các thao tác cơ bản: xây dựng cây ban đầu, cập nhật tạo phiên bản mới, và truy vấn trên các phiên bản đó.

5.1. "Khởi Tạo Quyển Sổ Đầu Tiên" (Build Ban Đầu - build)

Thao tác này giống hệt như việc xây dựng một cây Segment Tree (ST) thông thường. Mục tiêu là tạo ra phiên bản đầu tiên (Version 0) của cây từ mảng dữ liệu ban đầu. Quá trình diễn ra đệ quy:

1. Nếu đoạn hiện tại chỉ chứa một phần tử (nút lá), tạo một nút mới lưu giá trị của phần tử đó.
2. Nếu không, chia đoạn thành hai nửa, đệ quy xây dựng cây con trái và cây con phải.
3. Tạo nút hiện tại, giá trị của nó được tổng hợp từ giá trị của hai nút con (ví dụ: tổng, min, max), và gán con trỏ left, right tương ứng.
4. Con trỏ tới nút gốc của cây vừa xây dựng này sẽ được lưu lại, thường là roots[0].

Ví dụ: Mảng arr = [1, 3, 2, 5]. Giả sử xây dựng cây tính tổng. Nút lá cho 1, 3, 2, 5. Nút cha của (1,3) sẽ có giá trị 1+3=4. Nút cha của (2,5) sẽ có giá trị 2+5=7. Nút gốc sẽ có giá trị 4+7=11. roots[0] sẽ trỏ tới nút gốc này.

Cấu trúc Node và khởi tạo (C++):

// Cấu trúc Node của cây phân đoạn
struct Node
{ int value; // Giá trị tổng của nút Node* left; // Con trỏ đến nút con trái Node* right; // Con trỏ đến nút con phải // Constructor Node(int val = 0, Node* l = nullptr, Node* r = nullptr) : value(val), left(l), right(r) {}
}; // Danh sách các root tương ứng với từng phiên bản cây
vector<Node* > roots; // Hàm xây dựng cây phân đoạn từ mảng
Node* build(const vector<int> &arr, int l, int r)
{ if (l == r) { // Nút lá return new Node(arr[l]); } int mid = (l + r) / 2; Node* leftChild = build(arr, l, mid); Node* rightChild = build(arr, mid + 1, r); // Nút cha với tổng giá trị từ 2 con return new Node(leftChild->value + rightChild->value, leftChild, rightChild);
} // Demo
int main()
{ vector<int> arr = {1, 3, 2, 5}; if (!arr.empty()) { Node* root = build(arr, 0, arr.size() - 1); roots.push_back(root); } // Kiểm tra kết quả root cout << "Root value (total sum): " << roots[0]->value << endl; // Expect 11 return 0;
}

Trong đoạn mã trên, Node là lớp đại diện cho một nút trong cây. Hàm build tạo ra cây ST ban đầu một cách đệ quy.

5.2. "Viết Lại Lịch Sử" (Cập Nhật - update)

Đây là nơi phép màu "path copying" thực sự diễn ra, tạo nên tính bất biến cho PST. Hàm update sẽ không sửa đổi cây cũ mà tạo ra một cây mới (một phiên bản mới) dựa trên cây cũ và sự thay đổi.

Hàm update thường nhận các tham số:

• prevNode: Nút gốc của phiên bản cây trước đó.
• leftIdx, rightIdx: Khoảng chỉ số mà prevNode quản lý.
• targetIdx: Vị trí trong mảng cần cập nhật.
• newVal: Giá trị mới tại targetIdx. Hàm sẽ trả về một nút gốc mới, đại diện cho phiên bản cây sau khi cập nhật.

Quá trình đệ quy của update:

1. Tạo nút mới: Đầu tiên, tạo một bản sao của prevNode (hoặc một nút mới hoàn toàn có cấu trúc tương tự). Gọi là currentNode.
2. Trường hợp cơ sở (nút lá): Nếu leftIdx == rightIdx (đã đến nút lá cần cập nhật), thì currentNode.value sẽ là newVal.
3. Trường hợp đệ quy:
   • Tính mid = (leftIdx + rightIdx) // 2.
   • Nếu targetIdx <= mid (cập nhật nằm ở nhánh con trái):
     • Gọi đệ quy update cho nhánh con trái: currentNode.left = update(prevNode.left, leftIdx, mid, targetIdx, newVal).
     • Nhánh con phải không đổi, nên "xài chung": currentNode.right = prevNode.right.
   • Ngược lại (cập nhật nằm ở nhánh con phải):
     • Nhánh con trái không đổi: currentNode.left = prevNode.left.
     • Gọi đệ quy update cho nhánh con phải: currentNode.right = update(prevNode.right, mid + 1, rightIdx, targetIdx, newVal).
   • Cập nhật currentNode.value dựa trên giá trị của currentNode.left và currentNode.right.
4. Trả về currentNode.

Nút gốc mới này sẽ được lưu vào mảng roots để đánh dấu một phiên bản mới.

Ví dụ (tiếp theo): Từ roots[0] (tương ứng mảng [1, 3, 2, 5]), cập nhật phần tử tại chỉ số 1 (giá trị 3) thành 7. Một newRoot sẽ được tạo và lưu vào roots[1]. roots[0] vẫn trỏ đến cây ban đầu, không thay đổi. Cây mới tại roots[1] sẽ phản ánh mảng ảo [1, 7, 2, 5]. Chỉ các nút trên đường đi từ gốc đến lá của chỉ số 1 mới được tạo mới, các nút khác được chia sẻ từ roots[0].

Code minh họa (C++):

Node* update(Node* prevNode, int leftIdx, int rightIdx, int targetIdx, int newVal)
{ // Trường hợp an toàn, nếu cây lỗi if (prevNode == nullptr) { return (leftIdx == rightIdx) ? new Node(newVal) : nullptr; } if (leftIdx == rightIdx) { // Đã đến nút lá cần cập nhật return new Node(newVal); } int mid = (leftIdx + rightIdx) / 2; // Mặc định giữ nguyên con cũ Node* newLeftChild = prevNode->left; Node* newRightChild = prevNode->right; if (targetIdx <= mid) { newLeftChild = update(prevNode->left, leftIdx, mid, targetIdx, newVal); } else { newRightChild = update(prevNode->right, mid + 1, rightIdx, targetIdx, newVal); } // Tính giá trị mới int valLeft = newLeftChild ? newLeftChild->value : 0; int valRight = newRightChild ? newRightChild->value : 0; return new Node(valLeft + valRight, newLeftChild, newRightChild);
} // Demo
int main()
{ vector<int> arr = {1, 3, 2, 5}; if (!arr.empty()) { Node* root = build(arr, 0, arr.size() - 1); roots.push_back(root); } int n = arr.size(); // Cập nhật giá trị tại chỉ số 1 thành 7 Node* new_root = update(roots.back(), 0, n - 1, 1, 7); roots.push_back(new_root); // In giá trị root mới cout << "New root value after update: " << new_root->value << endl; // Expect 1 + 7 + 2 + 5 = 15 return 0;
}

5.3. Nhìn Trộm Quá Khứ" (Truy Vấn - query)

Sau khi đã có các phiên bản được lưu trữ thông qua các nút gốc trong mảng roots, việc truy vấn trên một phiên bản cụ thể trở nên rất đơn giản.

Hàm query sẽ nhận đầu vào là:

• node: Nút gốc của phiên bản cây cần truy vấn (ví dụ, roots[v]).
• leftIdx, rightIdx: Khoảng chỉ số mà node hiện tại quản lý.
• queryLeft, queryRight: Khoảng chỉ số cần truy vấn.

Cách hoạt động của hàm query này giống hệt như hàm query trên một cây Segment Tree thông thường. Không có gì đặc biệt liên quan đến "tính bất biến" ở đây cả, vì chúng ta chỉ "đọc" thông tin từ một phiên bản đã được cố định.

Ví dụ (tiếp theo): Truy vấn tổng đoạn [0, 2] trên roots[0] (phiên bản ban đầu, mảng ảo [1, 3, 2, 5]): Kết quả sẽ là 1+3+2=6. Truy vấn tổng đoạn [0, 2] trên roots[1] (phiên bản sau khi arr[1] cập nhật thành 7, mảng ảo [1, 7, 2, 5]): Kết quả sẽ là 1+7+2=10.

Code minh họa (C++):

int query(Node* node, int currentLeft, int currentRight, int queryLeft, int queryRight)
{ if (node == nullptr || queryLeft > currentRight || queryRight < currentLeft) { return 0; // Không giao nhau } // Đoạn nằm hoàn toàn trong truy vấn if (queryLeft <= currentLeft && currentRight <= queryRight) { return node->value; } int mid = (currentLeft + currentRight) / 2; int sumLeft = query(node->left, currentLeft, mid, queryLeft, queryRight); int sumRight = query(node->right, mid + 1, currentRight, queryLeft, queryRight); return sumLeft + sumRight;
} int main()
{ vector<int> arr = {1, 3, 2, 5}; if (!arr.empty()) { Node* rootV0 = build(arr, 0, arr.size() - 1); roots.push_back(rootV0); } int n = arr.size(); // Cập nhật phần tử tại index 1 thành 7 Node* rootV1 = update(roots.back(), 0, n - 1, 1, 7); roots.push_back(rootV1); // Truy vấn đoạn [0, 2] trên phiên bản gốc (v0) int resultV0 = query(roots[0], 0, n - 1, 0, 2); cout << "Sum in version 0 (index 0-2): " << resultV0 << endl; // Expect 1 + 3 + 2 = 6 // Truy vấn đoạn [0, 2] trên phiên bản mới (v1) int resultV1 = query(roots[1], 0, n - 1, 0, 2); cout << "Sum in version 1 (index 0-2): " << resultV1 << endl; // Expect 1 + 7 + 2 = 10 return 0;
}

5.4. Độ Phức Tạp: "Phép Thuật" Của Chúng Ta Nhanh Đến Mức Nào?

Đây là lúc sức mạnh thực sự của PST được thể hiện rõ ràng. Bảng dưới đây tóm tắt độ phức tạp của các thao tác chính:

Việc phân tích bảng này cho thấy một sự đánh đổi quan trọng: để có được khả năng truy vấn lịch sử, chúng ta chấp nhận tốn thêm một lượng không gian bộ nhớ là $O(log N)$ cho mỗi thao tác cập nhật. Tuy nhiên, chi phí này thường là chấp nhận được, đặc biệt khi so sánh với chi phí $O(N)$ của việc sao chép toàn bộ cấu trúc dữ liệu ở mỗi bước. PST cung cấp một điểm cân bằng hiệu quả giữa không gian lưu trữ và khả năng truy cập lịch sử.

Nếu không có kỹ thuật "path copying", mỗi lần cập nhật sẽ đòi hỏi việc tạo ra một cây mới hoàn toàn, dẫn đến chi phí $O(N)$ cả về thời gian và không gian. Chính vì chỉ có khoảng $O(log N)$ nút trên đường đi từ gốc đến lá bị thay đổi giá trị trong một Segment Tree khi cập nhật một điểm, "path copying" chỉ cần tạo mới đúng số lượng nút này. Các nút còn lại được "trỏ" tới từ phiên bản cũ, giữ nguyên cấu trúc. Điều này trực tiếp dẫn đến độ phức tạp $O(log N)$ cho cả thời gian và không gian của thao tác update, làm cho PST trở thành một giải pháp khả thi và mạnh mẽ.

6. Học "Ma Thuật" Này Để Làm Gì? (Ứng Dụng Thực Tế & "Giải Case" Hay Ho)

Cây Phân Đoạn Bất Biến không chỉ là một cấu trúc dữ liệu "ngầu" trên lý thuyết mà còn là một công cụ cực kỳ hữu ích trong việc giải quyết nhiều bài toán thực tế và trong lập trình thi đấu.

6.1. Truy Vấn Dữ Liệu "Cổ Đại": "Điểm Cao Nhất Của Đội X Vào Thứ Ba Tuần Trước Là Bao Nhiêu?"

Đây là ứng dụng trực quan và cơ bản nhất của PST. Khi có một chuỗi các cập nhật dữ liệu theo thời gian (hoặc theo một thứ tự phiên bản nào đó), và anh em muốn biết thông tin tổng hợp (như tổng, min, max,...) của một đoạn dữ liệu cụ thể sau một số lần cập nhật nhất định, PST là một lựa chọn hoàn hảo.

Với PST, mỗi thao tác update sẽ tạo ra một con trỏ gốc mới, đại diện cho một phiên bản mới của cây. Nếu muốn truy vấn trạng thái của dữ liệu sau lần cập nhật thứ v, chỉ cần sử dụng con trỏ roots[v] để bắt đầu truy vấn.

Ví dụ "Đời Thường": Hãy tưởng tượng việc theo dõi giá cổ phiếu của một công ty qua các ngày giao dịch. Mỗi ngày, giá cổ phiếu có thể thay đổi (đây là một update). Nếu ban lãnh đạo muốn biết: "Giá trị trung bình của cổ phiếu XYZ trong tuần giao dịch đầu tiên của tháng 3 năm ngoái là bao nhiêu?", PST có thể giúp trả lời câu hỏi này một cách hiệu quả, với mỗi ngày giao dịch được xem như một phiên bản.

6.2. Giải Quyết Các Bài Toán "Hack Não" Trong Competitive Programming:

Đây là đấu trường mà PST thực sự tỏa sáng, giúp các lập trình viên giải quyết những bài toán phức tạp liên quan đến truy vấn lịch sử hoặc truy vấn trên nhiều phiên bản của dữ liệu.

• "Kinh Điển Của Kinh Điển": Tìm Phần Tử Nhỏ Thứ K Trong Một Đoạn (K-th Number) Bài toán này yêu cầu tìm giá trị nhỏ thứ k trong một đoạn con A[L...R] của mảng A. Ý Tưởng "Phiêu Lưu Cùng Nhà Sử Học Thời Gian": Hãy tưởng tượng mỗi phần tử A[i] của mảng là một "sự kiện" trong dòng lịch sử, và giá trị của A[i] là một "đặc điểm" của sự kiện đó. Anh em là một nhà sử học du hành thời gian, muốn nghiên cứu tần suất xuất hiện của các "đặc điểm" này qua các giai đoạn lịch sử khác nhau. Một cây PST được xây dựng, trong đó roots[i] đại diện cho cây Segment Tree ghi nhận tần suất xuất hiện của tất cả các giá trị từ A[0] đến A[i]. Cụ thể hơn, nếu các giá trị trong mảng A lớn, chúng thường được "nén" (coordinate compression) hoặc ánh xạ vào một khoảng nhỏ hơn. Sau đó, mỗi nút lá của cây ST trong roots[i] sẽ tương ứng với một giá trị (đã nén) và lưu số lần giá trị đó xuất hiện trong tiền tố A[0...i]. Để tìm phần tử nhỏ thứ K trong đoạn A[L...R], nhà sử học sẽ "so sánh" hai "cuốn biên niên sử": một cuốn ghi lại lịch sử đến thời điểm R (truy cập qua roots[R]) và một cuốn ghi lại lịch sử đến thời điểm L-1 (truy cập qua roots[L-1]). Sự khác biệt về số lượng phần tử được lưu trữ ở các nút tương ứng của hai cây này (ví dụ, count_R_left_child - count_L_minus_1_left_child) sẽ cho biết có bao nhiêu phần tử thuộc nhánh giá trị bên trái (các giá trị nhỏ hơn) nằm trong đoạn A[L...R]. Dựa vào số lượng này và giá trị K cần tìm, nhà sử học quyết định "hành trình" tiếp theo của mình sẽ đi vào nhánh con trái hay nhánh con phải của cả hai cây roots[R] và roots[L-1] (tương tự như cách hoạt động của thuật toán tìm kiếm nhị phân trên cây). Quá trình này lặp lại cho đến khi đến được nút lá, và giá trị (đã nén) tại nút lá đó chính là phần tử nhỏ thứ K cần tìm. Bài toán tìm phần tử nhỏ thứ K trên một đoạn [L, R] có thể được chuyển đổi một cách thông minh thành bài toán truy vấn trên "hiệu số" của hai cấu trúc tiền tố. Cây PST roots[i] lưu trữ thông tin (ví dụ, số lượng các giá trị đã xuất hiện) cho tiền tố A[0...i]. Bằng cách thực hiện truy vấn đồng thời trên roots[R] và roots[L-1], và xem xét sự chênh lệch số lượng ở các nút tương ứng, chúng ta có thể suy ra thông tin cần thiết cho chính đoạn A[L...R]. Kỹ thuật này, thường được thấy trong các hàm query(rootR, rootL, k), là một mẫu hình mạnh mẽ và phổ biến khi sử dụng PST.

• Đếm Số Phần Tử Khác Nhau Trong Một Đoạn (Distinct Elements in Range) Qua Các Phiên Bản: Bài toán này yêu cầu đếm số lượng giá trị duy nhất trong một đoạn [L, R] của mảng, có thể là trên một phiên bản cụ thể của mảng sau một loạt các cập nhật. Ý Tưởng "Thám Tử Điều Tra Dấu Vết": Hãy hình dung một dòng thời gian ghi lại các sự kiện, và tại mỗi sự kiện, một vật phẩm mới có thể xuất hiện. Anh em, trong vai một thám tử, muốn biết trong một khoảng thời gian [L, R] của một "kịch bản" (phiên bản) v nào đó, có bao nhiêu loại vật phẩm khác nhau đã lộ diện. Một cách tiếp cận là xây dựng PST sao cho roots[i] là cây ST cho tiền tố A[0...i]. Để đếm số phần tử khác nhau, với mỗi phần tử A[j] khi xây dựng roots[j], nếu A[j] đã xuất hiện trước đó tại vị trí p < j, chúng ta sẽ "vô hiệu hóa" sự đóng góp của A[j] tại vị trí p trong cây roots[j-1] và "kích hoạt" sự đóng góp của A[j] tại vị trí j để tạo ra roots[j]. Khi truy vấn trên đoạn [L, R] của phiên bản roots[v], chúng ta cần đếm số vị trí x trong khoảng [L, R] mà có giá trị "kích hoạt" (ví dụ, bằng 1).

Cách tiếp cận này minh chứng cho việc PST cho phép "biến đổi" trục thời gian của dữ liệu thành một chiều của cấu trúc dữ liệu. Trong nhiều bài toán, các truy vấn liên quan đến "phiên bản" hoặc "thời điểm" (ví dụ, trạng thái sau k lần cập nhật, hoặc giá trị tại thời điểm t). PST cho phép xem "thời gian" hoặc "số thứ tự phiên bản" như một chiều dữ liệu bổ sung. Bằng cách xây dựng một PST cho mỗi "thời điểm" (ví dụ, roots[i] là cây cho mảng sau i lần cập nhật), chúng ta có thể thực hiện truy vấn trên chiều không gian (đoạn [L, R]) tại một "thời điểm" cụ thể. Điều này được minh họa rõ ràng trong cách giải bài toán Range Queries and Copies trên CSES, nơi "chỉ số của mảng (phiên bản) được xem như chiều thời gian".

6.3. Vài "Bí Kíp Gia Truyền" (Chém Gió Nâng Cao - Tùy Chọn, Nếu Anh Em Thích "Hardcore")

Khi đã nắm vững những kiến thức cơ bản về Cây Phân Đoạn Bất Biến, anh em có thể khám phá thêm một vài "chiêu thức" nâng cao để giải quyết những bài toán phức tạp hơn.

• Lazy Propagation (Truyền Lười) Với PST: Khi "Lười" Cũng Là Một Nghệ Thuật Trong Segment Tree thông thường, Lazy Propagation là một kỹ thuật hiệu quả để xử lý các cập nhật trên cả một đoạn (range update) thay vì chỉ một điểm (point update). Câu hỏi đặt ra là: liệu có thể kết hợp Lazy Propagation với PST để thực hiện range update trên các phiên bản lịch sử không? Câu trả lời là có, nhưng cần sự cẩn trọng. Cảnh Báo "Hack Não": Việc triển khai Lazy Propagation trên PST phức tạp hơn đáng kể so với ST thông thường. Nguyên nhân là vì khi "đẩy" (push down) các lazy tag từ một nút cha xuống các nút con, chúng ta cũng phải tuân thủ nguyên tắc bất biến. Điều này có nghĩa là các nút con (và có thể cả các nút cháu) bị ảnh hưởng bởi lazy tag cũng phải được tạo mới (thông qua path copying) để không làm thay đổi các phiên bản cũ mà nút cha đang thuộc về. Tuy nhiên, một khi đã làm chủ được kỹ thuật này, anh em sẽ sở hữu một công cụ cực kỳ mạnh mẽ. Phép Tương Đồng "Sổ Lệnh Chưa Thi Hành Của Sử Quan Lười Biếng": Hãy tưởng tượng mỗi "Sử Quan Thời Gian" (thuật toán update) đôi khi cảm thấy lười biếng không muốn cập nhật chi tiết từng trang một cho cả một chương lớn trong "Biên Niên Sử Hoàng Gia" khi có một sắc lệnh ảnh hưởng đến toàn bộ chương đó. Thay vào đó, Sử Quan sẽ ghi một "lệnh tổng" (lazy tag) vào đầu chương đó. Lệnh này ghi rõ rằng "Tất cả các trang trong chương này cần được cộng thêm X". Khi một người đọc (thao tác query) muốn xem chi tiết một trang cụ thể trong chương đó, Sử Quan mới kiểm tra: "À, chương này có một lệnh tổng chưa thi hành!". Lúc này, Sử Quan mới thực sự áp dụng lệnh đó cho trang đang được đọc và các trang liên quan (tạo ra các bản sao mới của những trang này nếu cần thiết để đảm bảo các phiên bản cũ không bị ảnh hưởng), đồng thời truyền lệnh xuống các tiểu mục nhỏ hơn trong chương. Việc kết hợp Lazy Propagation với PST đòi hỏi sự tỉ mỉ trong việc tạo nút mới. Khi một nút có lazy tag cần được "đẩy" xuống các nút con, các nút con đó (nếu bị ảnh hưởng) cũng phải được tạo mới thông qua path copying. Điều này đảm bảo rằng phiên bản hiện tại không làm thay đổi phiên bản cũ mà nút cha đang thuộc về. Mặc dù làm tăng độ phức tạp của việc cài đặt, kỹ thuật này mở rộng đáng kể khả năng của PST, cho phép thực hiện các cập nhật đoạn trên nhiều phiên bản lịch sử một cách hiệu quả.

• PST Trên Cây (Persistent Segment Tree on Tree): "Leo Cây" Xuyên Thời Gian Sức mạnh của PST không chỉ giới hạn ở việc xử lý các mảng một chiều. Nó hoàn toàn có thể được điều chỉnh để hoạt động trên cấu trúc cây, cho phép trả lời các truy vấn phức tạp trên đường đi giữa hai nút bất kỳ, và tất nhiên, các phiên bản khác nhau của cây (sau mỗi lần cập nhật giá trị nút chẳng hạn) cũng có thể được lưu lại. Kỹ thuật này thường được kết hợp với việc tìm Tổ Tiên Chung Gần Nhất (Lowest Common Ancestor - LCA) để xác định đường đi giữa hai nút. Ví dụ ứng dụng: Tìm phần tử nhỏ thứ K trên đường đi từ nút u đến nút v trong một cây, sau một loạt các thay đổi giá trị trên các nút của cây đó. Bản chất của Segment Tree là khả năng chia một cấu trúc lớn thành các phần nhỏ hơn để quản lý. Đối với mảng, đó là các đoạn con. Đối với cây, đó có thể là các đường đi (paths) hoặc các cây con (subtrees). Khi kết hợp với nguyên lý bất biến, PST trên cây cho phép thực hiện các truy vấn trên đường đi (path queries) qua nhiều "phiên bản" khác nhau của cây. Đây là một kỹ thuật rất mạnh mẽ, thường xuất hiện trong các bài toán đồ thị có độ phức tạp cao, nơi mà trạng thái của cây thay đổi theo thời gian và cần truy vấn thông tin lịch sử trên các đường đi.

7. Lời Kết: "Triển" Thôi Chờ Chi! (Go Forth and Persist!)

Qua cuộc hành trình vừa rồi, hy vọng rằng Cây Phân Đoạn Bất Biến (PST) không còn là một khái niệm xa lạ hay "khó nhằn" nữa đối với anh em. Nó không chỉ là một cấu trúc dữ liệu với cái tên "ngầu lòi" mà thực sự là một công cụ cực kỳ mạnh mẽ, một "bảo bối" giúp giải quyết vô số bài toán hóc búa liên quan đến việc truy vấn dữ liệu lịch sử và quản lý các phiên bản khác nhau của dữ liệu. PST là minh chứng cho sự kết hợp hoàn hảo giữa hiệu quả tính toán của Segment Tree và sự linh hoạt, khả năng "lưu giữ ký ức" của tính bất biến.

Giờ đây, khi đã được trang bị những "kiến thức tối thượng" về PST, đừng ngần ngại thử thách bản thân! Hãy tìm đến các bài tập trên những nền tảng lập trình thi đấu như TopCoder, Codeforces, SPOJ, hoặc tự mình "chế" ra vài bài toán "hack não" để rèn luyện kỹ năng sử dụng "phép thuật" này.

Và cuối cùng, một lời kêu gọi đầy dí dỏm: "Anh em đã sẵn sàng trở thành một Time Lord của thế giới dữ liệu chưa? Hãy nhớ, với PST, quá khứ luôn nằm trong tầm tay anh em (miễn là anh em có đủ RAM!). Chúc may mắn và code thật vui!"

Nếu thấy bài viết này hữu ích, đừng quên "commit" một lượt thích và "push" nó cho bạn bè cùng "clone" về học nhé! Còn nếu phát hiện "bug" ở đâu đó trong bài, cứ thoải mái "create issue", biết đâu những góp ý đó lại giúp "merge" được những ý tưởng tuyệt vời hơn thì sao!