Class: DataStructuresRMolinari::SegmentTree::SegmentTreeTemplate

Inherits:
Object
  • Object
show all
Includes:
Shared, Shared::BinaryTreeArithmetic
Defined in:
lib/data_structures_rmolinari/segment_tree_template.rb

Overview

A generic implementation of Segment Tree, which can be used for various interval-related purposes, like efficiently finding the sum (or min or max) on a arbitrary subarray of a given array.

There is an excellent description of the data structure at cp-algorithms.com/data_structures/segment_tree.html. The Wikipedia article (en.wikipedia.org/wiki/Segment_tree) appears to describe a different data structure which is sometimes called an “interval tree.”

For more details (and some close-to-metal analysis of run time, especially for large datasets) see en.algorithmica.org/hpc/data-structures/segment-trees/. In particular, this shows how to do a bottom-up implementation, which is faster, at least for large datasets and cache-relevant compiled code. These issues don’t really apply to code written in Ruby.

This is a generic implementation, intended to allow easy configuration for concrete instances. See the parameters to the initializer and the definitions of concrete realisations like MaxValSegmentTree.

We do O(n) work to build the internal data structure at initialization. Then we answer queries in O(log n) time.

Constant Summary

Constants included from Shared

Shared::INFINITY

Instance Method Summary collapse

Methods included from Shared

#contains_duplicates?

Constructor Details

#initialize(combine:, single_cell_array_val:, size:, identity:) ⇒ SegmentTreeTemplate

Construct a concrete instance of a Segment Tree. See details at the links above for the underlying concepts here.

Parameters:

  • combine —

    a lambda that takes two values and munges them into a combined value.

    • For example, if we are calculating sums over subintervals, combine.call(a, b) = a + b, while if we are doing maxima we will return max(a, b).

    • Things get more complicated when we are calculating, say, the index of the maximal value in a subinterval. Now it is not enough simply to store that index at each tree node, because to combine the indices from two child nodes we need to know both the index of the maximal element in each child node’s interval, but also the maximal values themselves, so we know which one “wins” for the parent node. This affects the sort of work we need to do when combining and the value provided by the single_cell_array_val lambda.

  • single_cell_array_val —

    a lambda that takes an index i and returns the value we need to store in the #build operation for the subinterval i..i.

    • This will often simply be the value data, but in some cases it will be something else. For example, when we are calculating the index of the maximal value on each subinterval we need [i, data] here.

    • If update_at is called later, this lambda must close over the underlying data in a way that captures the updated value.

  • size —

    the size of the underlying data array, used in certain internal arithmetic.

  • identity —

    the value to return when we are querying on an empty interval

    • for sums, this will be zero; for maxima, this will be -Infinity, etc



40
41
42
43
44
45
46
47
48
 
# File 'lib/data_structures_rmolinari/segment_tree_template.rb', line 40

def initialize(combine:, single_cell_array_val:, size:, identity:)
  @combine = combine
  @single_cell_array_val = single_cell_array_val
  @size = size
  @identity = identity

  @tree = []
  build(root, 0, @size - 1)
end

Instance Method Details

#query_on(left, right) ⇒ Object

The desired value (max, sum, etc.) on the subinterval left..right.

It must be that left..right is contained in 0…size.

The type of the return value depends on the concrete instance of the segment tree. We return the identity element provided at construction time if the interval is empty.

Parameters:

  • left —

    the left end of the subinterval.

  • right —

    the right end (inclusive) of the subinterval.

Raises:



59
60
61
62
63
64
65
 
# File 'lib/data_structures_rmolinari/segment_tree_template.rb', line 59

def query_on(left, right)
  raise DataError, "Bad query interval #{left}..#{right} (size = #{@size})" unless (0...@size).cover?(left..right)

  return @identity if left > right # empty interval

  determine_val(root, left, right, 0, @size - 1)
end

#update_at(idx) ⇒ Object

Reflect the fact that the underlying array has been updated at the given idx

Note that we don’t need the updated value itself. We get that by calling the lambda single_cell_array_val supplied at construction.

Parameters:

  • idx —

    an index in the underlying data array.



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

def update_at(idx)

  update_val_at(idx, root, 0, @size - 1)
end