3 ms·
I see segment tree in the catalog. This one is really popular in competitive programming. There are various techniques with segment tree in solving data structu
by limoce 5y ago
I see segment tree in the catalog. This one is really popular in competitive programming. There are various techniques with segment tree in solving data structure problems. However I did never see it in real industry project code. I once saw splay tree in Chromium[1] and FreeBSD but segment tree is rare. I wonder whether segment trees are actually practical?
[1] https://chromium.googlesource.com/v8/v8/+/refs/heads/chromium/3692/src/splay-tree.h https://chromium.googlesource.com/v8/v8/+/refs/heads/chromiu...
- hansworst 5y agoI may be misunderstanding the Wikipedia description on segment trees, but it feels like this is basically what bounding volume hierarchies are used for in computer graphics.
- limoce 5y agoGot it. I think BVHs are similar to interval trees instead. But after I searched through related data structures, I found that the structure of segment trees is similar to that of octrees. Segment trees look like basically 1-D version of octrees.
- mihaic 5y agoI once had to reverse engineer a geo IP database file from their source code, and I saw they were using a segment tree to map IP ranges to a location.