-is-this-fft-'s blog

Poll: what do you call this well-known extension of segment tree?
By -is-this-fft-, history, 3 years ago, In English

For some reason, everyone refers to it with a different name which creates a lot of confusion. This debate comes up any time someone mentions any of the names, so let's have a poll to settle this thing once and for all.

Consider the following problem.

Problem. There is an array $$$A$$$ of length $$$10^{18}$$$, initially filled with zeros. You are given $$$q$$$ queries of the following form:

  • Given $$$l$$$ and $$$r$$$, find $$$A[l] + A[l + 1] + \cdots + A[r]$$$.
  • Given $$$i$$$ and $$$x$$$, set $$$A[i] \gets x$$$.

What do you call the data structure that solves the problem above in time $$$O(q \log C)$$$?

Details if you're not sure what I mean
  • Compressed segment tree
  • Dynamic segment tree
  • Implicit segment tree
  • Sparse segment tree
  • Lazy creation segment tree
  • I don't know this data structure
  • I'm green or below
  • Vote: I like it
  • +111
  • Vote: I do not like it

Comments Comments (60)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +76 Vote: I do not like it

In Russian we most commonly call it "неявное дерево отрезков". The most precise translation is implicit segment tree.

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

In Turkish we most commonly call it "Örtük Aralık Ağacı". The most precise translation is implicit segment tree.

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

Since we are on this topic

  • DSU (disjoint set union)
  • UFDS (union-find disjoint set)
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Since we are on this topic — what is the correct expansion of the acronym UDFS:

    • Union-find data structure
    • Union-find disjoint set
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +157 Vote: I do not like it

      Since we are on this topic — what is the correct expansion of the acronym UDFS:

      • Union-Data Find Structure

      • Union-Disjoint Find Structure

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

      Upgraded DFS

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

    In Poland we never call it with any of these names. We always say "Find & Union" and abbreviate it as "F&U". However FWIW I've seen DSU many times and have absolutely never seen UFDS (but I guess it's closer to our F&U)

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

      In Russian it's "Система непересекающихся множеств (СНМ)"; translates as system of disjoint sets/set of disjoint sets.

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

    bad poll -- options should be DSU vs Union-find, nobody says "union-find disjoint set", it's just union-find.

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

Lazy segment tree (without the word "creation")

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

    Excuse me what? That's probably the worst idea you can have, "lazy creation segment tree" makes a lot of sense, but "lazy segment trees" is a name already reserved for a completely different idea.

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

      For what idea?

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

        Uhm, do you want me to explain what lazy propagation is? It is just letting some nodes having some outdated info if we have not reached them while going from the root. The other rule of thumb that distinguishes segment trees that need lazy propagation from ones that don't, is that usual segment trees can be implemented both top-down and bottom-up, while these that need lazy propagation need to be implemented top-down. An example requiring lazy propagation is "You need to handle queries where in a query you get an interval [L, R] and a color c and you recolor whole interval to color c, all old colors there get overriden". Segment tree beats is another one if I'm not mistaken. For some people (what may include you?) that are used to top-down trees they may not even notice the required laziness anymore, but for people that were used to bottom-up segment trees, lazy propagation was quite some dramatical change of thinking that caused me to fully switch to top-down approach.

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

          Although "lazy propagation" can be viewed as allowing nodes to contain "outdated info," it can also be viewed as simply storing the summary of a node's range along the entire path from the root to that node rather than storing the summary only in that one node.

          From this perspective, there's nothing lazy about the propagation happening in range-update segment trees. Performing propagation is not necessary to answer range queries, even if some "lazy" range updates have already taken place. And because of that, queries can still easily be answered in a bottom-up fashion.

          Propagation is only necessary during the range-updates themselves, and even then only when the range-updates are non-commutative: The entire reason propagation ever has to happen is to push any older range updates "below" the new ones so that they will be applied to subsequent queries in the correct order.

          The only special-case I'm aware of where "lazy propagation" can actually be efficiently implemented using only lazy evaluation is the case of range-assignments, where the result of a range-update does not depend on the contents of that range before the update. Otherwise, performing two combined queued lazy-range-updates on a range ends up costing twice as much as performing one, which leads to bad performance.

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

          If anything I'd call it lazy propagation segment tree, and didn't hear anybody called it lazy segment tree

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

          while these that need lazy propagation need to be implemented top-down

          I think this is not true. You can check AtCoder library which implements bottom-up segment tree with lazy propagation: link

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

            Their lazy_segtree is iterative, but not bottom-up. Look at just about any of the functions: They all start with a top-down propagation loop that looks like this:

            for (int i = log; i >= 1; i--)
  push_updates_from_i_layers_above;
            → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          So what you tell is "lazy segment tree is about lazy propagation, and not lazy creation, and other interpretations of this name are inappropriate and incorrect", ok sir

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it -20 Vote: I do not like it

            Of course lol. It's just definitely more often used and got stuck with that meaning and there's nothing you can do about it now. I'm sure there are tons of others examples where such shorthand was made historically but I'm too lazy to think of one

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it -9 Vote: I do not like it

              Yet my option got more votes than the OP's "lazy creation segment tree", even despite being hidden because of the negative feedback

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

                I am curious, what could be the reason why your original comment is hidden because of downvotes and that mine original reply to it has a lot of upvotes? Any ideas?

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

                  Maybe some don't know the difference between lazy propagation and lazy segment tree like me:)

                  → Reply
»
3 years ago, # |
  Vote: I like it +143 Vote: I do not like it
Meme
→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Slightly off-topic, but I don't want to create another blog

