Class: DataStructuresRMolinari::SegmentTree::SumSegmentTree

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

Instance Method Summary collapse

Constructor Details

#initialize(template_klass, data) ⇒ SumSegmentTree

Returns a new instance of SumSegmentTree.

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.



122
123
124
125
126
127
128
129
130
131
 
# File 'lib/data_structures_rmolinari/segment_tree.rb', line 122

def initialize(template_klass, data)
  data.must_be_a Enumerable

  @structure = template_klass.new(
    combine:               ->(a, b) { a + b },
    single_cell_array_val: ->(i) { data[i] },
    size:                  data.size,
    identity:              0
  )
end

Instance Method Details

#sum_on(i, j) ⇒ Object

The sum of the values in A(i..j)

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

Returns:

  • the sum of the values in A(i..j) or 0 if i > j.



137
138
139
 
# File 'lib/data_structures_rmolinari/segment_tree.rb', line 137

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