2-d extension of interval trees?

[Future]

Let's think of a scenario in 2-d plane: we have n points, whose coordinates are all integers within the range [1,n]. Each point can store a number. I can add/substract numbers at each point. I might also draw a rectangle and ask the sum of all numbers storing at the points inside this rectangle.

Can we design a data structure to make all the operations logn? or (logn)^2 is the optimal solution?

Thanks!

[fushar]

Hmm....
I think you can create an array of interval (segment) trees, and a query takes O(num_of_interval_trees * log n).
The easiest way is to use 2D BIT. Please take a look to this tutorial: http://www.topcoder.com/tc?module=Stati ... dexedTrees

[maxdiver]

I think, only (logn)^2.
We create interval tree for X coordinates, where each vertex of this tree is an interval tree for Y coordinates.

[mf]

If value at each point doesn't change, then you can use fractional cascading to improve query time from O(log^2 n) to O(log n).
But I'm not sure if it can be used if points' values can change.