Trong phần này, chúng ta sẽ xem cây phân đoạn là gì. Trước khi thảo luận về vấn đề đó, chúng ta hãy xem một vấn đề.
Giả sử chúng ta có một mảng arr [0,…, n-1], Chúng ta có thể thực hiện các phép toán sau -
-
Tìm tổng các phần tử từ chỉ số l đến r, trong đó 0 ≤ l ≤ r ≤ n-1
-
Thay đổi giá trị của một phần tử được chỉ định của mảng thành một giá trị mới x. Chúng ta cần làm arr [i] =x. Chữ i trong phạm vi từ 0 đến n - 1.
Chúng ta có thể giải quyết vấn đề này bằng cách sử dụng cây Phân đoạn. Cây phân đoạn có thể giúp chúng ta lấy tổng và truy vấn trong thời gian O (log n). Vì vậy, hãy để chúng tôi xem cách thể hiện điều này -
-
Các nút lá là các phần tử của mảng đã cho
-
Mỗi nút bên trong đại diện cho một số hợp nhất của các nút lá. Việc hợp nhất có thể khác nhau trong các trường hợp khác nhau. Ở đây hợp nhất là tổng các lá dưới một nút.
Giả sử chúng ta có một mảng như [1, 3, 5, 7, 9, 11]. Vì vậy, cây phân đoạn sẽ là
