Hello.

I have an array of numbers from 1 to N. The order is random. I have to answer a lot(M) of questions like: how many numbers from interval [x, y] bigger than k. I tried to build two-dimensional interval tree: each edge of interval tree has an internal tree. But that tree was too large.

1 <= N, M <= 100000
Memory limit = 64 Mb

Also I tried to build Fenwick tree. But it also needs too much memory: O(N^2).

Please, can you help me to compress an interval tree or Fenwick tree? Or, maybe, there is another way to solve this problem?

Thank you.

You can store in each node of interval tree sorted list of numbers in corresponding interval. It requires O(n log n) memory and can be built in O(n log n) time (you can merge two sorted lists in linear time). With this tree you can answer queries in O(log^2 n) time using binary search

Edited by author 10.11.2009 02:42

Thank you! It really works :)