Class: DataStructuresRMolinari::MaxValSegmentTree

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

Overview

A segment tree that for an array A(0…n) answers questions of the form “what is the maximum value in the subinterval A(i..j)?” in O(log n) time.

Instance Method Summary collapse

Constructor Details

#initialize(data) ⇒ MaxValSegmentTree

Returns a new instance of MaxValSegmentTree.

Parameters:

  • data —

    an object that contains values at integer indices based at 0, via data[i].

    • This will usually be an Array, but it could also be a hash or a proc.



36
37
38
39
40
41
42
43
 
# File 'lib/data_structures_rmolinari.rb', line 36

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

Instance Method Details

#max_on(i, j) ⇒ Object

The maximum value in A(i..j).

The arguments must be integers in 0…(A.size)

Returns:

  • the largest value in A(i..j) or -Infinity if i > j.



49
50
51
 
# File 'lib/data_structures_rmolinari.rb', line 49

def max_on(i, j)
  @structure.query_on(i, j)
end