Count number of overlapping intervals under memory constraints?

I need to maintain a list of intervals in the form of tuple (x, y) and answer queries which ask for the total number of intervals overlapping a point p. If there is no memory constraint i think the efficient solution 开发者_C百科would be to use a segment tree which requires O(nlogn) space by storing additional information in each node and using lazy update technique.

I tried to do it using an interval tree but the query's runtime depends on the number of reported intervals.

Can we do something better than this under memory constraints?

A better solution is Fenwick Trees (also known as binary index trees), which have the restriction that you can either update a range and query a point or update a point and query a range. Since you update ranges and query a point a Fenwick Tree is a good solution.

They have O(log N) lookup and use O(N) space, where N is the range of x and y. Additionally updates are O(log N) too.

Best of all is they are trivial to code. Much more trivial than Segment Trees.

Here is a great tutorial: TopCoder - Binary Index Trees