The problem stated in the title is the following: given an $n\times n$ binary matrix $M=\left(m_{rc}\right)$ report the number of $1$'s in a query rectangle
$[i,j]\times[h,k]$
$1\le i\lt j\le n,\, 1\le h\lt k\le n$
i.e. $\sum\limits_{r=i}^{j}\sum\limits_{c=h}^k m_{rs}$
In the 2014 article Reporting and counting maximal points in a query orthogonal rectangle in theorem 2 a complexity bound of $O\left(\frac{\log n}{\log\log n}\right)$ algorithm is stated for the special case that the number of $1$'s equals $n$
Questions:
- have there been improvements on the above complexity bound
- what is known an arbitrary number of $1$'s
