A Simple and Space Efficient Segment Tree Implementation

2018/07/14 by Lei Wang, Xiaodong Wang, Wang, Lei +1
Computer Science · #Algorithms and Data Compression #Data Management and Algorithms #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1807.05356

arxiv created 2018/07/14 · openalex publication_date 2018/07/14 · arxiv updated 2018/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The segment tree is an extremely versatile data structure. In this paper, a new heap based implementation of segment trees is proposed. In such an implementation of segment tree, the structural information associated with the tree nodes can be removed completely. Some primary computational geometry problems such as stabbing counting queries, measure of union of intervals, and maximum clique size of Intervals are used to demonstrate the efficiency of the new heap based segment tree implementation. Each interval in a set S=\I₁ ,I₂ ,⋯,I_n\ of n intervals can be insert into or delete from the heap based segment tree in O(log n) time. All the primary computational geometry problems can be solved efficiently.

Related

• A Deterministic Partition Tree and Applications
• New Algorithms for Position Heaps
• The Unified Segment Tree and its Application to the Rectangle Intersection Problem
• Succinct Data Structures for Segments
• Southwest Tree: A Low-Memory Data Structure for Partial Accumulations by Non-Commutative Invertible Operations