Hacker News Reader

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/chromiu...

View on HN

I 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.

Got 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.

I 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.

Reply on news.ycombinator.com