363. Max Sum of Rectangle No Larger Than K

I don't have idea to solve this problem so I followed the top rated solution. First of all, the solution follows idea in the link (https://www.youtube.com/watch?v=yCQN096CwWM) to solve maximum sum rectangle submatrix in a matrix. And the problem modified it a little bit to get the closest sum to K instead of maximum sum.
Let's say we have four points, left, right, top and bottom. A submatrix can be determined by these four points. Note left and right point can be determined by columns and top and bottom point can be determined by rows. Once we fixed the left and right points and do the sum from left to right for each row, the original problem becomes finding the subarray that has closest sum to K. Therefore, we can have two loops for all combinations of left and right.
To solve the subarray problem, we follow the same idea to do the cumulative sum. For subarray (i, j], we can compute the subarray sum by cum[j]-cum[i]. For the requirement cum[j]-cum[i] <= k, for a new cum[j], all we need to do is to search the cum before such that cum[i] >= cum[j]-k. Now, the problem become find the right cum[i] before j. This can be done by binary search or by building binary search tree.
The solution uses set<int> which is a binary search tree. Also it is very important to insert a 0 in first place because for cum[0], the requirement cum[j]-cum[i] <= k isn't valid since there isn't i. However, we can think of cum[i] as 0 and that's why we need to insert 0 initially.

1:  class Solution {  
2:  public:  
3:    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {  
4:      int row = matrix.size();  
5:      if (row == 0) return 0;  
6:      int col = matrix[0].size();  
7:      int res = INT_MIN;  
8:      // left point  
9:      for (int l = 0; l < col; l++) {  
10:        vector<int> sum(row, 0);  
11:        // right point  
12:        for (int r = l; r < col; r++) {  
13:          // from top point to bottom point  
14:          for (int i = 0; i < row; i++) {  
15:            sum[i] += matrix[i][r];  
16:          }  
17:          // for cum[], we want find cum[j]-cum[i] <= k  
18:          // so the problem becomes finding cum[i] >= cum[j] - k  
19:          // we use binary search tree here for cum[]  
20:          set<int> cum;  
21:          cum.insert(0);  
22:          int cum_j = 0, best = INT_MIN;  
23:          for (int j = 0; j < sum.size(); j++) {  
24:            cum_j += sum[j];  
25:            // get cum[i] such that cum[i] >= cum[j]-k;  
26:            auto cum_i = cum.lower_bound(cum_j-k);  
27:            if (cum_i != cum.end()) best = max(best, cum_j-*cum_i);  
28:            cum.insert(cum_j);  
29:          }  
30:          res = max(res, best);  
31:        }  
32:      }  
33:      return res;  
34:    }  
35:  };