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 



93
94
95
96
97
98
99
100
101
102
 
# File 'lib/data_structures_rmolinari/segment_tree.rb', line 93

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)



110
111
112
 
# File 'lib/data_structures_rmolinari/segment_tree.rb', line 110

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