It's been a while, but we are back with another Codeforces Gym!
Translated statements and my solutions are here, and statements are also added to the gym itself.
Today I will talk about various problems involving range queries in general, and segment trees in particular.
First, I describe simple problems with range queries, such as sum/min/max on a segment without any updates. It is essential to understand that sometimes you don't need any advanced data structures to process range queries. In some problems, you can write a for loop, use prefix sums, or precompute a sparse table. However, when update queries come into play, the need for better data structures arise, and here segment tree, and lazy segment tree come into play. Their applications can seem practically unlimited, but at the very end, we realize that there are some limitations. Because of that, we introduce our final data structure, which supports Split and Merge operations.
Watch the theory here, or skip straight to the practice session if you already know the theory.
Thank you nskybytskyi.
Starting in 15 minutes!
really excited!!!
thank you for putting in the effort to do such an amazing thing.
Can we please have more practice problems on segtrees? These are somewhat standard, lecture-style.
I somewhat agree with you. The problems from this gym are designed to introduce people to the topic of range queries. If you already solved them you are welcome to the sequel gyms: first and second. Unfortunately, I haven't translated them just yet, so you will need the help of the google translate or something, and potentially https://2cyr.com/decode/?lang=en to fix the encoding. I will add English statements to the gyms once I translate the problems.
Hey guys, I have encountered a problem in cases problem Dynamic Sum Queries. My code fails for the second test case
Thank you, in advance.
Could you please at least post the link to the problem so that people can test their solutions?
Your text to link here...
Your solution fails the following testcase:
Your output is 3 and the expected answer is 2.
It happens because you always add
j - a[i]
regardless of whether the value ofa[i]
has changed or not. Update the value ofa[i]
(a[i]+=j;
) after the query to your Fenwick Tree and you should be fine.Speaking of Fenwick Tree, you can also watch my video about it for some more practice problems and not-so-standard applications.
Hey nskybytskyi can you please make a contest mashup or question list from easy to hard so that we can try and maybe later you can make a editorial video!