tl;dr
Read this comment.
It's good to know that segment tree exists
- You can learn basic segment tree (Fenwick tree may be enough) if you want to overkill some problems. Just don't try to solve hard segment tree problems like this and this if you are cyan, because there are better ways to practice and learn something. This comment hits the spot: you can "be aware of the segment tree", but it shouldn't be your main weapon as a cyan / blue.
- If you take part to OI / ICPC, segment tree can be very useful (especially at regional level). Unlike on Codeforces, there may be easy-ish but not trivial segment tree problems (let's say with a rating around 2200). So, if you want to practice segment tree for some reason (e.g., you love segment trees, or you are practicing for OI), start with OI problems.
Should you master segment tree problems?
If you want to solve non-trivial segment tree problems, you should
- actually understand how segment tree works (including time complexity);
- have decent implementation skills;
- be able to convert the given problem into a segment tree problem.
If you are able to learn all these things, you already have purple skills. Conversely, if you are not purple, most probably you won't manage to actually learn segment tree.
Examples
- Blog 1: the author asks how to solve a problem. Someone replies, linking a comment about another problem whose solution is almost identical to the original problem. The comment contains a detailed explanation of the solution and an AC code.
The author of the blog replies that he wants an AC code of his problem because he can't implement the solution. It turns out it's because the provided AC code uses a segment tree as a struct.
- Blog 2: the author is "confused" about the time and space complexity of his solution using a segment tree. It turns out his solution is worse than the naive solution.
Comments
- Blog 1: if you understand the explanation of the solution, and you say you know segment tree, you should have no problems implementing the solution from scratch (point
2above). If not, it means that you don't understand the solution, so the problem is too hard for you (3). Then, why would you need to solve it? Also, copy-pasting others' code without understanding it does not count as solving the problem. Then, why are you asking for the code?
- Blog 2: I guess someone told you that the problem is solved "using segment tree" and you tried to implement a solution without even calculating the complexity (
1). Please note that there may be multiple ways, both correct and wrong, to use segment tree in a problem (similarly, in other problems there may be multiple greedy solutions, both correct and wrong). So, if you are using segment tree, it doesn't mean that the code is "magically" efficient. Finding an actually correct solution can be hard (3).
Conclusion
It's fine not to be good at points 1, 2, 3 above if you are blue or below. There are other (more important?) things to learn at that level.
Side note: when I first became yellow, I had no clue about how to solve the linked problems. Now I can solve them, but I'm still yellow.
I became blue from cyan after I learnt segment tree.
Correlation $$$\nRightarrow$$$ causation.
Did you become blue thanks to a segment tree problem?
At least I got 66 pts.
I wouldn't have got it if I hadn't known segment tree.
Can you send the link of the problem?
Let’s say that fake_littlejuruo solved a problem in an OI competition using sgt, but there isn’t direct correlation with her becoming blue.
Yes and actually I don't want to send the link as it can be solved non using segtree, but I'm too bad at stl...
The problem in an OI contest may be the second problem in china's csp 2022 s2.
notice the her in his comment...
Getting points from a segment tree problem is not the only way to get an advantage from learning about segment tree. In general, practicing algorithms make it easier to learn other algorithms and come up with new ones on your own.
I'm still cyan after learning it. But basic segtrees (I think) are worth to learn maybe?
based
upvoted twice
I'm sorry, last introductory CP course at KAIST I lectured, I teached segment tree but not DFS.
Learn whatever you think is fun. Maybe it's not the most useful thing to practice at those ratings, but I think for me it was good to learn segment tree while green, because it felt powerful and fun, and motivated me to practice more other things in competitive programming as well.
Learning basic segment tree can be OK. I just don't recommend cyans to try to solve "hard" segment tree problems (i.e., 90% of segment tree problems), because they are not ready for those problems. In fact, I don't think "reading the editorial, having trouble understanding and implementing the solution, and finally getting AC after some days" is fun, especially if your feeling is "ok, I got AC, but I still don't get why it works".
Looks like my 10-year competitive programming was all trash.
Seriously, how to improve by solving only problems "ready for you"?
There is a middle way between problems "ready for you" and problems whose rating is 1000 points higher than yours.
Sorry, your rating system is not my business. But the "reading the editorial, having trouble understanding and implementing the solution, and finally getting AC after some days" is exactly what I see as a pursuit of enlightenment. It's sad they failed to know, but they at least tried. They should end up in better places than the ones afraid to try.
The author of this blog wanted a pursuit of enlightenment, so he asked for the code to copy-paste. Also, I don't think getting AC after some days by copy-pasting the code of the other problem (whose solution is 90% the same) and trying random changes is much different.
I cited your sentence which I objected. Why do you want to talk about different things?
It's not a different thing.
"Reading the editorial, having trouble understanding and implementing the solution, and finally getting AC after some days", if you manage to learn something, can be very good (maybe the best way to learn). However, I wouldn't recommend it if it's done with the only goal of getting AC (for example, if you feel the need of searching for shortcuts such as a code to copy-paste).
It is a different thing.
Anyway, I agree to your last paragraph, so we can settle this.
So just because of this guy, you concluded that everyone below purple shouldn't learn segment trees?
I think I've seen many examples of blogs like that (e.g., the 2 linked blogs in just 2 days).
Is Darooha (Splay tree algo founder) also allowed to learn about segment trees?
There are exceptions to the rule.
lmfao, what exception? You said anyone below purple shouldn't learn about segment trees. Isn't he below purple? or he hasn't done enough contests?
The point is that non-trivial segment trees don't help improving rating if you are below purple. Of course you can learn them if you want, but this doesn't increase your rating.
As a yellow, I've never used a segment tree in a rated contest.
Well i dunno i have used segment trees in alot of problems in contests. tbh around 30% of them. using them is not the same as solving problems with it. sometimes u solve a problem on paper with lets say dp and value of dp of one index is based on an interval of pervious dps. sure there might be a better way to solve that problem but why bother in a rated contest ?
I don’t actually think that sgt is hard to implement you know. However, the author has a point: if u r just focusing on the rating, then there is no need for sgt. However if u r preparing for OI in your country, for example, then it would be quite useful.
You're everywhere! Cute Lyrically!
Cute piggy!
Well, I'm not purple yet but I've solved many problems during the contests using segment tree, there are tons of problems that doesn't require segment trees but using them makes the solution much easier and intuitive.
"You" reaching master without learning segment tree doesn't deny the fact that they are a really strong weapon to have inside the contest.
your graph gives me hope
I just practice segment tree tasks because its just too interesting to find out what more I can do with something I already know. That being said, I really love abusing fenwick trees wherever I can. Recently found out a way to deal with suffix sum/product/rmq queries with a fenwick tree, without reversing the array or using inclusion exclusion (Well, somehow it worked, all I did was switching places of query and update), and thinking of where I could abuse that. Agree with not going too far though, I don't understand lazy prop or segtree beats either.
I mainly agree with agree. Some years ago I was high yellow, but had still trouble with seg trees and it was rarely a problem and believe it's possible to wait a lot before learning lazy prog, monoids, seg tree beats... However I would say very standard segment tree can be already useful at blue sometimes while being relatively "easy" to learn, understand & implement
Auto comment: topic has been updated by TheScrasse (previous revision, new revision, compare).
If you are not purple, most probably you won't manage to actually learn segment tree.
I understood segment trees when I was blue and I don't think that many people are going to agree with this.
"actually learn segment tree" = be able to solve this and this. Why is the first problem rated *2500, if many blue people know segment tree?
So everyone who knows segment trees should be able to solve 2500 rated segment tree problems? Btw, blue $$$\neq$$$ cyan.
On Codeforces, problems where segment tree is intended usually have such ratings. The easiest problem where I've used a segment tree during a contest on Codeforces is 1513F - Swapping Problem (rating: 2500), whose intended solution doesn't require segment tree. I think trying to solve such problems as a cyan (but also as a blue) doesn't really help improving.
I bet I've seen lower rated segment tree problems, but I'm quite lazy to search for them. And codeforces isn't the only programming contest platform. There are a ton of problems in atcoder beginner contests for example that require segment tree knowledge.
As I said, you can practice these problems first (from OI, ABC, or whatever). Just don't jump to this after writing your first segment tree.
Was that the point of your blog? The title says "Don't practice segment tree if you are below purple", and I think that's the main information you're trying to pass.
The point is that you can try to solve these problems as a blue or below (which don't really require segment tree, Fenwick is enough), but you're not so ready for these problems.
Why do you keep emphasizing on Fenwick trees? I would even argue that it's more difficult to understand how a Fenwick tree works internally than a segment tree.
The point is that you don't need to learn segment tree (or Fenwick, or whatever) to solve the problem, you can just "be aware of the segment tree" and copy-paste the code (or rewrite it, if you feel it's useful for you). You don't need to learn segment tree.
Maybe not everyone wants to just "copy-paste". Me for example, I will like to understand what I'm copying and not just copying blindly.
Good job. I'm just saying it may be too hard for a cyan / blue, and it may lead to results such as this. The author of the blog managed to create a custom segment tree
combinefunction (so he understands the implementation of segment tree), but that's not enough to solve the problem.My last reply in this thread. I don't think a segment tree is a difficult data structure, and I believe everyone above 1600 rating can learn it easily.
It depends on the definition of "learning".
Maybe you're right, but there are much lower rated problems on CF where segment trees can help you solve a problem, for example 1779D - Boris and His Amazing Haircut. The intended solution uses a stack, but there is a pretty simple solution using a max segtree (or a sparse table, since there are no updates). The method doesn't work with a fenwick tree.
I don't think I would've solved the problem if I didn't know segment trees. Here is my solution for reference, if you'd like to see it: 187823684
Ok, I tried the problem you mentioned for the last 20 — 25 min and was not able to come up with a solution. But, that doesn't change the fact that I have my own segment tree library and I changed the code to support weighted queries (on lazy seg trees), etc. I am not saying that segment tree problems must be asked frequently at the expert level or that experts must learn them. All I'm saying is they are not that hard. Also, I don't like problems in contests to require some well-known complex topics. That's one of the reasons why I rarely compete in other platforms than Codeforces.
Alright, you do not understand DP because you cannot solve 3500 DP problems.
Strictly regarding Codeforces ratings, I'd say you can quite easily reach master without segment trees. But in my experience at Romanian OI, segment trees were immensely useful for me, and even back when I was still expert on CF (and far from reaching purple), I could easily implement segment trees, and was even quite good at segtree problems at OI (which would have on CF a rating of 2100-2300). It really depends on the competitions you are participating in, but I think you can learn segtrees at expert level, and during CF rounds you have a small (but certainly non-zero) chance of getting a div2D which you can solve in-contest with segtrees.
Auto comment: topic has been updated by TheScrasse (previous revision, new revision, compare).
I think even in Atcoder's ABC, there are segment tree problems, e.g. ABC283F, so I wouldn't discount learning it before reaching purple, hard to say when u would need one.
Fenwick tree is enough for that problem.
Fair enuf, it's just the first question that came to mind
I think that people understand the word "learn" differently. When I see/hear the phrase "I learned segment tree", I assume one of these two meanings:
I will call the second meaning learning the segment tree, and the first meaning being aware of the segment tree.
If you want to learn segment tree, and you're below Div1 — well, it will be very difficult. It will help you improve, but you'll have to work really hard, and the results you'll get most likely will be far less noticeable than if you instead practice binary search/DP/maths/DFS/general problem-solving. Actually understanding the segment tree and what information it has to store for the operations it must support is not a trivial task. From my experience: from the moment when I attended my first segment tree lecture+contest to the moment when I could implement a segment tree with operations "sum on segment + add on segment", two full years have passed. In these two years, I climbed from blue to red on CF, but I didn't actually understand the segment tree at all, apart from something very easy like RSQ/RMQ.
Okay, then what about being aware of the segment tree? Well, surely you'll be able to use it in some problems, and maybe you'll get some of them accepted. And being aware of ST is way easier than actually learning it. But there are two caveats:
So, being aware of the segment tree at low ratings is a bit double-edged: it can be used to solve problems, but you should remember that these problems are usually suited for simpler solutions, and even when you get AC, you should try to think about easier approaches afterward (for example, after the contest).
From my experience, 1600 can comfortably understand segment trees, and I think they should, because it is the easiest example of divide and conquer (apart from merge sort, probably). I think segment trees are good to teach for Cyan, but not less.
Whether the border be in 1600 or 2100, it's a matter of environment indeed. But I think personal experience can't be generalized. I have 3200 and I still can't write Chinese Remainder Theorem, but I don't think <3000 learning CRT is waste of time.
What level of understanding are you talking about? I agree that cyans can be taught something like RSQ/RMQ, maybe ST which stores sorted vectors in nodes. But in my experience both as a contestant and as a teacher, the moment you go to problems which force you to modify something internal in ST (the ones where you cannot use ST as a black box), it becomes a bit too much for people below purple. Just their coding skills and/or skills of deriving the requirements for data structures from the queries it has to process aren't enough by that moment.
I was talking about RMQ (without lazy propagation) segment trees, written recursively, and implemented from scratch with full knowledge of their structure.
I'm not sure what you mean about the problems that force the internal modification of ST. I just can't come up with such examples. Probably they are not hard because people don't understand the internal structure of segment trees, but they are just hard idea-wise. (e.g. Segment tree beats)
For example, something like segment tree descent.
Let's say that the problem is "add on segment" and "find the first prefix with sum $$$\ge x$$$", where values are non-negative. All queries have to be processed in $$$O(\log n)$$$.
Well, ignoring first query (lazy propagation), I think it's not hard for 1600.
I agree, sometimes it could be very tedious to write. However in theory it should be easy. Actually, the hard part doesn't seem to come from ST, it seems to come from binary search...
I do think it's hard, but maybe it's because of different problem styles in different environments. When I compared NERC (my home region) contests to contests from other regions, I was surprised to see that the other regions use much more advanced algorithms and data structures in their ICPC problems. For example, it was entirely possible to qualify to World Finals from NERC without writing anything more advanced than Floyd-Warshall, but in other regions, it's not gonna cut it.
So, maybe I'm biased because of different problemsetting and preparation traditions in my region.
I'm pretty sure if anyone, irrespective of their rating, devotes time to learning Segment Tree, they can do it.
I learned normal/lazy Segment Tree when I was around cyan (maybe green?). It spent around two weeks trying to understand it (be able to implement it without looking and apply in different contexts), but I did it.
On the whole, I found learning Segment Trees easier than trying to understand some CF editorials >.<
But I will leave it to higher rated people about what rating seg tree becomes important.
Auto comment: topic has been updated by TheScrasse (previous revision, new revision, compare).
don't write blogs if you are below master
RESPECT who below 2100!!!!!
i respect non-masters but i dont find their blogs enjoyable
I mean, Segment Tree is just easy stuff. Like, I've seen way too many dudes who do Codeforces contest regularly for years and haven't surpassed Green, but have learned like every single data structure and graph theory required to get a decent place in National OI (like HLD, FFT, Tricks to optimize DP, etc.). How're their performance? Well in an online class, one day the teacher decided to make a contest, and by the time they solved 2 easiest problem, which requires like Fenwick Tree, DSU with some observation, I have already finished the 5th one lol.
I hate it when higher rated people try to ridicule lower rated people by telling them what to learn. Allow them learn whatever they want, eventually they will realize that it isn't useful (if it isn't). Linking those blogs was unnecessary by the way, they are just trying to learn.
It's not easy to realize something isn't useful, if no one else points it out.
It isn't ridiculing, the more experienced have to guide the less experienced.
No one asked for his guidance. Allow me experiment and find what works for me.
You'd be wasting a lot of time. Humanity got so far because humans depend on what their ancestors discovered instead of wasting time repeating all of history discoveries and inventions on their own.
how the fuck are you relating discoveries in history to learning competitive programming?
It's all the same. People have experiences. They fail. They succeed. They share their experiences to the next generation, and the next generation use the previous generation's experience to be better.
Low rated person: Don't tell me how to learn, I am searching for my own way!
Also low rated person: These modern CF contests suck, just stupid ad-hocs, constructives and math, it's impossible to learn anything from them!
I don't understand how your comment is related to what I said. Anyways, you're red so I guess whatever you comment is right.
Okay, I will elaborate.
Practicing what you want and searching for your own way in competitive programming is fine. Maybe it's suboptimal, but some people have more fun that way.
But, if you choose to ignore the advice you are given, you've got to accept the consequences of it. I see a lot of people (including yourself) talking trash about contests every time they see something they either don't like solving or have no experience in. Very often, I get comments like "this round has absolutely no DSA" from people who didn't get to problems involving DSA (C-D and harder ones). If these people had followed the advice on what to practice at which level, they would be able to understand the problems suitable for their skill level better, and eventually would get to solve the problems with more advanced topics. But instead, they often say that it's contest organizers' fault, and feel like the problemset should be targeted at what they have learned.
tl;dr: Choosing your CP path is fine, but don't expect the platform to go the same path as you do.
how do you know my rating? I haven't even taken any contest, I'm not even in div2 lol. Well, I'm sorry if my comments seemed arrogant, but that was honestly how I felt about your problems. I generally dislike adhoc/constructive problems because I think you don't ever get to reuse the ideas, hence is learning them useful? and most of the problems like that feel very artificial to me, it's like forcing a random problem (like finding some permutation, or just some weird pattern) to become a CP problem.
NOTE: I will still continue to comment in future rounds, and this is a troll account.
It's not just my rounds only, I don't feel like it's directed at my contests in particular.
Reusing some particular idea is definitely rare. But, what matters is not the pattern, but how you arrive to it. Some people randomly guess it, but random guessing is very unreliable. So, in order to solve these types of problems, you have to develop the skills to understand how to search for those patterns, so that random guessing becomes not so random. These are general problem-solving skills, like learning to understand which constraints matter and which can be dropped (or even made stricter), quickly eliminating methods to solve the problem because they don't work. These skills are very helpful for higher-rated problems, where you sometimes don't have a single clue which data structure or algorithm can be used to solve the problem and which cannot. So, I believe practicing these types of problems helps develop the skills essential to progress, and I (and many other authors, I think) try to introduce them in easier problems to help participants practice them.
tl;dr: Guessing is not that helpful, but learning how to eliminate your "guess space" so that you don't just do it blindly is important.
I partly agree. Learning Segment Tree is good, but when you reach an area where the ideas are out of your scope, you have to stop. I personally know basic Segment Tree, and it was kind of useful to me. Even when not using it directly, its ideas can help me find stuff.
This blog is badly written and is trying to prove some questionable points, but the general message is correct: you don't need segment tree until div1.
You can learn about segment tree whenever you want. Just knowing that there is a data structure that supports queries on segment and updates is not bad. Sometimes you just need sum/min on segment with updates, and that's nice if you can just implement a simple segment tree when you need it.
But learning segment tree early sometimes causes you to start writing segment tree as soon as you see array and queries on segment, before you actually solved the problem. This sucks. I think that forcing is literally the worst habit of newbie cp-ers. Start by solving the problem not caring about the complexity. If you can't answer the query in linear (or quasi-linear) time, no segment tree will help you! Do not approach problems by asking "how do I put it in segment tree".
In many cases there are much simpler solutions than segment tree.
I fully agree. Maybe the blog is badly written also because I haven't specified what I mean with "learn" and "practice" segment tree?
The fact that this comment is completely relevant to today's div2, that happened a bit after the comment, is just perfect.
I don't even understand in which problem it is possible to use segment tree or think that you should use segment tree...
More like the number of people that tried to force greedy onto C :)
Auto comment: topic has been updated by TheScrasse (previous revision, new revision, compare).
i learned how to modify segment tree when i was a hardstuck pupil and couldn’t solve div 2 Cs. Checkmate
Your rating graph is really inspiring. Stuck for a while, but you persisted and saw lots of growth.
I more or less learned segment tree after I became 2000+. Before that, I just used sqrt decomposition everywhere. Being a cyan or blue, why would you learn segment tree, if sqrt decomposition is much more intuitive and easier to understand?
Solution using segment tree might be cleaner/easier to implement (especially if you have practice using segment tree). Also SQRT decomposition might be too slow.
Do I need to know how segment trees actually works before I use it? I think me knowing what it does is enough for me to be able to use it when I have a problem that needs a similar solution and I am aware of it . This is know as black boxing and I've even solved some dp problems this way, I still don't know how it works but I managed to get a working code and an ac during a live contest all on my own.
It can help, but on the long term it's bad. Learning something without actually understanding how it works can make you struggle when you have to go to higher levels
I asked the same question couple of weeks before (https://codeforces.com/blog/entry/111284)
Well, I practiced segment tree when I was in grade 6. (I was not good at it at that time, and now I am still not good at it.)
I think that stack problems tend to be way harder than seg tree problems. People, don't fall for ChatGPT lies!
I learned segt when I was a newbie at the turkey national camp for juniours