You need two segment trees — one for the rows and one for the columns. Cuts divide the rows and columns in some parts. In each leaf node store the length of the part that the current row/column belongs to. Actually, my solution uses another two segment trees where I store the starting index for the part that this row/column belongs to and I use binary search to find in which part the cut is. Check my code for better understanding.