Let A be a $N*N$ matrix. Now A is defined in a special manner:
Each row of A is defined by two integers L and R ($0\le L,R\le {N-1}$), such that all elements from the $L^{th}$ to the $R^{th}$ are all $1$'s in this row. All rest elements of thisrow are $0$.
Like for example if the row identifiers for our matrix are $[0,1], [2,3], [0,0], [4,4]$. Our matrix will look like:
$$ A = \begin{bmatrix} 1 & 1 & 0 &0 \\ 0 & 0 & 1 &1 \\ 1 & 0 & 0 &0 \\ 0 & 0 & 0 &1 \end{bmatrix}$$
Now I have to find the rank of such a matrix in $GF(2)$. I am aware of a $O(N^2)$ solution to the above problem. But I was curious if we could do better because of the special form of the matrix?