### ainta's blog

By ainta, 5 years ago, , I found a problem about dynamic MST.

To solve it, I read this paper.

But I cannot understand it(Is it divide-and-conquer?)  Comments (7)
 » 5 years ago, # | ← Rev. 2 →   At first you can try to solve it by sqrt-decomposition:1) Divide all queries to sqrt(max(n,m,k)) blocks.2) In each block firstly add all edges that will be modified in block (denote it S) to mst in any order, and then try to add edges not from S one by one in non decreasing order to mst. If edge not from mst will be added then it should be in any mst in block, so you can merge the ends of that edge and make the number of vertexes equal to O(blockSize).3) Now you should try to add edges not from S in non decreasing order to mst. Then each edge that will not be added to mst can't be in mst in block. So you can remove that edges and make number of edges equal to O(blockSize).4) Finally you can simply build mst for each query in O(blockSize * alpha) time.Okay. To get faster solution let's do the same in divide and conquer manner over queries: every time when we entering our solve function we should make the size of graph equal to the number of queries that we should process in function. So we have solution with complexity O(n * log^2n), cause we should sort the edges in block. Actually it's difficult to get complexity O(n logn) (I've not can) cause in paper authors telling us that we should firstly change all edges length by their numbers in sorted list of all lengths and then sort edges with integral lengths in O(numberOfEdges) time, but in that case we will get the constant about 16 or 32, cause the length of array will be different each time from (1 to n).
•  » » » If you start with a tree (as opposed to starting with no edges), then you when you are given an edge $e$ from $u$ to $v$ of cost $c$, you can find the maximum value edge on the path from $u$ to $v$ and if its value is greater than $c$, you can replace it with $e$, obtaining a tree with a smaller cost. All of these operations can be done with a LCT. Here is a possible implementation.
•  » » There is an online solution that works in $O(m^{1/2})$ query time. This algorithm uses top trees. I don't know it, but I heard it have many applications in dynamic graph algorithms. The best known bound is $O(\log^4 n)$ amortized per query. This would be impossible to phrase as a competitive programming task, but I think it's an interesting read?