VitalyKo's blog

How to do MO on trees without extra check for LCA?
By VitalyKo, 7 months ago, In English

Let's say we have values on nodes, not edges (with edges everything is fine) and want to answer some path queries with MO algorithm

Usual implementation would do something like this

    move l, r
    ...
    if (u != lca && v != lca) toggle(lca);
    ans[query_id] = ...;
    if (u != lca && v != lca) toggle(lca);

Which is absolutely ok when toggling each node works in $$$O(1)$$$, but that's not always the case. We can have some values inside the node $$$v$$$ and toggling takes $$$size(values[v])$$$ operations. Then that extra toggle for lca node would break the time complexity.

I can think of some fixes to that:

1) Change something in the algorithm so you wouldn't need to extra toggle for lca.

2) Change the way you sort the queries, so you have a small amount of queries segments where lca is the same, so you can toggle it once in the start of the segment and toggle it back in the end.

3) Create a new tree where each node would have only a single value but it will be still possible to represent each path with a segment (and we won't increase total sizes too much).

But I can't find how to do any of these. Any suggestions?

  • Vote: I like it
  • +76
  • Vote: I do not like it

»
7 months ago, hide # |
← Rev. 2  
Vote: I like it +8 Vote: I do not like it

As for 1) unless someone comes up with some drastically different approach instead of some slight modification of the Euler tour, I don't think that it's possible, since the vertice cannot appear more than $$$const$$$ number of times, and there are $$$O(deg_v)$$$ non-intersecting segments all of which require the vertex $$$v$$$ to be in the segment at least once, and if $$$size(values[v]) \simeq n$$$ and $$$deg_v \simeq n$$$ then Mo isn't possible.

As for 3) I also don't have many ideas, feels kinda similar to altering the euler tour, but idk

As for 2), I have a better complexity than $$$O(n^2)$$$, but still not really good. Let $$$m$$$ be the sum of sizes of values, then I can do something like $$$O((n + m)^{\frac{5}{3}}))$$$. Basically it's a 3D Mo, since each query can be parametrized with 3 values $$$l$$$, $$$r$$$, $$$lca$$$, and now we're traversing the space $$$[1, 2, \ldots, m]^3$$$. Since there is more freedom in moving in the third dimension than just increase/decrease, maybe it's possible to get a better complexity.

→ Reply