Han Zhu's Study Notes

Given a 2D matrix   matrix , find the sum of the elements inside the rectangle defined by its upper left corner ( row 1,   col 1) and lower right corner ( row 2,   col 2). 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: The matrix is only modifiable by the  update  function. You may assume the number of calls to  update  and  sumRegion  function is distributed evenly. You may assume that  row 1 ≤  row 2 and  col 1 ≤  col 2. Thought process: Binary indexed tree. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 3...

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: The array is only modifiable by the  update  function. You may assume the number of calls to  update  and  sumRange  function is distributed evenly. Thought process: If we continue to use prefix sum, update() will take O(n). To reduce the time complexity, use binary indexed tree or segment tree instead. Solution 1 (Binary indexed tree): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class NumArray { private int [] nums ; private int [] tree ; public NumArray ( int [...

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are  given the locations and height of all the buildings  as shown on a cityscape photo (Figure A), write a program to  output the skyline  formed by these buildings collectively (Figure B).   The geometric information of each building is represented by a triplet of integers  [Li, Ri, Hi] , where  Li  and  Ri  are the x coordinates of the left and right edge of the ith building, respectively, and  Hi  is its height. It is guaranteed that  0 ? Li, Ri ? INT_MAX ,  0 < Hi ? INT_MAX , and  Ri - Li > 0 . You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0. For instance, the dimensions of all buildings in Figure A are recorded as:  [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] . The output is a list ...