Class: DataStructuresRMolinari::SegmentTree::MaxValSegmentTree

Inherits:
Object
  • Object
show all
Extended by:
Forwardable
Defined in:
lib/data_structures_rmolinari/segment_tree.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(template_klass, data) ⇒ MaxValSegmentTree

Returns a new instance of MaxValSegmentTree.

Parameters:

  • template_klass —

    the “template” class that provides the generic implementation of the Segment Tree functionality.

  • 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.



59
60
61
62
63
64
65
66
67
68
 
# File 'lib/data_structures_rmolinari/segment_tree.rb', line 59

def initialize(template_klass, data)
  data.must_be_a Enumerable

  @structure = template_klass.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.



74
75
76
 
# File 'lib/data_structures_rmolinari/segment_tree.rb', line 74

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