Please subscribe to the official Codeforces channel in Telegram via the link ×

What to do for query problems?

Revision en1, by rangerscowboys, 2024-05-06 03:34:09

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?



  Rev. Lang. By When Δ Comment
en1 English rangerscowboys 2024-05-06 03:34:09 1260 Initial revision (published)