itspyre's blog

RQ Practice
By itspyre, history, 3 weeks ago, In English

Hi y'all! I wanted to post this blog to ask some of the more experienced coders here how could I learn and get better at range query problems or for that matter structures like segment trees. I would also appreciate if I got some advice on DP. Thanks!

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

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

as a more experienced coder,quit drums

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It is weird for me to say this as a newbie but i would recommend reading the editorial and coming back to it after a week or so and try to solve it without looking at the editorial again.

idk if it will work for u but it did for me so yea trust gng :D

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

I list some simple segment-tree problems.

Luogu-P3373(A simple segment-tree with two lazy-tag)

Luogu-P1253(A simple segment-tree with two lazy-tag)

Luogu-P1438(Lazy-tag but more hard)

Luogu-P4513(An interesting problem)

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Although I'm a pupil (so you could say that I'm not as experience as you are), I think that you should try doing RQ problems on CSES.

→ Reply
  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I think Luogu has lots of range query problem and contained all levels and is friendly to beginners.

    → Reply
  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Firstly i respect opinions of all elo and believe that elo isn't a reliable parametric to judge experience, secondly some other person also said cses rq is a good place so thanks to both of you it's a good source. Have a good day :)

    → Reply
»
3 weeks ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

If you want to learn more range query data-structure.

You can learn Binary Indexed tree, Sparse Table or some Balanced Binary Search Tree.

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Very good

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

for the seg trees and dp (and lots of other stuff), cses problemset is a really good resource https://cses.fi/problemset/

→ Reply
  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    yes im aware of cses dp ive solved them quite a bit but didnt know about rq thanks!

    → Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

A lot of usaco problems from like 2016-2019ish have very good semi-standard solutions

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I'd start with point updates and range sums using a Fenwick tree, then point updates and range minimum with a segment tree. That makes the difference between the structures easier to see than learning all their variants at once.

With a Fenwick tree, assigning a value isn't the same as adding it. To set a[i] = x, add x - old_a[i] to the tree and update the stored array value.

For lazy propagation, start with range add and range sum. Adding x to a segment of length len increases its sum by x * len. The lazy tag stores the addition still owed to its children.

Also, test your implementations on arrays of size 1 to 10 against a plain loop. Mix random updates and queries, especially single-element ranges and repeated updates to one position. This catches indexing and lazy-tag mistakes much faster than staring at the code.

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

also for dp atcoder has a good problemset: https://atcoder.jp/contests/dp/tasks

for segtrees you can check the cf edu section

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

Next monday there is an official educational contest focused on segment trees on AtCoder: https://atcoder.jp/contests/aalc001

→ Reply