StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>All these data structures are used for solving different problems:</p> <ul> <li><strong>Segment tree</strong> stores intervals, and optimized for "<em>which of these intervals contains a given point</em>" queries.</li> <li><strong>Interval tree</strong> stores intervals as well, but optimized for "<em>which of these intervals overlap with a given interval</em>" queries. It can also be used for point queries - similar to segment tree. </li> <li><strong>Range tree</strong> stores points, and optimized for "<em>which points fall within a given interval</em>" queries.</li> <li><strong>Binary indexed tree</strong> stores items-count per index, and optimized for "<em>how many items are there between index m and n</em>" queries.</li> </ul> <p>Performance / Space consumption for one dimension:</p> <ul> <li><strong>Segment tree</strong> - O(n logn) preprocessing time, O(k+logn) query time, O(n logn) space</li> <li><strong>Interval tree</strong> - O(n logn) preprocessing time, O(k+logn) query time, O(n) space</li> <li><strong>Range tree</strong> - O(n logn) preprocessing time, O(k+logn) query time, O(n) space</li> <li><strong>Binary Indexed tree</strong> - O(n logn) preprocessing time, O(logn) query time, O(n) space</li> </ul> <p>(k is the number of reported results).</p> <p>All data structures can be dynamic, in the sense that the usage scenario includes both data changes and queries:</p> <ul> <li><strong>Segment tree</strong> - interval can be added/deleted in O(logn) time (see <a href="http://3glab.cs.nthu.edu.tw/~spoon/courses/CS631100/Lecture05_handout.pdf">here</a>)</li> <li><strong>Interval tree</strong> - interval can be added/deleted in O(logn) time</li> <li><strong>Range tree</strong> - new points can be added/deleted in O(logn) time (see <a href="http://www.cs.unb.ca/tech-reports/documents/TR95_100.pdf">here</a>)</li> <li><strong>Binary Indexed tree</strong> - the items-count per index can be increased in O(logn) time</li> </ul> <p>Higher dimensions (d>1):</p> <ul> <li><strong>Segment tree</strong> - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1)) space</li> <li><strong>Interval tree</strong> - O(n logn) preprocessing time, O(k+(logn)^d) query time, O(n logn) space</li> <li><strong>Range tree</strong> - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1))) space</li> <li><strong>Binary Indexed tree</strong> - O(n(logn)^d) preprocessing time, O((logn)^d) query time, O(n(logn)^d) space</li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload