题目描述

先前，小红有一个数组，要求这个数组中选择若干个数，使得选出的数之和与剩下的数之和的差值绝对值尽可能小。

思路：二维前缀和+二分

这个问题其实就是在求一个靠近 $\frac{sum}{2}$ 的最近的数，不过这个数是由正方形中的数的和组成的。

那么可以考虑枚举正方形的左上角端点，然后二分正方形的边长，找到一个正方形数之和大于等于 $\frac{sum}{2}$ 的最小边长。

而这里判断时需要快速求出一个正方形内数的和，可以通过预处理二维前缀和，然后查询可以$O(1)$计算出。

时间复杂度：$O(nmlogn)$