[HN Gopher] Succinct Dynamic Data Structures (2001) [pdf] ___________________________________________________________________ Succinct Dynamic Data Structures (2001) [pdf] Author : tjalfi Score : 6 points Date : 2021-09-14 01:12 UTC (1 days ago) (HTM) web link (www.imsc.res.in) (TXT) w3m dump (www.imsc.res.in) | tjalfi wrote: | Here's the abstract. | | We develop succinct data structures to represent (i) a sequence | of values to support partial sum and select queries and update | (changing values) and (ii) a dynamic array consisting of a | sequence of elements which supports insertion, deletion and | access of an element at any given index. | | For the partial sums problem on n non-negative integers of k bits | each, we support update operations in O(b) time and sum in O(logb | n) time, for any parameter b, lgn/ lg lg n <= b <= nE for any | fixed positive E < 1. The space used is kn+o(kn) bits and the | time bounds are optimal. When b = lgn/ lg lg n or k = 1 (i.e., | when we are dealing with a bit-vector), we can also support the | select operation in the same time as the sum operation, but the | update time becomes amortised. | | For the dynamic array problem, we give two structures both using | o(n) bits of extra space where n is the number of elements in the | array: one supports lookup in constant worst case time and | updates in O(nE) worst case time, and the other supports all | operations in O(lg n/lg lg n) amortized time. The time bound of | both these structures are optimal. ___________________________________________________________________ (page generated 2021-09-15 23:01 UTC)