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

By -is-this-fft-, history, 2 years 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

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