{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:04:40Z","timestamp":1757617480036,"version":"3.44.0"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031826696"},{"type":"electronic","value":"9783031826702"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-82670-2_10","type":"book-chapter","created":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T23:25:29Z","timestamp":1738970729000},"page":"122-135","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Dynamic Range Minimum Queries on\u00a0the\u00a0Ultra-wide Word RAM"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1120-5154","authenticated-orcid":false,"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8322-4952","authenticated-orcid":false,"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-8507-4820","authenticated-orcid":false,"given":"M\u00e1ximo","family":"P\u00e9rez L\u00f3pez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1525-0104","authenticated-orcid":false,"given":"Tord","family":"Stordalen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/s00224-004-1155-5","volume":"37","author":"S Alstrup","year":"2004","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: a survey and a new algorithm for a distributed environment. Theory Comput. Syst. 37, 441\u2013456 (2004)","journal-title":"Theory Comput. Syst."},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pp. 534\u2013543 (1998)","DOI":"10.1109\/SFCS.1998.743504"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of the 4th Latin American Symposium on Theoretical Informatics, pp. 88\u201394 (2000)","DOI":"10.1007\/10719839_9"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Berkman, O., Breslauer, D., Galil, Z., Schieber, B., Vishkin, U.: Highly parallelizable problems. In: Proceedings of 21st STOC, pp. 309\u2013319 (1989)","DOI":"10.1145\/73007.73036"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.tcs.2022.01.002","volume":"905","author":"P Bille","year":"2022","unstructured":"Bille, P., G\u00f8rtz, I.L., Skjoldjensen, F.R.: Partial sums on the ultra-wide word RAM. Theor. Comput. Sci. 905, 99\u2013105 (2022)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"10_CR6","doi-asserted-by":"publisher","first-page":"1578","DOI":"10.1007\/s00453-023-01193-1","volume":"86","author":"P Bille","year":"2024","unstructured":"Bille, P., G\u00f8rtz, I.L., Stordalen, T.: Predecessor on the ultra-wide word RAM. Algorithmica 86(5), 1578\u20131599 (2024)","journal-title":"Algorithmica"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Bille, P., G\u00f8rtz, I.L., Stordalen, T., P\u00e9rez-L\u00f3pez. M.: Dynamic range minimum queries on the ultra-wide word RAM. arXiv:2411.16281 (2024)","DOI":"10.2139\/ssrn.5296998"},{"key":"10_CR8","unstructured":"Blelloch, G.E.: Prefix sums and their applications. In: Synthesis of Parallel Algorithms (1990)"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Chaudhuri, S., Radhakrishnan, J.: The randomized complexity of maintaining the minimum. In: Proceedings of 5th SWAT, pp. 4\u201315 (1996)","DOI":"10.1007\/3-540-61422-2_116"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.tcs.2016.02.016","volume":"638","author":"GS Brodal","year":"2016","unstructured":"Brodal, G.S., Davoodi, P., Lewenstein, M., Raman, R., Satti, S.R.: Two dimensional range minimum queries and fibonacci lattices. Theor. Comput. Sci. 638, 33\u201343 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Davoodi, P., Srinivasa\u00a0Rao, S.: Path minima queries in dynamic weighted trees. In: Proceedings of 12th WADS, pp. 290\u2013301 (2011)","DOI":"10.1007\/978-3-642-22300-6_25"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Rosenberg, B.: Computing partial sums in multidimensional arrays. In: Proceedings of 5th SOCG, pp. 131\u2013139 (1989)","DOI":"10.1145\/73833.73848"},{"issue":"5","key":"10_CR13","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1147\/rd.515.0559","volume":"51","author":"T Chen","year":"2007","unstructured":"Chen, T., Raghavan, R., Dale, J.N., Iwata, E.: Cell broadband engine architecture and its first implementation\u2013a performance view. IBM J. Res. Dev. 51(5), 559\u2013572 (2007)","journal-title":"IBM J. Res. Dev."},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1007\/s00453-012-9683-x","volume":"68","author":"ED Demaine","year":"2014","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On cartesian trees and range minimum queries. Algorithmica 68, 610\u2013625 (2014)","journal-title":"Algorithmica"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Farzan, A., L\u00f3pez-Ortiz, A., Nicholson, P.K., Salinger, A.: Algorithms in the ultra-wide word model. In: Proceedings of 12th TAMC, pp. 335\u2013346 (2015)","DOI":"10.1007\/978-3-319-17142-5_29"},{"issue":"2","key":"10_CR16","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proceedings of 16th STOC, pp. 135\u2013143 (1984)","DOI":"10.1145\/800057.808675"},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"Hagerup, T.: Sorting and searching on the word ram. In: Proceedings of 15th STACS, pp. 366\u2013398 (1998)","DOI":"10.1007\/BFb0028575"},{"issue":"2","key":"10_CR19","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10_CR20","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"RE Ladner","year":"1980","unstructured":"Ladner, R.E., Fischer, M.J.: Parallel prefix computation. J. ACM 27(4), 831\u2013838 (1980)","journal-title":"J. ACM"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Larsen, K.G., Pagh, R.: I\/o-efficient data structures for colored range and prefix reporting. In: Proceedings of 23rd SODA, pp. 583\u2013592 (2012)","DOI":"10.1137\/1.9781611973099.49"},{"issue":"2","key":"10_CR22","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1109\/MM.2008.31","volume":"28","author":"E Lindholm","year":"2008","unstructured":"Lindholm, E., Nickolls, J., Oberman, S., Montrym, J.: NVIDIA tesla: a unified graphics and computing architecture. IEEE Micro 28(2), 39\u201355 (2008)","journal-title":"IEEE Micro"},{"issue":"4","key":"10_CR23","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M P\u01cetra\u015fcu","year":"2006","unstructured":"P\u01cetra\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":"10_CR24","unstructured":"Reinders, J.: AVX-512 instructions. Intel Corporation (2013)"},{"issue":"3","key":"10_CR25","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D Sleator","year":"1983","unstructured":"Sleator, D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10_CR26","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1109\/MM.2017.35","volume":"37","author":"N Stephens","year":"2017","unstructured":"Stephens, N., et al.: The ARM scalable vector extension. IEEE Micro 37(2), 26\u201339 (2017)","journal-title":"IEEE Micro"},{"issue":"2","key":"10_CR27","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0214022","volume":"14","author":"AC Yao","year":"1985","unstructured":"Yao, A.C.: On the complexity of maintaining partial sums. SIAM J. Comput. 14(2), 277\u2013288 (1985)","journal-title":"SIAM J. Comput."},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"Yuan, H., Atallah, M.J.: Data structures for range minimum queries in multidimensional arrays. In: Proceedings of 21st SODA, pp. 150\u2013160 (2010)","DOI":"10.1137\/1.9781611973075.14"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2025: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-82670-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T04:41:05Z","timestamp":1757133665000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-82670-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031826696","9783031826702"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-82670-2_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"7 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bratislava","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sofsem.sk","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}