LeetCode 308 - Range Sum Query 2D - Mutable


Leetcode 304 - Range Sum Query 2D - Immutable
https://kennyzhuang.gitbooks.io/leetcode-lock/content/308_range_sum_query_2d_-_mutable.html
Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10
Note:
  1. The matrix is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRegion function is distributed evenly.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.
http://shibaili.blogspot.com/2018/11/308range-sum-query-2d-mutable.html
read heavy - 那就正常写，矩阵里面直接存cumulative sum. 读是O(1), 写是O(m * n)

write heavy -  bit, 读写都是O(log m * log n)


X.

Idea: it should come out some way to store the computed results of sums and get region sum based on the pre-computed results. “Range Sum” is a good idea in this case, because every element in the matrix stores the sum of all previous elements in this row and it can get the range sum by difference of end element and previous element of start point.

https://yeqiuquan.blogspot.com/2017/06/308-range-sum-query-2d-mutable.html
We use int[][] colSum to store the prefix sum of each column.

colSum[i][j] denotes the sum of first i elements in column j.

To update an element, we find the corresponding column and update all the prefix sums that rely on this element.
    public int[][] colSum;
    public int[][] matrix;
    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        if (matrix == null || matrix.length == 0) {
            return;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        colSum = new int[m + 1][n];
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < n; j++) {
                colSum[i][j] = colSum[i - 1][j] + matrix[i - 1][j];
            }
        }
    }
    
    public void update(int row, int col, int val) {
        for (int i = row + 1; i < colSum.length; i++) {
            colSum[i][col] = colSum[i][col] - matrix[row][col] + val;
        }
        matrix[row][col] = val;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int j = col1; j <= col2; j++) {
            sum += colSum[row2 + 1][j] - colSum[row1][j]; 
        }
        return sum;
    }


X. 2D BIT
https://zhuhan0.blogspot.com/2017/09/leetcode-308-range-sum-query-2d-mutable.html
https://zhuhan0.blogspot.com/2017/09/leetcode-308-range-sum-query-2d-mutable.html


