Trước hết tính tổng các số từ 1 đến n với f[i] = a[1]+a[2]+…+a[n]

Nhận xét tại vị trí j cần tìm vị trí i (i <= j) sao cho

l <= f[j]-f[i-1] <= r => f[j]-r <= f[i-1] <= f[j]-l với 1 <= i <= j hay cần đếm số lượng vị trí i sao cho:

• f[j]-r <= f[i] <= f[j]-l
• 0 <= i < j

Thấy vậy, ta dùng BIT để đếm số lượng các số trước đó thỏa điều kiện trên. Nhận xét là nó bị kẹp nên ta dùng phần bù : chỉ việc lấy số lượng các số <= f[j]-l trừ đi số lượng các số < f[j]-r thì ta sẽ được phần cần tìm.

Vậy tạo một BIT để đếm, nhưng số lớn (10^9 và hơn thế nữa) nên ta cần nén số lại, những số ta dùng hay nói cách khác là cập nhật và lấy giá trị là f[i]. Ta cho vào một mảng rồi sort lại, đẩy vào một mảng mới tương ứng mỗi giá trị sẽ có một thứ tự 1 2 3… trên BIT. Ta sẽ ánh xạ tương ứng mỗi giá trị trên BIT là các f[i] thành các giá trị là vị trí trên mảng đã sort. Lưu ý BIT chỉ hoạt động với index bắt đầu là 1. Để thực hiện ánh xạ này, ta chặt nhị phân trên mảng đã sort nói trên và cộng 1 cho vị trí tìm được nếu mảng sort là index-0.