Segment Tree — Range Sum Query

Thử: update một phần tử — chỉ các node trên đường lá→gốc thay đổi (O(log n)); query [L..R] cũng chỉ ghép vài đoạn phủ.

L = R =
Mảng gốc:
Node xanh: bị duyệt qua. Node xanh đậm: nằm trọn trong khoảng truy vấn, lấy giá trị trực tiếp.