Say height = h and width = w.
  • Constructor: hw logh logw.
  • update(): logh logw.
  • sumRegion(): logh logw.
    private int[][] matrix;
    private int[][] tree;
    private int height;
    private int width;

    public NumMatrix(int[][] matrix) {
        height = matrix.length;
        if (height == 0) {
            return;
        }
        width = matrix[0].length;
        this.matrix = new int[height][width];
        tree = new int[height + 1][width + 1];
        
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }
    
    public void update(int row, int col, int val) {
        int diff = val - matrix[row][col];
        matrix[row][col] = val;
        
        for (int i = row + 1; i <= height; i += (i & -i)) {
            for (int j = col + 1; j <= width; j += (j & -j)) {
                tree[i][j] += diff;
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum(row2, col2) - sum(row1 - 1, col2) - sum(row2, col1 - 1) + sum(row1 - 1, col1 - 1);
    }
    
    private int sum(int row, int col) {
        int sum = 0;
        for (int i = row + 1; i > 0; i -= (i & -i)) {
            for (int j = col + 1; j > 0; j -= (j & -j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }


    int[][] tree;
    int[][] nums;
    int m;
    int n;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        m = matrix.length;
        n = matrix[0].length;
        tree = new int[m+1][n+1];
        nums = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }

    public void update(int row, int col, int val) {
        if (m == 0 || n == 0) return;
        int delta = val - nums[row][col];
        nums[row][col] = val;
        for (int i = row + 1; i <= m; i += i & (-i)) {
            for (int j = col + 1; j <= n; j += j & (-j)) {
                tree[i][j] += delta;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (m == 0 || n == 0) return 0;
        return sum(row2+1, col2+1) + sum(row1, col1) - sum(row1, col2+1) - sum(row2+1, col1);
    }

    public int sum(int row, int col) {
        int sum = 0;
        for (int i = row; i > 0; i -= i & (-i)) {
            for (int j = col; j > 0; j -= j & (-j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }

https://www.cnblogs.com/yrbbest/p/5058571.html




http://bookshadow.com/weblog/2015/11/18/leetcode-range-sum-query-mutable/
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.
解法I：线段树（Segment Tree）的基础应用
class NumArray(object): def __init__(self, nums): self.nums = nums self.size = size = len(nums) h = int(math.ceil(math.log(size, 2))) if size else 0 maxSize = 2 ** (h + 1) - 1 self.st = [0] * maxSize if size: self.initST(0, size - 1, 0) def update(self, i, val): if i < 0 or i >= self.size: return diff = val - self.nums[i] self.nums[i] = val self.updateST(0, self.size - 1, i, diff, 0) def sumRange(self, i, j): """ if i < 0 or j < 0 or i >= self.size or j >= self.size: return 0 return self.sumRangeST(0, self.size - 1, i, j, 0) def initST(self, ss, se, si): if ss == se: self.st[si] = self.nums[ss] else: mid = (ss + se) / 2 self.st[si] = self.initST(ss, mid, si * 2 + 1) + \ self.initST(mid + 1, se, si * 2 + 2) return self.st[si] def updateST(self, ss, se, i, diff, si): if i < ss or i > se: return self.st[si] += diff if ss != se: mid = (ss + se) / 2 self.updateST(ss, mid, i, diff, si * 2 + 1) self.updateST(mid + 1, se, i, diff, si * 2 + 2) def sumRangeST(self, ss, se, qs, qe, si): if qs <= ss and qe >= se: return self.st[si] if se < qs or ss > qe: return 0 mid = (ss + se) / 2 return self.sumRangeST(ss, mid, qs, qe, si * 2 + 1) + \ self.sumRangeST(mid + 1, se, qs, qe, si * 2 + 2) 解法II：树状数组（Binary Indexed Tree / Fenwick Tree）
class NumArray(object): def __init__(self, nums): self.sums = [0] * (len(nums) + 1) self.nums = nums self.n = len(nums) for i in xrange(len(nums)): self.add(i + 1,nums[i]) def add(self,x,val): while x <= self.n: self.sums[x] += val x += self.lowbit(x) def lowbit(self,x): return x & -x def sum(self,x): res = 0 while x > 0: res += self.sums[x] x -= self.lowbit(x) return res def update(self, i, val): self.add(i + 1, val - self.nums[i]) self.nums[i] = val def sumRange(self, i, j): if not self.nums: return 0 return self.sum(j+1) - self.sum(i)

X.
https://leetcode.com/discuss/70948/15ms-easy-to-understand-java-solution
We use colSums[j][i] = the sum of ( matrix[0][j], matrix[1][j], matrix[2][j],......,matrix[i - 1][j] ).
private int[][] colSums;
private int[][] matrix;

public NumMatrix(int[][] matrix) {
    if(   matrix           == null
       || matrix.length    == 0
       || matrix[0].length == 0   ){
        return;   
     }

     this.matrix = matrix;

     int m   = matrix.length;
     int n   = matrix[0].length;
     colSums = new int[n][m + 1];
     for(int i = 0; i < n; i++){
        for(int j = 1; j <= m; j++){
            colSums[i][j] = colSums[i][j - 1] + matrix[j - 1][i];
        } 
     }
}
//time complexity for the worst case scenario: O(m)
public void update(int row, int col, int val) {
    for(int i = row + 1; i < colSums[0].length; i++){
        colSums[col][i] = colSums[col][i] - matrix[row][col] + val;
    }

    matrix[row][col] = val;
}
//time complexity for the worst case scenario: O(n)
public int sumRegion(int row1, int col1, int row2, int col2) {
    int ret = 0;

    for(int j = col1; j <= col2; j++){
        ret += colSums[j][row2 + 1] - colSums[j][row1];
    }

    return ret;
}
https://discuss.leetcode.com/topic/30250/15ms-easy-to-understand-java-solution/12
This can be improved to O(1) space. I changed it to row sum version. BTW I think this solution is better than the BIT version since it's quite hard to give a BIT solution during an interview (unless you have seen BIT before).
    // O(1) space
    int[][] mMatrix = null;
    int m = 0;
    int n = 0;
    
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
        mMatrix = matrix;
        m = matrix.length;
        n = matrix[0].length;
        // rowSums[i][j] = rowSums[i][0] + rowSums[i][1] + ... + rowSums[i][j]
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                matrix[i][j] = matrix[i][j] + matrix[i][j - 1];
            }
        }
    }
    // O(n)
    public void update(int row, int col, int val) {
        // handle col = 0 differently
        int originalValue = col == 0 ? mMatrix[row][0] : mMatrix[row][col] - mMatrix[row][col - 1];
        int diff = val - originalValue;
        for (int j = col; j < n; j++) {
            mMatrix[row][j] += diff;
        }
    }
    // O(m)
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int result = 0;
        for (int i = row1; i <= row2; i++) {
            // handle col = 0 differently
            result += col1 == 0 ? mMatrix[i][col2] : mMatrix[i][col2] - mMatrix[i][col1 - 1];
        }
        return result;
    }
https://kennyzhuang.gitbooks.io/leetcode-lock/content/308_range_sum_query_2d_-_mutable.html
public class NumMatrix {

    int[][] tree;
    int[][] nums;
    int m;
    int n;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        m = matrix.length;
        n = matrix[0].length;
        tree = new int[m+1][n+1];
        nums = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }

    public void update(int row, int col, int val) {
        if (m == 0 || n == 0) return;
        int delta = val - nums[row][col];
        nums[row][col] = val;
        for (int i = row + 1; i <= m; i += i & (-i)) {
            for (int j = col + 1; j <= n; j += j & (-j)) {
                tree[i][j] += delta;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (m == 0 || n == 0) return 0;
        return sum(row2+1, col2+1) + sum(row1, col1) - sum(row1, col2+1) - sum(row2+1, col1);
    }

    public int sum(int row, int col) {
        int sum = 0;
        for (int i = row; i > 0; i -= i & (-i)) {
            for (int j = col; j > 0; j -= j & (-j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
}

http://www.1point3acres.com/bbs/thread-210173-1-1.html
其实后来发现我给的解法 好像就是quad tree。
对于quad tree每一个region，存总的sum， 和所有row的 和 所有column 的sum。. visit 1point3acres.com for more.
递归过程t(n) = t(n/2) +O(n) 因为只有一个quadrant 需要 recursive call， 其他的可以直接根据region 存的值算出来 所以是o（n）

at
Labels: , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts

  • Archives
  • HackerRank: Pacman A*
    HackerRank: Pacman A* In the previous game, you performed UCS on the PacMan grid. In this game we use AStar algorithm to reduce the nodes...
  • LeetCode 471 - Encode String with Shortest Length
    Related:  LeetCode 394 - Decode String http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/ Given a  non...
  • HackerRank: PacMan - BFS
    HackerRank: PacMan - BFS In the previous game, you performed DFS on the PacMan grid. It was seen that DFS might not always give the short...
  • DropBox Interview Misc
    https://paper.dropbox.com/doc/Interview-Notes-Dropbox-wl7npLjRBjrAKA5AOBsaM Behavioural https://www.paysa.com/blog/2017/04/05/what-to...
  • Buttercola: Buddy System
    Buttercola: Buddy System Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold: 1. A node...
  • Print all sequences of given length | GeeksforGeeks
    Print all sequences of given length | GeeksforGeeks Given two integers k and n, write a function that prints all the sequences of length k...
  • LeetCode 988 - Smallest String Starting From Leaf
    https://leetcode.com/problems/smallest-string-starting-from-leaf/ Given the  root  of a binary tree, each node has a value from  0  to  2...
  • LeetCode 860 - Lemonade Change
    https://leetcode.com/problems/lemonade-change/description/ At a lemonade stand, each lemonade costs  $5 .  Customers are standing in a ...
  • Uber Interview
    优步面经 Email domain address typo, need to figure out and return correct domain name. e.g. yhaoo–> yahoo, giaml –> gmail, hmailot–> ...