[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)