The segment tree is a nice data structure that often appears in programming contests. However, outside the contest world the segment tree seems to be unknown:
- There is no Wikipedia article about it (there is an article but it describes another data structure).
- I haven't seen any algorithm textbook that mentions it.
- I haven't found scientific papers that describe it.
So can you explain why the segment tree is so unknown? Or do you know sources outside the contest world?
Maybe, simply because it is useless outside programming contests and it has no application in real world?
However, I think I have seen somewhere that it is used deeply in the heart of Linux...
On the other hand, lack of real world applications has not prevented other data structures from being described in the literature. :)
If you think about it, a segment tree really is nothing special. It's just a balanced binary search tree with an implicit order defined by the element ranks. Its structure is static, a fact that makes it unuseful for many real-world applications, but more often than not one can use a self-balancing binary search tree instead and solve the same kinds of queries with only a little bit more work.
So whenever somebody will write about what you would call a segment tree, he or she is likely to refer to it as an augmented binary search tree or even a more abstract description like order-statistic tree.
By the way, the Wikipedia-version of a segment tree is just a generalization of the version of segment trees typically found in competitive programming: If you store only intervals of length 1, it's exactly the same.
As for examples:
Good points. However, there are many data structures that are "just" binary tree variations but still described in the literature. For example, the binary heap is also a static binary tree with simple operations — but it is included in every textbook.
In addition, many other techniques are also simple — like binary search, depth-first search, and merge sort — but everybody knows their names.
I didn't say segment trees are "just some kind of binary tree".
What I'm saying is that a segment tree is exactly a balanced binary search tree, so this is what people are likely to use to refer to it. Balanced binary search trees appear in hundreds of variations and augmentations in various publications.
A binary heap is something entirely different from a binary search tree, so I don't see the analogy here.
Why do you say Wiki article is about another structure? From what I read it is about somewhat generalized, but still same structure
There is an article about segment tree on e-maxx;
I think due to the fact that it is of no use that I know of. I am aware of a few data structures which are used though, like KD Tree (an ex-colleague of mine used it extensively for his geofencing application), bloom filter (for fast real time search) etc which are useful but serves no purpose in competitive programming world.