2026-08-17T16:09:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23246 2025-10-27T10:36:12Z ddc:004 open_access

A Simple Integer Successor-Delete Data Structure Brodal, Gerth Stølting Successor queries deletions interval union-find union-find We consider a simple decremental data structure for maintaining a set of integers, that supports initializing the set to {1,2,…,n} followed by d deletions and s successor queries in arbitrary order in total 𝒪(n+d+s⋅(1+log_{max(2,s/n)} min(s,n))) time. The data structure consists of a single array of n integers. A straightforward modification allows the data structure to also support p predecessor and r range queries, with a total output k, in total 𝒪(n+d+k+q ⋅ (1+log_{max(2,q/n)} min(q,n))) time, where q = s+p+r. The data structure is essentially a special case of the classic union-find data structure with path compression but with unweighted linking (i.e., without linking by rank or size), that is known to achieve logarithmic amortized time bounds (Tarjan and van Leeuwen, 1984). In this paper we study the efficiency of this simple data structure, and compare it to other, theoretically superior, data structures. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gerth Stølting Brodal 2025 Is Part Of LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2025.8 urn:nbn:de:0030-drops-232461 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.8 eng https://creativecommons.org/licenses/by/4.0/legalcode