{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T00:31:24Z","timestamp":1759365084195,"version":"build-2065373602"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T00:00:00Z","timestamp":1753056000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T00:00:00Z","timestamp":1753056000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["FB0001"],"award-info":[{"award-number":["FB0001"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s00224-025-10229-8","type":"journal-article","created":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T13:31:25Z","timestamp":1753104685000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["(Worst-case) Optimal Adaptive Dynamic Bitvectors"],"prefix":"10.1007","volume":"69","author":[{"given":"Gonzalo","family":"Navarro","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,21]]},"reference":[{"key":"10229_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284","volume-title":"Compact Data Structures - A Practical Approach","author":"G Navarro","year":"2016","unstructured":"Navarro, G.: Compact Data Structures - A Practical Approach. Cambridge University Press, Cambridge, UK (2016)"},{"key":"10229_CR2","unstructured":"Clark, D.R.: Compact PAT trees. PhD thesis, University of Waterloo, Canada (1996)"},{"key":"10229_CR3","doi-asserted-by":"crossref","unstructured":"Munro, J.I.: Tables. In: Proc. 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 37\u201342 (1996)","DOI":"10.1007\/3-540-62034-6_35"},{"key":"10229_CR4","doi-asserted-by":"crossref","unstructured":"Fredman, M., Saks, M.: The cell probe complexity of dynamic data structures. In: Proc. 21st Annual ACM Symposium on Theory of Computing (STOC), pp. 345\u2013354 (1989)","DOI":"10.1145\/73007.73040"},{"issue":"3","key":"10229_CR5","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/2601073","volume":"10","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Sadakane, K.: Fully-functional static and dynamic succinct trees. ACM Trans. Algorithms. 10(3), 16 (2014)","journal-title":"ACM Trans. Algorithms."},{"key":"10229_CR6","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct dynamic data structures. In: Proc. 3rd International Symposium on Algorithms and Data Structures (WADS), pp. 426\u2013437 (2001)","DOI":"10.1007\/3-540-44634-6_39"},{"key":"10229_CR7","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Sadakane, K., Sung, W.-K.: Succinct data structures for searchable partial sums. In: Proc. 14th International Symposium on Algorithms and Computation (ISAAC), pp. 505\u2013516 (2003)","DOI":"10.1007\/978-3-540-24587-2_52"},{"issue":"2","key":"10229_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/1240233.1240244","volume":"3","author":"H-L Chan","year":"2007","unstructured":"Chan, H.-L., Hon, W.-K., Lam, T.-W., Sadakane, K.: Compressed indexes for dynamic text collections. ACM Trans. Algorithms. 3(2), 21 (2007)","journal-title":"ACM Trans. Algorithms."},{"key":"10229_CR9","doi-asserted-by":"crossref","unstructured":"Dietz, P.: Optimal algorithms for list indexing and subset rank. In: Proc. Workshop on Algorithms and Data Structures (WADS), pp. 39\u201346 (1989)","DOI":"10.1007\/3-540-51542-9_5"},{"key":"10229_CR10","unstructured":"Arge, L., Vitter, J.S.: Optimal dynamic interval management in external memory (extended abstract). In: Proc. 37th Annual Symposium on Foundations of Computer Science (FOCS), pp. 560\u2013569 (1996)"},{"key":"10229_CR11","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Adaptive dynamic bitvectors. In: Proc. 31st International Symposium on String Processing and Information Retrieval (SPIRE), pp. 204\u2013217 (2024)","DOI":"10.1007\/978-3-031-72200-4_16"},{"key":"10229_CR12","doi-asserted-by":"crossref","unstructured":"Chan, H.-L., Hon, W.-K., Lam, T.-W.: Compressed index for a dynamic collection of texts. In: Proc. 15th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 445\u2013456 (2004)","DOI":"10.1007\/978-3-540-27801-6_34"},{"issue":"3","key":"10229_CR13","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/1367064.1367072","volume":"4","author":"V M\u00e4kinen","year":"2008","unstructured":"M\u00e4kinen, V., Navarro, G.: Dynamic entropy-compressed sequences and full-text indexes. ACM Trans. Algorithms. 4(3), 32 (2008)","journal-title":"ACM Trans. Algorithms."},{"key":"10229_CR14","unstructured":"Blandford, D., Blelloch, G.: Compact representations of ordered sets. In: Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 11\u201319 (2004)"},{"issue":"1","key":"10229_CR15","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0022-0000(86)90043-7","volume":"33","author":"JI Munro","year":"1986","unstructured":"Munro, J.I.: An implicit data structure supporting insertion, deletion, and search in time 0(log n). J. Comput. Syst. Sci. 33(1), 66\u201374 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"10229_CR16","doi-asserted-by":"crossref","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. In: Proc. 33rd International Colloquium on Automata, Languages and Programming (ICALP), pp. 370\u2013381 (2006)","DOI":"10.1007\/11786986_33"},{"issue":"4","key":"10229_CR17","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R Raman","year":"2007","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms. 3(4), 43 (2007)","journal-title":"ACM Trans. Algorithms."},{"key":"10229_CR18","unstructured":"Miltersen, P.B.: Cell probe complexity\u2013 a survey. Downloaded from https:\/\/www.cs.umd.edu\/~gasarch\/BLOGPAPERS\/cellprobesurvey.pdf (2000)"},{"key":"10229_CR19","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Germany (2006)"},{"key":"10229_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-959-0","volume-title":"Variable-Length Codes for Data Compression","author":"D Solomon","year":"2007","unstructured":"Solomon, D.: Variable-Length Codes for Data Compression. Springer, Germany (2007)"},{"key":"10229_CR21","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. J. ACM. 21, 246\u2013260 (1974)","journal-title":"J. ACM."},{"key":"10229_CR22","unstructured":"Fano, R.: On the number of bits required to implement an associative memory. Memo 61, Computer Structures Group, Project MAC, Massachusetts (1971)"},{"key":"10229_CR23","doi-asserted-by":"crossref","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. In: Proc. 9th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 60\u201370 (2007)","DOI":"10.1137\/1.9781611972870.6"},{"issue":"3","key":"10229_CR24","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.tcs.2007.07.042","volume":"387","author":"A Gupta","year":"2007","unstructured":"Gupta, A., Hon, W.-K., Shah, R., Vitter, J.S.: Compressed data structures: Dictionaries and data-aware measures. Theor. Comput. Sci. 387(3), 313\u2013331 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10229_CR25","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M P\u0103tra\u015fcu","year":"2006","unstructured":"P\u0103tra\u015fcu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35(4), 932\u2013963 (2006)","journal-title":"SIAM J. Comput."},{"key":"10229_CR26","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 841\u2013850 (2003)"},{"key":"10229_CR27","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.is.2014.06.002","volume":"47","author":"F Claude","year":"2015","unstructured":"Claude, F., Navarro, G., Ord\u00f3\u00f1ez, A.: The wavelet matrix: An efficient wavelet tree for large alphabets. Inf. Syst. 47, 15\u201332 (2015)","journal-title":"Inf. Syst."},{"key":"10229_CR28","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Nekrich, Y.: Compressed data structures for dynamic sequences. In: Proc. 23rd Annual European Symposium on Algorithms (ESA), pp. 891\u2013902 (2015)","DOI":"10.1007\/978-3-662-48350-3_74"},{"key":"10229_CR29","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2013.07.004","volume":"25","author":"G Navarro","year":"2014","unstructured":"Navarro, G.: Wavelet trees for all. J. Discr. Algorithms. 25, 2\u201320 (2014)","journal-title":"J. Discr. Algorithms."},{"key":"10229_CR30","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)"},{"issue":"4","key":"10229_CR31","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed texts. J. ACM. 52(4), 552\u2013581 (2005)","journal-title":"J. ACM."},{"key":"10229_CR32","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proc. 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"issue":"1","key":"10229_CR33","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/j.is.2013.08.003","volume":"39","author":"NR Brisaboa","year":"2014","unstructured":"Brisaboa, N.R., Ladra, S., Navarro, G.: Compact representation of Web graphs with extended functionality. Inf. Syst. 39(1), 152\u2013174 (2014)","journal-title":"Inf. Syst."},{"issue":"3","key":"10229_CR34","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"JI Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"key":"10229_CR35","doi-asserted-by":"crossref","unstructured":"Joannou, S., Raman, R.: Dynamizing succinct tree representations. In: Proc 11th International Symposium on Experimental Algorithms (SEA), pp. 224\u2013235 (2012)","DOI":"10.1007\/978-3-642-30850-5_20"},{"issue":"4","key":"10229_CR36","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D Benoit","year":"2005","unstructured":"Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica. 43(4), 275\u2013292 (2005)","journal-title":"Algorithmica."},{"key":"10229_CR37","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Practical adaptive dynamic bitvectors. Softw. Pract. Exper. (2025)","DOI":"10.1007\/s00224-025-10229-8"},{"issue":"3","key":"10229_CR38","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM. 32(3), 652\u2013686 (1985)","journal-title":"J. ACM."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10229-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10229-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10229-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T05:21:13Z","timestamp":1759296073000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10229-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,21]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10229"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10229-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2025,7,21]]},"assertion":[{"value":"23 June 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 July 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"The author consents to publish the paper.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}],"article-number":"30"}}