TheScrasse's blog

By TheScrasse, history, 2 weeks ago, In English

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

  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: 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 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: 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.

 
 
 
 
  • Vote: I like it
  • -19
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

I became blue from cyan after I learnt segment tree.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    Correlation $$$\nRightarrow$$$ causation.

    Did you become blue thanks to a segment tree problem?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      At least I got 66 pts.

      I wouldn't have got it if I hadn't known segment tree.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Can you send the link of the problem?

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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.

            Spoiler
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm still cyan after learning it. But basic segtrees (I think) are worth to learn maybe?

»
2 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

based

»
2 weeks ago, # |
  Vote: I like it +90 Vote: I do not like it

I'm sorry, last introductory CP course at KAIST I lectured, I teached segment tree but not DFS.

»
2 weeks ago, # |
  Vote: I like it +101 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    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".

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      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"?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it -22 Vote: I do not like it

        There is a middle way between problems "ready for you" and problems whose rating is 1000 points higher than yours.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +51 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it -29 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it +39 Vote: I do not like it

              I cited your sentence which I objected. Why do you want to talk about different things?

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it +21 Vote: I do not like it

                  It is a different thing.

                  Anyway, I agree to your last paragraph, so we can settle this.

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it -10 Vote: I do not like it

              So just because of this guy, you concluded that everyone below purple shouldn't learn segment trees?

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I think I've seen many examples of blogs like that (e.g., the 2 linked blogs in just 2 days).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Is Darooha (Splay tree algo founder) also allowed to learn about segment trees?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it +7 Vote: I do not like it

                  There are exceptions to the rule.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  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 ?

»
2 weeks ago, # |
  Vote: I like it +60 Vote: I do not like it
Спойлер
»
2 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Very stupid opinion

»
2 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

»
2 weeks ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

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.

»
2 weeks ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by TheScrasse (previous revision, new revision, compare).

»
2 weeks ago, # |
Rev. 2   Vote: I like it +41 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    "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?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      So everyone who knows segment trees should be able to solve 2500 rated segment tree problems? Btw, blue $$$\neq$$$ cyan.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it -11 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
          Rev. 2   Vote: I like it -10 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it -6 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it -10 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                  Rev. 2   Vote: I like it +3 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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 combine function (so he understands the implementation of segment tree), but that's not enough to solve the problem.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it +5 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it -6 Vote: I do not like it

                  It depends on the definition of "learning".

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Alright, you do not understand DP because you cannot solve 3500 DP problems.

»
2 weeks ago, # |
Rev. 3   Vote: I like it +28 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by TheScrasse (previous revision, new revision, compare).

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it +47 Vote: I do not like it

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 am aware that segment tree exists, can implement or copypaste RMQ/RSQ/something else standard, I know that segment tree supports these operations. I use segment tree as a black box"
  • "I understand how the segment tree works on the inside, can implement it from scratch off the top of my head with some non-standard operations, I can derive the requirements for the nodes of the segment tree from the operations it has to support"

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:

  • Most of these problems will not be segment tree problems. An actual segment tree problem requires much more knowledge that ones typically solved by blue-rated and lower-rated participants.
  • And since the problems you solve with segment tree most likely won't be segment tree problems, it means that model solutions will use something simpler. In other words, your solution will be overkill for the problem, and maybe if you try to think how to solve the problem without a segment tree, you'll come up with a solution that is much easier to code and debug. I've seen a lot of this happening on my rounds, where model solutions for some problems require no difficult data structures and are about 20-30 lines long, but participants instead submit something with segment tree that is about thrice as long. Moreover, thinking about easier solutions will make you improve in the long run, since it's practice of general problem-solving and solution simplification methods which will help you in any contest.

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).

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +54 Vote: I do not like it

    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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -21 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        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)

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it -21 Vote: I do not like it

          For example, something like segment tree descent.

          If it is unclear what I mean by segment tree descent (maybe it's called differently?)
          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
            Rev. 2   Vote: I like it +27 Vote: I do not like it

            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...

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it +15 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks ago, # ^ |
                Rev. 3   Vote: I like it +7 Vote: I do not like it

                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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by TheScrasse (previous revision, new revision, compare).

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the suggestion. Anything else you can recommend ?

I am just solving the questions linearly by filtering the questions by ratings.

»
2 weeks ago, # |
  Vote: I like it +55 Vote: I do not like it

don't write blogs if you are below master

»
2 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    It's not easy to realize something isn't useful, if no one else points it out.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It isn't ridiculing, the more experienced have to guide the less experienced.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      No one asked for his guidance. Allow me experiment and find what works for me.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          how the fuck are you relating discoveries in history to learning competitive programming?

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it -10 Vote: I do not like it

            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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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!

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it +15 Vote: I do not like it

            It's not just my rounds only, I don't feel like it's directed at my contests in particular.

            you don't ever get to reuse the ideas

            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.

»
2 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it +134 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I fully agree. Maybe the blog is badly written also because I haven't specified what I mean with "learn" and "practice" segment tree?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    The fact that this comment is completely relevant to today's div2, that happened a bit after the comment, is just perfect.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't even understand in which problem it is possible to use segment tree or think that you should use segment tree...

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        More like the number of people that tried to force greedy onto C :)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by TheScrasse (previous revision, new revision, compare).

»
2 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

i learned how to modify segment tree when i was a hardstuck pupil and couldn’t solve div 2 Cs. Checkmate

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your rating graph is really inspiring. Stuck for a while, but you persisted and saw lots of growth.

»
2 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

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?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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.

»
2 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I asked the same question couple of weeks before (https://codeforces.com/blog/entry/111284)

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't i am below green

»
2 weeks ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it
ChatGPT has the answer
  • »
    »
    13 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think that stack problems tend to be way harder than seg tree problems. People, don't fall for ChatGPT lies!

»
2 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I learned segt when I was a newbie at the turkey national camp for juniours