I was reading this: https://cp-algorithms.com/data_structures/segment_tree.html (segment tree) and I noticed something crazy. The create function is unnecessary. You can just call $$$n$$$ update functions. This could actually save 1-2 minutes of typing. Maybe even 10-20 minutes if the segment tree is especially weird.
Edit: okay, I see how this is not optimal. It looks like this would have a time complexity of $$$O(n \cdot log(n))$$$, while the normal creation method has a time complexity of $$$O(n)$$$.
The build function takes less than a minute to code, wtf are you on about
not if your fingers are cold
also the time complexity might be the same but the constant factor for calling update N times will be way larger, since we'll be recursively going through a segment multiple times (with some being returned early)
doing $$$N$$$ updates takes $$$\mathcal{O}(N\cdot\log{N})$$$, building the tree takes $$$\mathcal{O}(N)$$$
I think you might be thinking of a heap. Building a heap (which is technically a list, not a tree) is $$$O(n)$$$, but building a segment tree is definitely $$$O(n\cdot \log(n))$$$.
Building a segment tree is O(n) : There are O(n) nodes, and for each node we do O(1) operations.
iirc, each tree has $$$n \cdot \log(n)$$$ nodes, so building a segment tree can't be less than $$$O(n \cdot \log(n))$$$.
The last layer of segment tree has n nodes, the penultimate layer has n/2 nodes and so on : n+n/2+n/4+...+1 ~ 2n. Therefore there are O(n) nodes.
But here is where I'm confused. Each layer has $$$n$$$ things it stores, right? And the sequence $$$n, \frac{n}{2}, \frac{n}{4} \cdots 4, 2, 1$$$ has $$$\log_2(n)$$$ elements. So wouldn't that mean $$$n \cdot log_2(n)$$$ nodes?
the sequence does have $$$\log_2n$$$ elements, but its sum is bounded by $$$2\cdot n$$$, and it's the sum which gives the number of nodes. The number of terms in the sequence — $$$\log_2{n}$$$ — gives the number of layers in the tree
There is another way to calculate it: On the last layer there are $$$n$$$ nodes, and every space between two elements will contribute one node (it appeared as "mid" once), so there are $$$2n-1$$$ nodes in total.
Also the way qwertylkjhg says is much easier.
What you are wrong with is that " Each layer has $$$n$$$ things it stores". To be precise, it is the total length of the segments which is $$$n$$$, not the number of segments.
yes, I see that now. It looks like the first layer has 1 node, second has 2, third 4, etc. That makes sense how it is only O(n) nodes.
Nonsense.
say you are building a segment tree for $$$n$$$ elements. You need the segment tree to be a perfect binary tree — so you need the number of leaves to be the least $$$2^x \geq n$$$, let's call it $$$N$$$, which is bounded by $$$2\cdot n$$$. Total number of nodes in the segment tree will be twice that (actually $$$2\cdot N - 1$$$ but ok)
You should use a build function. This could actually save 0.1s-1s of execution. (However this is nothing compared to your 1-2 minutes)
It could be 10-20 minutes depending on the type of tree. I've seen some really weird segment trees before.
Such as range prefix maximum count query with range addition?
You will 100% get TL if you attempt to update the segment tree $$$O(n)$$$ times on that one problem.
I am not sure, but this is one of the weird ones I have seen: https://leetcode.com/problems/longest-substring-of-one-repeating-character/description/. It is like dp in a segment tree. I have also seen it in an edu problem once. It just takes a few minutes to code out each function.
Edit: I just checked it using the update method and it was within the time limit. It also shortened the code by a little bit. But you are right, it was quite a bit slower.
It's more like maintaining the length of the prefix and suffix with same characters and has nothing to do with DP... (and you can find this in the GSS series)
You are not getting TL in that problem only because TL in this problem is loose.
Anyway I'm not against the fact that sometimes you can use update functions in place of build functions to save coding time. But mentioning it as "crazy" or "unnecessary" just show how ignorant you are.
ok, well I do appreciate you showing me the differences in time complexities.
It won't if you create a merge function:
This can be reused in the update function, so coding up the merge function is something seperate from the other functions. The build function is almost always gonna be the same if you do this.
That is actually a very good idea. It looks like it makes every single build and update function only a few lines.