Rectangle Sum & Update

来源：Mitbbs, Google First Phone Interview

原帖：http://www.mitbbs.com/article_t1/JobHunting/32574909_0_1.html

题目：
Given a 2D space of maximum size NxN which supports two operations :
[1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
[2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,y2)
inclusive, and there is an infinite stream of such 2 types of operations which have to supported. How would you store the values for efficient updates and retrievals ? （二维线段树  说算法+分析复杂度）

思路：
我gg的电面题目。后来发现这道题在mitbbs和meetqun上曾经出现过多次。
有O(logn)的解法，用quad-tree或者树状数组(binary index tree) 
不过面试官对于O(n)的复杂度是可以接受的。面试官期待的也是O(n)的解法

代码：

 vector<vector<int>> matrix;   
 int M = matrix.size(), N = matrix[0].size();   
   
 // update > > sum   
 // update O(1); sum O(n^2)   
 void update(int r, int c, int val) {   
     matrix[r][c] = val;   
 }   
   
 // (r1,c1) upper left, (r2,c2) bottom right   
 int sum(int r1, int c1, int r2, int c2) {   
     int res = 0;   
     for (int i = r1; i <= r2; ++i) {   
         for (int j = c1; j <= j2; ++j) {   
             res += matrix[i][j];   
         }   
     }      
     return res;   
 }   
   
 // sum > > update   
 // dp[i][j] computer sum of rectangle [0,0] --- [0,j] --- [i,0] --- [i,j]   
 // update O(n^2), sum O(1).   
 vector<vector<int>> dp(M,vector(N,0));   
   
 void compute() {   
     dp[0][0] = matrix[0][0];   
     for (int j = 1; j < N; ++j) {   
         dp[0][j] = dp[0][j-1] + matrix[0][j];   
     }   
     for (int i = 1; i < M; ++i) {   
         dp[i][0] = dp[i-1][0] + matrix[i][0];   
     }   
     for (int i = 1; i < M; ++i) {   
         for (int j = 1; j < N; ++j) {   
             dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i][j];   
         }   
     }   
 }   
   
 void update(int r, int c, int val) {   
     int dif = val - matrix[i][j];   
     for (int i = r; i < M; ++i) {   
         for (int j = c; j < N; ++j) {   
             dp[i][j] += dif;   
         }   
     }   
 }   
   
 int sum(int r1, int c1, int r2, int c2) {   
     if (r1 == 0 && c1 == 0) return dp[r2][c2];   
     else if (r1 == 0) return dp[r2][c2] - dp[r2][c1-1];   
     else if (c1 == 0) return dp[r2][c2] - dp[r1-1][c2];   
     else return dp[r2][c2] - dp[r1-1][c2] - dp[r2][c1-1] + dp[r1-1][c1-1];   
 }   
   
 // sum ~= update   
 // update    
 vector<vector<int>> dp(M,vector(N,0));   
   
 // row dp; dp[i][j] = sum_i_{k = 0}^{k = j};   
 void compute() {   
     for (int i = 0; i < M; ++i) {   
         for (int j = 0; j < N; ++j) {   
             if (j == 0) dp[i][j] = matrix[i][j];   
             else dp[i][j] = dp[i][j-1] + matrix[i][j];   
         }   
     }   
 }   
   
 void update(int r, int c, int val) {   
     int dif = val - matrix[i][j];   
     for (int j = c; j < N; ++j) {   
         dp[r][j] += dif;   
     }   
 }   
   
 int sum(int r1, int c1, int r2, int c2) {   
     int res = 0;   
     for (int i = r1; i <= r2; ++i) {   
         res += c1 == 0 ? dp[i][c2] : dp[i][c2] - dp[i][c2-1];   
     }   
     return res;   
 }