# Lars Arge

## An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

### DOI

• Pankaj K. Agarwal, Department of Computer Science, Duke University
• ,
• Lars Arge
• Haim Kaplan, Department of Computer science, Tel-Aviv university, Israel
• Eyal Molad, Department of Computer science, Tel-Aviv university, Israel
• Robert E. Tarjan, Department of Computer Science, Princeton University, United States
• Ke Yi, Department of Computer Science and Engineering, HKUST, Hong Kong
Let S be a set of n intervals in $\mathbb{R}$, and let $(\mathbf{S}, +)$ be any commutative semigroup. We assign a weight $\omega(s) \in \mathbf{S}$ to each interval in S. For a point $x \in \mathbb{R}$, let $S(x) \subseteq S$ be the set of intervals that contain x. Given a point $q \in \mathbb{R}$, the stabbing-semigroup query asks for computing $\sum_{s \in S(q)} \omega(s)$. We propose a linear-size dynamic data structure, under the pointer-machine model, that answers queries in worst-case $O(\log n)$ time and supports both insertions and deletions of intervals in amortized $O(\log n)$ time. It is the first data structure that attains the optimal $O(\log n)$ bound for all three operations. Furthermore, our structure can easily be adapted to external memory, where we obtain a linear-size structure that answers queries and supports updates in $O(\log_B n)$ I/Os, where B is the disk block size. For the restricted case of a nested family of intervals (either every pair of intervals is disjoint or one contains the other), we present a simpler solution based on dynamic trees

Original language English S I A M Journal on Computing 41 1 104–127 24 0097-5397 https://doi.org/10.1137/10078791X Published - 2012

### Research areas

• dynamic data structures, stabbing queries, semigroup queries

Citationformats

ID: 52283315