pllk's blog

Why is the segment tree unknown outside contests?
By pllk, 11 years ago, In English

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?

  • Vote: I like it
  • +45
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    On the other hand, lack of real world applications has not prevented other data structures from being described in the literature. :)

    → Reply
»
11 years ago, # |
← Rev. 11   Vote: I like it +26 Vote: I do not like it

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:

  • Range trees are an example of a data structure that essentially has the exact same structure as a typical segment tree in competitive programming: http://en.wikipedia.org/wiki/Range_tree
  • Similar concepts are also used in parallel algorithms to achieve a logarithmic computation depth, for example to compute the sum of an array in time and O(N) work.
  • In the original link-cut tree paper, splay trees are used to compute range aggregations on node chains.
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 11   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Why do you say Wiki article is about another structure? From what I read it is about somewhat generalized, but still same structure

→ Reply
»
11 years ago, # |
  Vote: I like it -43 Vote: I do not like it

There is an article about segment tree on e-maxx;

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply