9-step walkthrough. range_set(2,5) rồi range_sum(3,6)=3. Node pop-in khi allocate, lazy badge cam khi lazy=1. ← → nav, Space play/pause.
STEP 1 — INIT
Cây sparse: chỉ root $[0,7]$ được cấp phát. Tất cả 14 node còn lại chưa tồn tại (mờ). Tổng cây chín = 0.
Gọi $\texttt{range\_set}([2,5])$ từ root. $[0,7]$ không nằm trọn trong $[2,5]$ → phải push_down và recurse xuống 2 con.
push_down ở root tạo 2 con $L=[0,3]$ và $R=[4,7]$ (cả 2 đều rỗng, $\text{lazy}=0$). Giờ recurse vào từng con.
Ở $L=[0,3]$: $LL=[0,1]$ rời với $[2,5]$ → skip. $LR=[2,3]$ nằm trọn → treo lazy=1, freq=2, dừng. KHÔNG đi xuống lá.
Ở $R=[4,7]$: $RL=[4,5]$ nằm trọn → treo lazy=1, freq=2. $RR=[6,7]$ rời → skip. Cả update chỉ chạm 5 node mới.
Recompute từ dưới lên: $L.\text{freq}=2$, $R.\text{freq}=2$, $\text{root}.\text{freq}=4$. Lazy vẫn còn ở $[2,3]$ và $[4,5]$ — món nợ chờ push xuống.
Gọi $\texttt{range\_sum}([3,6])$ từ root. $[0,7]$ không trọn trong $[3,6]$ → recurse xuống $L$ và $R$.
Ở $L$: $[0,1]$ skip. $[2,3]$ không trọn → push_down: lazy=1 truyền xuống $[2,2]$ và $[3,3]$ vừa sinh ($\text{freq}=1$ mỗi node). Lazy "trả nợ".
Node đóng góp: $[3,3]=1$, $[4,5]=2$, $[6,6]=0$. Tổng $=1+2+0=3$. Cây cuối có 11 node thay vì full 15 — sparse!