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.



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.

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.

Raises:



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

def update_at(idx)
  raise DataError, "Bad update index #{idx} (size = #{@size})" unless (0...@size).cover?(idx)

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