# matrix columns represented by binary search tree

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.

## 1 Answer

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$.