# Engineering a Combinatorial Laplacian Solver: Lessons Learned +
## 3 Implementation
### Logarithmic Time Updates  
While the data structure presented above allows fast repairs for short basis cycles, the worst-case time is still in \(\mathcal{O}(n)\). We therefore also implement the data structure by [PERSON] et al. [12] with \(\mathcal{O}(\log n)\) worst-case time repairs. It is based on link-cut trees [33]. The first observation it uses is that every rooted tree \(T\) on \(n\) nodes can be decomposed into edge-disjoint subtrees intersecting in exactly one node such that each subtree has \(\leq n/2\) nodes. Equivalently, we find a vertex in \(T\), all of whose induced subtrees have size \(\leq n/2\). We call such a vertex a good vertex separator. By recursively finding good vertex separators on the subtrees, we get a recursive decomposition of the whole tree into subtrees. Since the size of the trees halves in each step, the depth of this decomposition is at most \(\mathcal{O}(\log n)\).  
Now, consider a tree \(T\) at one level of recursion with root \(r\) that is split into the subtrees \(T_{0},\ldots,T_{k}\) at the good vertex separator \(d\). Let \(T_{0}\) contain \(r\) without loss.  
**Remark 1**.: _We can implement query and update efficiently by storing several values: (i) \(d_{\mathrm{drop}}\): the total potential drop on the path \(P_{T}(r,d)\), (ii) \(d_{\mathrm{ext}}\): the total flow contribution to \(P_{T}(r,d)\) from vertices below \(d\), and (iii) for every \(u\in V(T)\): \(\operatorname{height}(u):=\sum_{e\in P_{T}(r,u)\cap P_{T}(r,d)}r_{e}\), i.e., the accumulated resistance in common between the \(P_{T}(r,d)\) path and the \(P_{T}(r,u)\) path._  
Then, we can compute \(\operatorname{query}(u)\) as follows: If \(u\in T_{0}\), the potential drop consists of the potential drop \(\operatorname{query}_{T_{0}}(u)\) in \(T_{0}\) and the part \(d_{\mathrm{ext}}\cdot\operatorname{height}(u)\) of the potential drop caused by vertices beyond \(d\). If, however, \(u\in T_{i}\) and \(u\
eq d\), then we have the complete potential drop \(d_{\mathrm{drop}}\) along \(P_{T}(d,r)\) and a recursive potential drop \(\operatorname{query}_{T_{i}}(u)\).  
The \(\operatorname{update}(u,\alpha)\) operation can be implemented similarly: If \(u\
ot\in T_{0}\), we need to adjust \(d_{\mathrm{ext}}\) by \(\alpha\). In all cases, we need to update \(d_{\mathrm{drop}}\) by the \(\operatorname{height}(u)\) part of the \(P_{T}(r,u)\) path in common with \(T_{0}\). Unless \(u=d\), we then need to recursively update the tree \(T_{i}\) with \(u\in T_{i}\). While we could directly implement this recursion, we unroll it to get a more efficient implementation. We can store the complete state of the data structure in a dense vector \(x\) containing the \(d_{\mathrm{drop}}\) and \(d_{\mathrm{ext}}\) values for all recursion levels. For each \(u\in T\), query is then a dot product \(q(u)\cdot x\) with a vector \(q(u)\) containing the appropriate coefficients, and \(\operatorname{update}(u,\alpha)\) is a vector addition \(x:=x+\alpha l(u)\) with a vector \(l(u)\). The vectors \(q(u)\) and \(l(u)\) are sparse with at most \(\mathcal{O}(\log n)\) nonzero entries and can be determined directly from the recursive decomposition in \(\mathcal{O}\big{(}n\log(n)\big{)}\) time (their entries are either \(\operatorname{height}(u)\) or one). [PERSON] et al. [12] provide more details about the unrolling.