Xem Segment Tree. Trước hãy xem bài toán: mảng arr[0…n-1], hai thao tác:
- Tìm tổng phần tử từ chỉ số l đến r (0 ≤ l ≤ r ≤ n-1).
- Cập nhật arr[i] = x (0 ≤ i ≤ n-1).
Segment Tree giải quyết cả hai trong O(log n). Biểu diễn:
- Nút lá = phần tử mảng.
- Nút nội = hợp nhất (merge) các lá dưới nó. Ở đây hợp nhất = tổng.
Ví dụ mảng [1, 3, 5, 7, 9, 11]. Segment tree:
