The property holds for all (i,j) if and only if it holds for all prefixes and all suffixes. You can prove this easily with pen and paper.
Prefix and suffix sums can be checked in linear time.