Skip to content

Instantly share code, notes, and snippets.

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

Embed
What would you like to do?
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?

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 |
@kagan94

This comment has been minimized.

Copy link

commented Oct 2, 2016

What do the reported results (k) mean?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.