tl;dr↵
------------------↵
↵
Please, don't practice segment tree if you are below purple.↵
↵
UPD: ok, yRead [this comment](https://mirror.codeforces.com/blog/entry/111828?#comment-995630).↵
↵
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](https://mirror.codeforces.com/blog/entry/111746) and [this](https://mirror.codeforces.com/blog/entry/111813) if you are cyan, because there are better ways to practice and learn something. [This comment](https://mirror.codeforces.com/blog/entry/111828?#comment-995567) hits the spot: you can "be aware of the segment tree", but it shouldn't be your main weapon as a cyan / blue.↵
↵
↵
UPD: i- 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.↵
↵
WhyShould you master segment tree problems?↵
------------------↵
If you want to solve non-trivial segment tree problems, you should↵
↵
1. actually understand how segment tree works (including time complexity);↵
2. have decent implementation skills;↵
3. 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](https://mirror.codeforces.com/blog/entry/111746): 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.<br>↵
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](https://mirror.codeforces.com/blog/entry/111813): 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](https://mirror.codeforces.com/blog/entry/111746): 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 `2` above). 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](https://mirror.codeforces.com/blog/entry/111813): 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.
------------------↵
↵
↵
UPD: ok, y
↵
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](https://mirror.codeforces.com/blog/entry/111746) and [this](https://mirror.codeforces.com/blog/entry/111813) if you are cyan, because there are better ways to practice and learn something. [This comment](https://mirror.codeforces.com/blog/entry/111828?#comment-995567) 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 want to solve non-trivial segment tree problems, you should↵
↵
1. actually understand how segment tree works (including time complexity);↵
2. have decent implementation skills;↵
3. 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](https://mirror.codeforces.com/blog/entry/111746): 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.<br>↵
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](https://mirror.codeforces.com/blog/entry/111813): 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](https://mirror.codeforces.com/blog/entry/111746): 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 `2` above). 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](https://mirror.codeforces.com/blog/entry/111813): 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.
