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
In Russian we most commonly call it "неявное дерево отрезков". The most precise translation is implicit segment tree.
In Turkish we most commonly call it "Örtük Aralık Ağacı". The most precise translation is implicit segment tree.
...
arağaç
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.
Since we are on this topic
Since we are on this topic — what is the correct expansion of the acronym UDFS:
Since we are on this topic — what is the correct expansion of the acronym UDFS:
Union-Data Find Structure
Union-Disjoint Find Structure
Upgraded DFS
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)
In Russian it's "Система непересекающихся множеств (СНМ)"; translates as system of disjoint sets/set of disjoint sets.
bad poll -- options should be DSU vs Union-find, nobody says "union-find disjoint set", it's just union-find.
Lazy segment tree (without the word "creation")
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.
For what idea?
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.
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.
If anything I'd call it lazy propagation segment tree, and didn't hear anybody called it lazy segment tree
they're too lazy to say the whole thing
I think this is not true. You can check AtCoder library which implements bottom-up segment tree with lazy propagation: link
Their
lazy_segtreeis 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: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
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
Yet my option got more votes than the OP's "lazy creation segment tree", even despite being hidden because of the negative feedback
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?
Maybe some don't know the difference between lazy propagation and lazy segment tree like me:)
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.
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"?
Nowadays, if you want to get gold easily at RMI, you need to know data structures :(
I didn't
Btw I've overkilled 1513F - Swapping Problem with merge sort tree (comment).
RMI is a special contest
Segment tree beats goes brrrrrrr
There is an easy solution with merge sort tree! It can process chmin as well.
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.
'The one and only' correct naming scheme:
I hope it helps :))
these stats show that we greens or below are busier people than specialists or above XD
*atleast 1
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!
Ok please explain to me what is implicit about it.
The nodes are implicit. Until you create them
Isn't this just called a...
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.'
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)
Segment tree is already dynamic. I mean, it's not static, right?
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
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.
Just mark both, it's allowed.
How about binary trie?
Since when have you started rating cyans??It should have been : I am Cyan or Below
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.
for the new specialists, it feels good when you don't have to vote
I'm green or belowI mean, this is an application of both lazy propagation and an implicit segment tree. So I suppose I would go with the third option. :)
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".
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)
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
Can we use coordinate compression and then apply regular seg tree?
Yes but that's not the point. I should have added that queries are online or something.
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.
I know you can do it with treap, but that's beside the point.
In Pig Latin we most commonly call it "implicityay egmentsay eetray". The most precise translation is implicit segment tree.