Instantly share code, notes, and snippets.

# ianchanning/readme.md Last active Nov 24, 2018

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

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

### 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 |
``````

### kagan94 commented Oct 2, 2016

 What do the reported results (k) mean?