rangerscowboys's blog

By rangerscowboys, history, 5 weeks ago, In English

Howdy Codeforces!

Recently, while solving previous Codefoces problems, I have seen many query problems. What I mean by query problems are: you are given q queries, like updating and printing something.

This is what I have gathered from query problems: - Arrays can be used for simple query problems. - Prefix sums can sometimes be used for query problems (No Updates Ranged Query) - Sets/Multisets are often used for query problems that need O(logn) operations. - Ordered set is used for some query problems (Point Update Range Query) - Segment tree (with lazy propagation on ranged updates) can be used often for Point Update Range Query, Range Update Point Query, Range Update Range Query.

Of course, although segment tree is a solution for many query problems, it isn't easy to code, especially for specialists like me.

Me personally, I have started to direct myself to thinking set/multiset first, because it seems to often work.

Did I miss any ways to solve query problems? Does anyone have a segment tree template that I can use (with lazy propagation)? Do you all have a different approach to query problems than what I do? What do you all see most often as the solution to query problems?

Thanks!

  • Vote: I like it
  • +8
  • Vote: I do not like it

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

Have you considered ordered_set cheese? Since it's applicable to a couple of those problems. Fenwick tree also works in some cases.

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

You missed mo's algorithm and possibly sparse table as well.

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

There is so many variety on what a query problem can be, that there's no one way to solving them. Though as a specialist you should be fine with just prefix sum and binary search. Data structures you mentioned can help too, but I didn't see a lot of them below Div2D and they usually appear only at Div2E and harder problems.

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

    This might be from a while ago, but while solving previous Codeforces query problems, they were like question C or D in Div2. I really want to solve 3 in Div2s.

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

maybe you can learn fenwick tree?

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

    My teacher once told me if you learn segment tree, you will never need to learn fenwick tree... and ig he does have a point lol –– the implementation for segment tree does feel more straightforward, and segment tree does have more capabilities than fenwick tree.

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

      yes, segment tree > fenwick tree. but since a segment tree "isn't easy to code" you could try to code a fenwick tree which are only about 10-15 lines of code and easy to memorize.

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

        That's partly why I asked for a segment tree template lol

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 4   Vote: I like it +1 Vote: I do not like it

          Bru, you could've just asked me over google chat... I legit have a segment tree template that's very good which uses lazy prop.

          lazy prop segtree template
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I might be wrong, but what can fenwick tree do that segment tree can't do?

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

      Anything that's possible to be done w/ fenwick tree can be done w/ segment tree(at least to my knowledge). It's just like what M1ngXu mentioned above: fenwick tree is faster to implement.

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

This is my lazy propagation segment tree template, I tried to learn it with chatgpt i asked the multiple versions of lazy propagation before finalizing this one, may be you can try that too

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

    this is really memory consuming, use integers instead of pointers to improve it. (or dont use integers at all). Dynamic segtrees almost never need lazy propogation so that's a non issue.

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

      actually i know this memory consuming, but the reason i love this implementation is because i dont have to focus multiple variable in arguments of fuctions like QL, QR, NodeL , NodeR and for begginers like me it gets really confusing. so i tried this implementation with node class as seperate so this saves me from commiting mistakes, i dont know much about the dynamic segment tree, i just found this usefull, because its has similarities from Leetcode type of coding format. where everything is in class nicely.