## 2-d extension of interval trees?

Moderator: Board moderators

Future
New poster
Posts: 2
Joined: Fri Nov 21, 2003 5:33 pm

### 2-d extension of interval trees?

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
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

### Re: 2-d extension of interval trees?

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
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

### Re: 2-d extension of interval trees?

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 2-d extension of interval trees?

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.