Class: DataStructuresRMolinari::IndexOfMaxValSegmentTree

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

Instance Method Summary collapse

Constructor Details

#initialize(data) ⇒ IndexOfMaxValSegmentTree

Returns a new instance of IndexOfMaxValSegmentTree.

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.



63
64
65
66
67
68
69
70
 
# File 'lib/data_structures_rmolinari.rb', line 63

def initialize(data)
  @structure = SegmentTreeTemplate.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



78
79
80
 
# File 'lib/data_structures_rmolinari.rb', line 78

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