Блог пользователя -is-this-fft-

Автор -is-this-fft-, история, 3 года назад, По-английски

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
  • Проголосовать: нравится
  • +111
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +76 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Since we are on this topic

  • DSU (disjoint set union)
  • UFDS (union-find disjoint set)
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

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

    • Union-find data structure
    • Union-find disjoint set
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +157 Проголосовать: не нравится

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

      • Union-Data Find Structure

      • Union-Disjoint Find Structure

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +582 Проголосовать: не нравится

      Upgraded DFS

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +49 Проголосовать: не нравится

    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)

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -42 Проголосовать: не нравится

Lazy segment tree (without the word "creation")

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +103 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      For what idea?

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

          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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится

            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;
            
        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          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

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится -20 Проголосовать: не нравится

            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

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится -9 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                3 года назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +143 Проголосовать: не нравится
Meme
»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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"?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

'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 :))

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

spoiler
»
3 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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!

»
3 года назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

Ok please explain to me what is implicit about it.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +55 Проголосовать: не нравится

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)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +41 Проголосовать: не нравится

      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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +54 Проголосовать: не нравится
  • 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.
»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Another Meme
»
3 года назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

How about binary trie?

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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)

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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