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

readme.md

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 |

What do the reported results (k) mean?