Think first about how you can determine the number of 1's in any row in O(log n) time.