Are merge sort tree and wavelet tree the same data structure?
[poll closed, 0 yes, 14 no]

Fun fact: merge sort tree and wavelet tree are the same data structure! A wavelet tree is the merge sort tree of the inverse array.

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

    Have you ever used merge sort tree or wavelet tree in any problem whatsoever, without being told "this is a practice problem for merge sort tree/wavelet tree"?

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

    Regarding your last comment: I prefer to think of a wavelet tree as being analogous to some kind of a quicksort tree rather than a merge sort tree on the inverse array, since it's easier to think of it that way (though it might be less accurate).

    But the actual construction is much closer to a trie with every vertex storing some information about elements in the subtree of that vertex in the order that they appear in the array. Indeed, if you shift all elements so that everything is $$$\ge 1$$$ in the array, and add sentinel elements $$$0$$$ and $$$2^m - 1$$$ to the beginning and the end of the array (or use this as the starting range of values in the call to the build function instead of adding them to the array), where $$$m = \lceil \log_2 \max_{i = 1 \ldots n} (a_i + 1) \rceil$$$, then the wavelet tree is isomorphic to the trie.

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

'The one and only' correct naming scheme:

  • this is implicit segment tree
  • if you use a treap to reorder ranges dynamically and slice arbitrarily, the best name is dynamic segment tree
  • lazy segment tree is for lazy propagation of data, wtf
  • compressed tree is a common name for virtual tree as a subset of nodes in a tree(graph)
  • the only thing that's sparse is sparse table, but it's a different data structure.

I hope it helps :))

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

these stats show that we greens or below are busier people than specialists or above XD

spoiler
→ Reply
»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

I tend to use both Implicit and Dynamic Segment Tree. Sparse Segment Tree also sounds correct and is often used by people.

However, Compressed Segment Tree reminds me of this blog by bicsi. Plus implicit segtree doesn't "feel" like it uses compression.

Lazy Creation Segtree is technically kinda correct but it sounds lame (and can be confused by lazy segtree), so nope, rejected.

Lastly, if you think about it, implicit segtree is actually a Bitwise Trie!

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

Ok please explain to me what is implicit about it.

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

    The nodes are implicit. Until you create them

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

Isn't this just called a...

  • segment tree?

Of course, I'm joking a little. But this really is just the default behavior I would expect from a segment tree in Haskell. Lazy and persistent, by default! If I didn't know it would just annoy and confuse people, I'd be tempted to describe the typical ephemeral mutable-array-based segment tree implementations as 'implicit segment trees.'

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +55 Vote: I do not like it

I have never even realized somebody on this planet can have an idea to call it differently than dynamic segment tree (but I won't argue it makes more sense than others :P)

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

    Segment tree is already dynamic. I mean, it's not static, right?

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

      It's hard to tell what word "dynamic/static" mean in algorithmics sometimes, because dynamic programming was called dynamic because of a reason that in my opinion is the exact reason why this should NOT be called dynamic :P.

      But I see a good analogy that the shape of typical segment tree is not changing, while the shape of dynamic segment tree changes a lot

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

IMO "dynamic segment tree" is more suitable because we dynamically allocate memory for the segment tree. Whereas "implicit segment tree" might cause confusion as there is another term implicit graph, which is not anything close to this segment tree we are talking about.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +54 Vote: I do not like it
  • Although "implicit" is popular, it doesn't really agree with how implicit data structures are defined in literature since the data structure in question is often implemented with pointers, hash tables, or other non-implicit data structures. In fact, your vanilla segment tree with binary heap like indexing is more appropriately called "implicit".
  • "Dynamic", at least to me, sounds unspecific since it is already such an overloaded term. It is also often used to describe data structures for which you can dynamically modify the size of the underlying abstract representation of the data (through insertions and deletions) which isn't the case here since the array is static in size. Sure, you are dynamically allocating memory but it doesn't really clarify the purpose of the data structure.
  • "Sparse" (which is in my opinion, the best choice) is consistent with how some other similar data structures are called. In fact, you can view the above as an one-dimensional sparse matrix with support for efficient modification and submatrix sum queries.
→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Another Meme
→ Reply
»
3 years ago, # |
  Vote: I like it +58 Vote: I do not like it

How about binary trie?

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

Since when have you started rating cyans??It should have been : I am Cyan or Below

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

I think in English, the most common term for it is "sparse segment tree." At least, that's what USACO guide uses. I've also heard dynamic segment tree before, but "sparse segment tree" seems to be more popular.

I'm actually surprised by the number of people who denoted it as an implicit segment tree. I've never heard that before.

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

for the new specialists, it feels good when you don't have to vote I'm green or below

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

I mean, this is an application of both lazy propagation and an implicit segment tree. So I suppose I would go with the third option. :)

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

In Chinese we call it "动态开点线段树" which means "Dynamic node-opening segment tree" (translated in a machine-like style). So I suppose that we call it "Dynamic segment tree".

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

Can I select multiple options as I both called it Dynamic Segment Tree (meaning that it is possible to extend its total length) and Implicit Segment Tree (meaning that only stores the data that is needed in the calculation)

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I often just use the same code as for a regular segment tree or Fenwick tree, but backed by hashmap(s) instead of array(s). I don't know what that is called lol

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

Can we use coordinate compression and then apply regular seg tree?

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

    Yes but that's not the point. I should have added that queries are online or something.

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

I voted "I'm green or below" :^)

Btw you're missing the obvious answer: treap. My treap can work as indexed set with range queries, which naturally solves it.

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

In Pig Latin we most commonly call it "implicityay egmentsay eetray". The most precise translation is implicit segment tree.

→ Reply