What are the differences between segment trees, interval trees, binary indexed trees and range trees?

Stack Overflow: http://stackoverflow.com/questions/17466218/what-are-the-differences-between-segment-trees-interval-trees-binary-indexed-t/34699478

One Dimension

k is the number of reported results

	Segment	Interval	Range	Indexed
Preprocessing	n logn	n logn	n logn	n logn
Query	k+logn	k+logn	k+logn	logn
Space	n logn	n	n	n
Insert/Delete	logn	logn	logn	logn

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |        n logn |     n logn |         n logn |    n logn |
|Query         |        k+logn |     k+logn |         k+logn |      logn |
|Space         |        n logn |          n |              n |         n |
|              |               |            |                |           |
|Insert/Delete |          logn |       logn |           logn |      logn |

Higher Dimensions

d > 1

	Segment	Interval	Range	Indexed
Preprocessing	n(logn)^d	n logn	n(logn)^d	n(logn)^d
Query	k+(logn)^d	k+(logn)^d	k+(logn)^d	(logn)^d
Space	n(logn)^(d-1)	n logn	n(logn)^(d-1))	n(logn)^d

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |     n(logn)^d |     n logn |      n(logn)^d | n(logn)^d |
|Query         |    k+(logn)^d | k+(logn)^d |     k+(logn)^d |  (logn)^d |
|Space         | n(logn)^(d-1) |     n logn | n(logn)^(d-1)) | n(logn)^d |