Tutorial — Tổng Đoạn

Biến đổi tổng đoạn con từ chỉ số $i$ đến $j$ thành hiệu hai tiền tố $P_j - P_{i-1}$ với mảng cộng dồn $P$. Điều kiện tổng nằm trong $[L, R]$ tương đương với bất đẳng thức $P_j - R \le P_{i-1} \le P_j - L$.

Khi cố định chỉ số kết thúc $j$, ta cần đếm số lượng giá trị $P_k$ với $0 \le k < j$ thuộc đoạn $[P_j - R, P_j - L]$. Vì giá trị $P_k$ có thể rất lớn, việc ánh xạ các giá trị này về tập chỉ số nhỏ hơn là điều bắt buộc.

Sử dụng kỹ thuật rời rạc hóa trên tập các giá trị $P_k$, $P_j - R$ và $P_j - L$. Sau đó, duy trì tần suất các $P_k$ đã duyệt bằng cây Fenwick Tree để thực hiện truy vấn đếm trong đoạn với độ phức tạp $O(\log n)$ mỗi bước.