Class: DataStructuresRMolinari::MaxValSegmentTree

Inherits:
Object
  • Object
show all
Extended by:
Forwardable
Defined in:
lib/data_structures_rmolinari.rb

Overview

Takes an array A and tells us what the maximum value is on a subinterval i..j in O(log n) time.

TODO:

  • allow min val too

    • add a flag to the initializer

    • call it ExtremalValSegment tree or something similar

Instance Method Summary collapse

Constructor Details

#initialize(data) ⇒ MaxValSegmentTree

Returns a new instance of MaxValSegmentTree.



33
34
35
36
37
38
39
40
 
# File 'lib/data_structures_rmolinari.rb', line 33

def initialize(data)
  @structure = GenericSegmentTree.new(
    combine:               ->(a, b) { [a, b].max },
    single_cell_array_val: ->(i) { data[i] },
    size:                  data.size,
    identity:              -Float::INFINITY
  )
end