Тут можно обойтись тем же B-tree. В запросе x-y нам нужно найти значение x
а потом идти по списку.
Из того же списка en.wikipedia.org/wiki/B%2B_tree
Performing a range query with k elements occurring within the range requires O(log bn + k) operations
а потом идти по списку.
Из того же списка en.wikipedia.org/wiki/B%2B_tree
Performing a range query with k elements occurring within the range requires O(log bn + k) operations
чтобы посчитать количество нужно будет хранить пару чисел в узлах
stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way/2329236#2329236
Это конечно всё теория оторванная от реальности.