### -is-this-fft-'s blog

By -is-this-fft-, history, 4 months ago,

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

 » 4 months ago, # | ← Rev. 2 →   +76 In Russian we most commonly call it "неявное дерево отрезков". The most precise translation is implicit segment tree.
 » 4 months ago, # |   +32 In Turkish we most commonly call it "Örtük Aralık Ağacı". The most precise translation is implicit segment tree.
•  » » 4 months ago, # ^ |   +17 ...arağaç
•  » » 4 months ago, # ^ |   +10 In English we most commonly call it "sparse segment tree." At least that's the term USACO Guide uses.
 » 4 months ago, # |   +33 Since we are on this topic DSU (disjoint set union) UFDS (union-find disjoint set)
•  » » 4 months ago, # ^ |   +32 Since we are on this topic — what is the correct expansion of the acronym UDFS: Union-find data structure Union-find disjoint set
•  » » » 4 months ago, # ^ |   +157 Since we are on this topic — what is the correct expansion of the acronym UDFS: Union-Data Find Structure Union-Disjoint Find Structure
•  » » » 4 months ago, # ^ |   +582 Upgraded DFS
•  » » 4 months ago, # ^ |   +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)
•  » » » 4 months ago, # ^ |   0 In Russian it's "Система непересекающихся множеств (СНМ)"; translates as system of disjoint sets/set of disjoint sets.
•  » » 4 months ago, # ^ |   0 bad poll -- options should be DSU vs Union-find, nobody says "union-find disjoint set", it's just union-find.
 » 4 months ago, # |   -42 Lazy segment tree (without the word "creation")
•  » » 4 months ago, # ^ |   +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.
•  » » » 4 months ago, # ^ |   +15 For what idea?
•  » » » » 4 months ago, # ^ | ← 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.
•  » » » » » 4 months ago, # ^ |   0 If anything I'd call it lazy propagation segment tree, and didn't hear anybody called it lazy segment tree
•  » » » » » » 4 months ago, # ^ |   +121 they're too lazy to say the whole thing
•  » » » » » 4 months ago, # ^ |   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
•  » » » » » » 4 months ago, # ^ |   +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; 
•  » » » » » 4 months ago, # ^ |   +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
•  » » » » » » 4 months ago, # ^ |   -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
•  » » » » » » » 4 months ago, # ^ |   -9 Yet my option got more votes than the OP's "lazy creation segment tree", even despite being hidden because of the negative feedback
•  » » » » » » » » 4 months ago, # ^ | ← 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?
•  » » » » » » » » » 4 months ago, # ^ |   0 Maybe some don't know the difference between lazy propagation and lazy segment tree like me:)
 » 4 months ago, # |   +143 Meme
 » 4 months ago, # | ← Rev. 4 →   0 Slightly off-topic, but I don't want to create another blogAre 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.
•  » » 4 months ago, # ^ |   +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"? Yes No
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +6 Nowadays, if you want to get gold easily at RMI, you need to know data structures :( SpoilerI didn'tBtw I've overkilled 1513F - Swapping Problem with merge sort tree (comment).
•  » » » » 4 months ago, # ^ |   +1 RMI is a special contest
•  » » » » 4 months ago, # ^ |   +14 Segment tree beats goes brrrrrrr
•  » » » » » 4 months ago, # ^ |   0 There is an easy solution with merge sort tree! It can process chmin as well.
•  » » 4 months ago, # ^ |   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.
 » 4 months ago, # |   +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 :))
 » 4 months ago, # |   0 these stats show that we greens or below are busier people than specialists or above XD spoiler
•  » » 4 months ago, # ^ |   +11 Spoiler*atleast 1
 » 4 months ago, # |   +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!
 » 4 months ago, # |   +40 Ok please explain to me what is implicit about it.
•  » » 4 months ago, # ^ |   +123 The nodes are implicit. Until you create them
 » 4 months ago, # |   +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.'
 » 4 months ago, # | ← 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)
•  » » 4 months ago, # ^ |   +29 Segment tree is already dynamic. I mean, it's not static, right?
•  » » » 4 months ago, # ^ |   +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
 » 4 months ago, # |   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.
 » 4 months ago, # | ← 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.
 » 4 months ago, # |   +4 Another Meme
•  » » 4 months ago, # ^ |   -20 Just mark both, it's allowed.
 » 4 months ago, # |   +58 How about binary trie?
 » 4 months ago, # |   +8 Since when have you started rating cyans??It should have been : I am Cyan or Below
 » 4 months ago, # |   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.
 » 4 months ago, # | ← Rev. 2 →   0 for the new specialists, it feels good when you don't have to vote I'm green or below
 » 4 months ago, # | ← 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. :)
 » 4 months ago, # |   +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".
 » 4 months ago, # |   +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)
 » 4 months ago, # | ← 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
 » 4 months ago, # |   +8 Can we use coordinate compression and then apply regular seg tree?
•  » » 4 months ago, # ^ |   0 Yes but that's not the point. I should have added that queries are online or something.
 » 4 months ago, # |   0 hmm what should I vote for? :/I'm green or below & I know the data structure and call it Dynamic segment tree
 » 4 months ago, # |   -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.
•  » » 4 months ago, # ^ |   -10 I know you can do it with treap, but that's beside the point.
 » 4 months ago, # |   0 In Pig Latin we most commonly call it "implicityay egmentsay eetray". The most precise translation is implicit segment tree.