Bài viết là bản dịch của: https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/
Có rất nhiều bài toán yêu cầu thực hiện các truy vấn trên các đoạn, dãy số, các tập giá trị. Có thể kể đến như: “Tính tổng tất cả phần tử trong mảng từ vị trí l đến r“, hoặc “tìm phần tử bé nhất trong mảng từ vị trí l đến r“. Các bài toán như vậy có thể dễ dàng xử lí bằng các CTDL mạnh, trong đó có Segment Tree (Cây phân đoạn).
Segment Tree là gì ?
Segment Tree (Cây Phân Đoạn) là một cây nhị phân được dùng để lưu các phân đoạn, khoảng. Với mỗi nút của cây sẽ thể hiện một khoảng.
Ví dụ xét một mảng A có N phần tử và một Cây phân đoạn T:
- Gốc của cây T sẽ biểu diễn cả mảng A[0:N-1]
- Mỗi lá của cây T sẽ biểu diễn 1 phần tử nhỏ A[i] với 0 <= i < N
- Mỗi nút khoảng của cây T biển diễn một khoảng tập hợp nhiều phần tử nhỏ A[i:j] với O <= i < j < N
Gốc của cây T biểu diễn cả mảng A[0:N-1]. Sau đó ta sẽ chia khoảng này thành 2 phần và nó sẽ là 2 nút con của gốc biểu diễn A[0:(N-1)/2] và A[(N-1)/2 + 1:(N-1)]. Các bước tiếp theo ta tiếp tục chia đôi khoảng này và tạo thành 2 nút con của nút đó và lặp lại.
Chiều cao của cây sẽ là Log(2,N) Có N lá biểu diễn N phần tử của mảng. Và số lượng nút là N – 1. Do đó tổng số lượng nút là 2*N – 1.
Sau khi đã xây dựng xong cây phân đoạn thì chúng ta không thể thay đổi cấu trúc của nó nữa. Cấu trúc của cây sẽ là cấu trúc tĩnh. Ta có thể cập nhật giá trị ở các nút nhưng không thể thay đổi cấu trúc của nó. Các thao tác trên Segment Tree thường được sử dụng bằng đệ quy, và có tính thuần đệ quy. Do có tính đệ quy tự nhiên, Segment Tree rất dễ cài đặt. Segment Tree cho ta hai thao tác chính
- Cập nhật (Update): Thao tác này sẽ cập nhật một phần tử hoặc một khoảng trên mảng
- Truy vấn (Query): Thao tác này sẽ lấy dữ liệu một khoảng hoặc một phần tử trên cây
Cài đặt
Vì Segment Tree là một cây nhị phân, ta có thể sử dụng một mảng tuyến tính một chiều để biểu diễn Segment Tree. Trong đa số các bài toán cần sử dụng Segment Tree, ta cần phải nghĩ “Làm sao để lưu nó trong một Segment Tree” ?
Ví dụ: Ta cần tìm tổng của toàn bộ phần tử trong mảng từ vị trí l đến r, thì với mỗi nút, ta sẽ lưu tổng của các con của chúng. Nếu ta cần tìm phần tử nhỏ nhất trong mảng từ vị trí l đến r, thì với mỗi nút (trừ nút lá), ta sẽ lưu phần tử nhỏ nhất của nút con của chúng.
Khi ta đã biết cần lưu cái gì trong một Segment Tree, ta có thể bắt đầu cài đặt cây bằng phương pháp đệ quy (từ dưới lên). Ta sẽ đi từ những nút lá và đi về gốc và cập nhật các thay đổi trên đường từ lá đến gốc. Lá sẽ chỉ biểu diễn một phần tử nhỏ. Ở mỗi bước ta sẽ ghép hai nút con thành một nút cha biểu diễn một khoảng. Việc ghép các nút con sẽ khác nhau ở các bài toán khác nhau. Và phần tử gốc sẽ biểu diễn cả mảng.
Để cập nhật (update), ta đơn giản chỉ cần tìm nút lá chứa phần tử đó để cập nhật. Điều này có thể dễ dàng thực hiện bằng cách chọn đi sang trái hoặc phải tùy theo các nút chứa khoảng có chứa phần tử con đó không. Khi ta đã tìm nút lá , ta sẽ cập nhật lại theo cách từ dưới lên từ lá đó lên ngọn.
Để thực hiện truy vấn trên Segment Tree từ l đến r. Ta sẽ đệ quy từ gốc và kiểm tra xem có một khoảng nào hoàn toàn thuộc từ l đến r không. Nếu có một nút chứa đúng khoảng l – r, ta sẽ trả về giá trị nút đó. Ví dụ một mảng có 7 phần tử.
Sẽ dễ hiểu hơn với một vài ví dụ. Cho một mảng A có N phần tử và vài truy vấn. Có 2 kiểu truy vấn sau:
- Update (Cập nhật): Tăng một phần tử ở vị trí idx một giá trị val
- Query (Truy vấn): Lấy tổng từ L đến R sao cho 0 <= l <= r < N
Thuật toán ngây thơ:
Đây là một cách tiếp cận đơn giản nhất. Với truy vấn lấy tổng, ta sẽ chạy một vòng lặp từ l đến r để lấy tổng với độ phức tạp O(N). A[idx] += val sẽ cập nhật giá trị một phần tử với độ phức tạp O(1). Thuật toán này khá tốt nếu các thao tác cập nhật có nhiều và có rất rất ít thao tác lấy tổng.
Thuật toán ngây thơ 2:
Ở hướng này ta sẽ tính và lưu trước một mảng cộng dồn. Với mỗi truy vấn lấy tổng ta chỉ cần trả về (sum[r] – sum[l-1]) với độ phức tạp O(1). Nhưng để cập nhật, ta sẽ cần sửa lại giá trị của cả mảng cộng dồn với độ phức tạp O(N). Thuật toán này sẽ tốt nếu số lượng truy vấn có nhiều và có rất rất ít thao tác cập nhật.
Sử dụng Segment Tree:
Giờ hãy xem ta sẽ sử dụng Segment Tree như thế nào cho bài toán này. Như chúng ta đã biết mỗi nút sẽ biểu diễn một khoảng hoặc một đoạn. Ở bài toán này ta cần tìm tổng của toàn bộ phần tử trong một khoảng cho trước. Vậy ở mỗi nút ta sẽ cần lưu tổng của toàn bộ phần tử trong khoảng và được biểu diễn trong một nút. Để làm điều này, ta sẽ xây dựng một cây phân đoạn sử dụng đệ quy (từ dưới lên) như giải thích bên trên. Mỗi nút lá sẽ có một phần tử duy nhất. Tất cả nút khoảng sẽ là tổng của các nút con của chúng.
Như code bên trên ta sẽ đi từ nút gốc và đệ quy để xây dựng các nút con trái phải cho đến khi gặp phải nút lá Từ nút lá ta sẽ đệ quy ngược về gốc và cập nhật các nút trên đường đi. Biến node thể hiện nút ta đang làm việc. Vì cây phân đoạn là một cây nhị phân, 2*node biểu diễn nút ở bên trái và 2*node + 1 biểu diễn nút phải. start và end thể hiện khoảng l và r biểu diễn bằng nút. Độ phức tạp để xây dựng là O(N).
Để cập nhật một phần tử, ta cần vào khoảng mà phần tử đang bên trong và đệ quy tiếp tục sang trái hoặc phải
.Độ phức tạp của thao tác cập nhật sẽ là O(logN).
Để truy vấn trên một khoảng, ta cần đảm bảo 3 điều kiện:
- Khoảng biểu diễn bởi nút nằm hoàn toàn trong khoảng cần tìm
- Khoảng biểu diễn bởi nút nằm ngoài trong khoảng cần tìm
- Khoảng biểu diễn bởi nút nằm một phần bên trong và một phần bên ngoài khoảng cần tìm
Trong trường hợp khoảng của nút nằm ngoài khoảng cần tìm, ta chỉ cần return 0. Nếu khoảng đó nằm hoàn toàn trong khoảng cần tìm, ta chi cần trả về giá trị của nút là tổng của toàn bộ phần tử trong khoảng được biểu diễn bởi bởi nút. Và nếu khoảng được biểu diễn bởi nút nằm một phần trong khoảng cần tìm, ta trả về tổng của nút con trái và nút con phải.
=> Độ phức tạp của truy vấn là O(logN)
Cập nhật một khoảng (Lazy Propagation – Lan truyền lười biếng):
Đôi khi bài toán đặt bạn cần cập nhật một khoảng từ l đến r, thay vì chỉ cập nhật một phần tử. Một phương pháp là cập nhật toàn bộ phần tử từng cái một bằng một vòng lặp, điều này sẽ tốn O(NlogN) thời gian.
Để tránh gọi quá nhiều lần hàm cập nhật, ta có thể sửa đổi lại cách cập nhật một khoảng.
Hãy chỉ làm việc gì đó khi nó cần thiết. Khi cập nhật một khoảng, ta sẽ cập nhật nút và đánh giá các nút con của nó là nó cần cập nhật, và chỉ cập nhật khi cần. Để làm điều này ta cần một mảng lazy[] cùng cỡ với Segment Tree. Mặc địch mọi phần tử của mảng lazy[] đều là 0 thể hiện không có nút nào cần cập nhật. Nếu có một phần tử khác không, lazy[k] là phần tử cần cập nhật, và ta cần cập nhật nút k trong cây nhị phân trước khi làm bất kì truy vấn nào.
Ta cần bảo đảm 3 điều sau:
- Nếu nút hiện tại cần cập nhật, ta cần cập nhật trước nút con nào đó
- Nếu khoảng hiện tại của nút hiện tại nằm hoàn toàn trong khoảng cần cập nhật, thì cập nhật luôn và cập nhật lazy[] cho các nút con
- Nếu khoảng của nút hiện tại chồng lấn với khoảng cần tìm, cập nhật nút như cách cập nhật phía trước.
Vì ta đã cập nhật hàm update để trì hoãn việc cập nhật giá trị, chúng ta cần thay đổi cả hàm truy vấn. Điều duy nhất cần thay đổi là nếu có các thao tác cập nhật nào còn chưa thực hiện, ta cần kiểm tra và cập nhật chúng trước.