I've been reading this paper on the persistence algorithm:
https://people.mpi-inf.mpg.de/~mkerber/ck-phcwat-11.pdf
Given a matrix M with columns $M_j$.
it states on page 3 that we may add two columns $M_j+ M_i$ and store it at $M_j$ in time $\#M_i * log(\#M_i + \#M_j)$
where $\#M_i$ is the number of nonzero entries of column j.
using a binary search tree to represent the nonzero entries of each column.
Can anyone explain how the column addition would work? I think I'm just missing something very simple.
see https://www.geeksforgeeks.org/merge-two-balanced-binary-search-trees/
say we have: $M_1 \gets M_1+M_2$
representing each bit vector $M_i$ by a binary tree $T_i$ with nonzero entries as nodes, we may add two bit vectors $M_1$ and $M_2$ by merging binary trees $T_2$ into $T_1$. For each node n $\in T_2$, if $T_1 $and $T_2$ share the node n, we delete that node in $T_1$. otherwise we insert the node n into $T_1$.