Hello coders, hope you are well in these times! :)
I would like to ask you something regarding "subarray problems" (problems where you need to find subbaray(s) / count subarrays that meet certain specifications). So, the questions: What are useful algorithms for these kind of problems ? Do you have any nice tricks that could help out ? :)
Thank you in advance!
Your question is not well crafted.
There are many variations of subarray query questions. Similarly there are many different types of algorithms to solve them. It is not possible to list them specifically.
If you have a specific problem that you need help for, just ask directly.
Thank you for your answer! :)
I don't have any specific problem I need help with. I just want to get better at solving those problems, so now I am thinking are there any useful, common algorithms that can possibly be used when solving these problems. When you said there are many different types of algorithms to solve them, I completely understand that, so that's why I am asking: common ones, ones that you see the most often and that are somehow useful.
Once more, thank you for your answer! :)
Unfortunately, such algorithms are usually tailored specifically to the problem (so your question is still a bit pointless). I can name you some generic techniques though: range tree, square root decomposition, dynamic programming, binary search.
If you're talking about range queries, some things I know off the top of my head are binary indexed trees, segment trees, implicit treaps, Mo's algorithm, wavelet trees, square root decomposition, prefix sums, sparse tables, this static range query DS that I found in Benq's Github repo, and merge sort trees.