Can someone list some main things which can be done using MO’s algorirhm like
1)Number of distinct elements in [l,r]
2)Sum of all elements in [l,r]
Can anyone suggest more like these?
1 Like
MO’s algorithm is quite general. It’s applicable anytime where you have a static array, a lot of overlapping queries known in advance (offline) and where the can easily add/remove the contribution of an element easily. It’s particularly useful when you work with an operation that is complicated enough to make segment trees hard/impossible to use.
One off the cuff idea for a problem would be: You’re given coefficients A_i and a value x. For a number of queries l,r, evaluate the polynomial a_l + x a_{l+1} + x^2 a_{l+1} + \ldots + x^{r-l} a_r. However, this particular task could also be done with a segment tree with the correct preparation. You should use a segment tree rather than MO when possible, segment trees are much faster and imo much nicer do deal with.
A example where MO’s algorithm is crucial would be something like Powerful array.
Bear in mind that MO’s algorithm is not restricted to arrays. I’ve seen it implemented for queries on trees (specifically where queries are over the shortest path between two nodes).
Perhaps a bit outside the scope of your question, but from my experience when it comes to tasks with queries in general my mental checklist is
- Can queries be done analytically? If so just process the queries online.
- Is the function a good fit for a segment tree? Use a segment tree to solve queries online.
- Is the function weird but fits the requirements for MO? Use MO if O(n \sqrt n) will do.
- Investigate other solutions, specific data structures related to the operation at hand.
8 Likes
Sorry but it is not immediately obvious to me, how would you deal with the polynomial evaluation problem?
@meooow Just for emphasis, the poly evaluation is for a fixed x. For a MO solution, say you start with S := a_2 + a_3 x + a_4 x^2. You can expand left by doing S := Sx + a_1 expand right by doing S := S + a_5 x^3 (exponent will vary with r-l, of course). You can retract from the left by doing S := (S-a_2)/x and retract from the right by doing S := S-a_2 x^2 (again exponent will vary with r-l).
@meooow For a segment tree solution you can premultiply the array with to be a_1, a_2 x, a_3 x^2, ... and then do a sum query and divide by whatever power of x is in the leftmost term. Thinking about it this approach could be problematic if you work with integers (instead of floating point) with large x, but still.
Oh I was assuming x to be a part of the query. I understand you now. For the segment tree approach you can also build the tree with [a_1, a_2,..., a_{n-1}, a_n] as the leaves, [a_1+a_2x, a_3+a_4x, ..., a_{n-1}+a_nx] as the second level, [a_1+a_2x+a_3x^2+a_4x^3,...] on the third, and so on. Then to answer a query you don’t need division, just multiplication of terms by certain powers of x when putting together the answer.
1 Like