Class: DataStructuresRMolinari::SegmentTree::IndexOfMaxValSegmentTree

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 index of the maximal value in the subinterval A(i..j)?” in O(log n) time.

Instance Method Summary collapse

Constructor Details

#initialize(template_klass, data) ⇒ IndexOfMaxValSegmentTree

Returns a new instance of IndexOfMaxValSegmentTree.

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.



88
89
90
91
92
93
94
95
96
97
 
# File 'lib/data_structures_rmolinari/segment_tree.rb', line 88

def initialize(template_klass, data)
  data.must_be_a Enumerable

  @structure = template_klass.new(
    combine:               ->(p1, p2) { p1[1] >= p2[1] ? p1 : p2 },
    single_cell_array_val: ->(i) { [i, data[i]] },
    size:                  data.size,
    identity:              nil
  )
end

Instance Method Details

#index_of_max_val_on(i, j) ⇒ Integer?

The index of the maximum value in A(i..j)

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

Returns:

  • (Integer, nil) —

    the index of the largest value in A(i..j) or nil if i > j.

    • If there is more than one entry with that value, return one the indices. There is no guarantee as to which one.

    • Return nil if i > j



105
106
107
 
# File 'lib/data_structures_rmolinari/segment_tree.rb', line 105

def index_of_max_val_on(i, j)
  @structure.query_on(i, j)&.first # discard the value part of the pair, which is a bookkeeping
end