304_range_sum_2d.rb

class NumMatrix 
  # (0, 0) is the top left
  def initialize(matrix)
    @corner_areas = matrix
    @corner_areas.each.with_index do |row, y|
      row.each.with_index do |value, x|
        upper_sum = positive_dig(@corner_areas, y - 1, x)
        left_sum = positive_dig(@corner_areas, y, x - 1)

        @corner_areas[y][x] = value + upper_sum + left_sum - positive_dig(@corner_areas, y - 1, x - 1)
      end
    end
  end

  # 
  #          c1        c2
  #    ┌─────┼─────────┼──┐
  #    │  A  │    B    │  │
  # r1 ┼─────┼─────────┤  │
  #    │  C  │    D    │  │
  # r2 ┼─────┴─────────┘  │
  #    └──────────────────┘
  # upper left corner (row1, col1) and lower right corner (row2, col2).
  # 
  def sum_region(row1, col1, row2, col2)
    # Need to subtract - 1 from indices, otherwise it will delete the corner of the region
    # we want to sum!
    inner_area = positive_dig(@corner_areas, row1 - 1, col1 - 1)
    full_area = positive_dig(@corner_areas, row2, col2)

    left_area = positive_dig(@corner_areas, row2, col1 - 1)
    upper_area = positive_dig(@corner_areas, row1 - 1, col2)

    full_area - left_area - upper_area + inner_area
  end

  def positive_dig(arr, *indices)
    # We need to filter these otherwise Ruby will negative index from end of array
    if indices.any?(&:negative?)
      0
    else
      arr.dig(*indices)
    end
  end
end