## 3 Algorithms
### Manipulation Part
We show that the function \(\mathrm{Update}\) can be implemented so that the total time in a period is proportional to \(k\). Partitions can be manipulated so that the function \(\mathrm{Move}\) runs in constant time. Thus the latter part of the function \(\mathrm{Update}\)is the computational bottleneck. To compute this part efficiently, we implement \(E_{\mathrm{HI}}\) as a doubly linked list (see Figure 5). For each step of the traversal, we memorize the position of the most recently inserted element into \(E_{\mathrm{HI}}\). Note that when we arrive at \(\top\) and go back to the most recent branch node, we have to recover the corresponding position in some way e.g., by means of a stack. When we insert an element \(e_{i}\) into \(E_{\mathrm{HI}}\), we put \(e_{i}\) in the next position of the most recently inserted element. It can be easily verified that all elements placed before (respectively, after) the most recently inserted element are sorted in increasing order of their indices. Thus, in order to scan all elements \(e_{l}\in E_{\mathrm{HI}}\) with \(i<l<j\), it suffices to search from the position of the most recently inserted element until the condition breaks. Since the total number of elements searched in a period is proportional to \(k\), we obtain the time necessary to compute the function \(\mathrm{Update}\) through a period. ```
functionUpdate(\(f\), \(g\), \(p\), \(G\), \(B_{\mathrm{new}}\), \(E_{\mathrm{HI}}\)) \(i\leftarrow\mathrm{V}\left(f\right)\); if the HI arc of \(f\) is selected and \(e_{i}\
ot\in E_{\mathrm{HI}}\)then \(\mathrm{Move}\left(e_{i},p,G,B_{\mathrm{new}}\right)\); \(E_{\mathrm{HI}}\gets E_{\mathrm{HI}}\cup\left\{e_{i}\right\}\); elseif the LO arc of \(f\) is selected and \(e_{i}\in E_{\mathrm{HI}}\)then \(\mathrm{Move}\left(e_{i},p,G,B_{\mathrm{new}}\right)\); \(E_{\mathrm{HI}}\gets E_{\mathrm{HI}}\setminus\left\{e_{i}\right\}\); endif for all \(e_{l}\in E_{\mathrm{HI}}\) with \(i<l<j\)do \(\mathrm{Move}\left(e_{l},p,G,B_{\mathrm{new}}\right)\); \(E_{\mathrm{HI}}\gets E_{\mathrm{HI}}\setminus\left\{e_{l}\right\}\); endfor endfunction functionMove(\(e_{i}\), \(p\), \(G\), \(B_{\mathrm{new}}\)) \(b\leftarrow\) the block of \(p\) which contains \(e_{i}\); if the child of \(b\) is not in \(B_{\mathrm{new}}\)then  Add a new empty block \(b^{\prime}\) to \(p\);  Add \(b^{\prime}\) to \(G\) in such a way that \(b^{\prime}\) has no child and the child of \(b\) is \(b^{\prime}\); \(B_{\mathrm{new}}\gets B_{\mathrm{new}}\cup\left\{b^{\prime}\right\}\); endif  Move \(e_{i}\) to the block corresponding to the child of \(b\);  Delete \(b\) from \(p\) and \(G\) if \(b\) is empty; endfunction
```  
**Algorithm 2** Update the current partition \(p\) and the auxiliary data structures \(G,B_{\mathrm{new}},E_{\mathrm{HI}}\) according to the current node \(f\), the selected arc type of \(f\), and the next node \(g\)  
Let us consider the number of traversed nodes with repetition during the computation. Clearly the number of periods is \(m+1\). For each \(i\)\((0\leq i\leq m)\), let \(P_{i}\) denote the path traced in the \(i\)-th period, which starts with a branch node and ends with \(\top\). The number of HI arcs in \(P_{i}\) is bounded above by \(k\). The head of each LO arc in \(P_{i}\) is a branch node, since the LO arc of a non-branch node is not selected in our traversal. The LO arc of any branch node is traversed exactly once. Thus the total number of LOarcs traversed during the computation is \(m\). Therefore, \(\sum_{0\leq i\leq m}|P_{i}|\leq(m+1)k+m\). We conclude that the time necessary to execute Algorithm 1 is proportional to \(n+km\).