Example 04 — Segment tree query output

6-step walkthrough. Phím ← →, click Play, scrub bằng Next/Prev.

query sum(1, 4) = ? [0,5] 24 [0,2] 8 [3,5] 16 [0,1] 7 [2,2] 1 [3,4] 13 [5,5] 3 [0,0] 2 [1,1] 5 [3,3] 4 [4,4] 9 02 15 21 34 49 53
Step 1 / 6

STEP 1 — INITIAL

Array $a = [2, 5, 1, 4, 9, 3]$. Truy vấn $\text{sum}(1, 4) = ?$

Tại gốc $[0,5]$, đoạn $[1,4]$ giao một phần → đệ quy xuống cả hai con.

Xuống $[0,2]$: $[1,1]$ phủ hoàn toàn → lấy 5; $[2,2]$ → lấy 1; $[0,0]$ ngoài khoảng → bỏ qua.

Xuống $[3,5]$: $[3,4]$ phủ hoàn toàn → lấy 13; $[5,5]$ bỏ qua.

Ba nút đóng góp: $[1,1]$, $[2,2]$, $[3,4]$. Đây là lý do $O(\log n)$.

Kết quả: $5 + 1 + 13 = 19$. Cây 11 nút, chỉ đọc 3 nút.