Module: DataStructuresRMolinari
- Defined in:
- lib/data_structures_rmolinari.rb,
lib/data_structures_rmolinari.rb,
lib/data_structures_rmolinari/segment_tree.rb
Overview
Segment Tree: various concrete implementations
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.
Here we provide several concrete segment tree implementations built on top of the template (generic) versions. Each instance is backed either by the pure Ruby SegmentTreeTemplate or its C-based sibling CSegmentTreeTemplate
Defined Under Namespace
Modules: Algorithms, SegmentTree Classes: CDisjointUnion, CSegmentTreeTemplate, DisjointUnion, Heap, MaxPrioritySearchTree, MinPrioritySearchTree