{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:09Z","timestamp":1759639089020},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319087825"},{"type":"electronic","value":"9783319087832"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08783-2_11","type":"book-chapter","created":{"date-parts":[[2014,7,5]],"date-time":"2014-07-05T10:04:30Z","timestamp":1404554670000},"page":"116-128","source":"Crossref","is-referenced-by-count":0,"title":["The Range 1 Query (R1Q) Problem"],"prefix":"10.1007","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rezaul A.","family":"Chowdhury","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pramod","family":"Ganapathi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel","family":"McCauley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuan","family":"Tang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/conm\/223\/03131","volume":"223","author":"P.K. Agarwal","year":"1999","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. Contemporary Mathematics\u00a0223, 1\u201356 (1999)","journal-title":"Contemporary Mathematics"},{"key":"11_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/978-3-540-73437-6_29","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"2007","unstructured":"Amir, A., Fischer, J., Lewenstein, M.: Two-dimensional range minimum queries. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 286\u2013294. Springer, Heidelberg (2007)"},{"key":"11_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The lca problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"issue":"2","key":"11_CR4","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. Journal of Algorithms\u00a057(2), 75\u201394 (2005)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"11_CR5","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0222017","volume":"22","author":"O. Berkman","year":"1993","unstructured":"Berkman, O., Vishkin, U.: Recursive star-tree parallel data structure. SIAM Journal on Computing\u00a022(2), 221\u2013242 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"11_CR6","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1007\/s00453-011-9499-0","volume":"63","author":"G.S. Brodal","year":"2012","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: On space efficient two dimensional range minimum data structures. Algorithmica\u00a063(4), 815\u2013830 (2012)","journal-title":"Algorithmica"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Rosenberg, B.: Computing partial sums in multidimensional arrays. In: SoCG, pp. 131\u2013139. ACM (1989)","DOI":"10.1145\/73833.73848"},{"issue":"1","key":"11_CR8","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G. Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: The count-min sketch and its applications. Journal of Algorithms\u00a055(1), 58\u201375 (2005)","journal-title":"Journal of Algorithms"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"De Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational geometry. Springer (2008)","DOI":"10.1007\/978-3-540-77974-2"},{"key":"11_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1007\/978-3-642-12200-2_16","volume-title":"LATIN 2010: Theoretical Informatics","author":"J. Fischer","year":"2010","unstructured":"Fischer, J.: Optimal succinctness for range minimum queries. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 158\u2013169. Springer, Heidelberg (2010)"},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/978-3-540-74450-4_41","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"J. Fischer","year":"2007","unstructured":"Fischer, J., Heun, V.: A new succinct representation of rmq-information and improvements in the enhanced suffix array. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol.\u00a04614, pp. 459\u2013470. Springer, Heidelberg (2007)"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Fischer, J., Heun, V., Stiihler, H.: Practical entropy-bounded schemes for o(1)-range minimum queries. In: Data Compression Conference, pp. 272\u2013281. IEEE (2008)","DOI":"10.1109\/DCC.2008.45"},{"issue":"3","key":"11_CR13","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.tcs.2007.07.041","volume":"387","author":"A. Golynski","year":"2007","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. TCS\u00a0387(3), 348\u2013359 (2007)","journal-title":"TCS"},{"key":"11_CR14","unstructured":"Gonz\u00e1lez, R., Grabowski, S., M\u00e4kinen, V., Navarro, G.: Practical implementation of rank and select queries. In: Poster Proc. WEA, pp. 27\u201338 (2005)"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Navarro, G., Nekrich, Y., Russo, L.: Space-efficient data-analysis queries on grids. TCS (2012)","DOI":"10.1016\/j.tcs.2012.11.031"},{"issue":"2","key":"11_CR16","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0196-6774(88)90041-7","volume":"9","author":"M.H. Overmars","year":"1988","unstructured":"Overmars, M.H.: Efficient data structures for range searching on a grid. Journal of Algorithms\u00a09(2), 254\u2013275 (1988)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"11_CR17","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","volume":"41","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theory of Computing Systems\u00a041(4), 589\u2013607 (2007)","journal-title":"Theory of Computing Systems"},{"issue":"1","key":"11_CR18","first-page":"12","volume":"5","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct data structures for flexible text retrieval systems. JDA\u00a05(1), 12\u201322 (2007)","journal-title":"JDA"},{"issue":"4","key":"11_CR19","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1137\/090765092","volume":"40","author":"M. Sharir","year":"2011","unstructured":"Sharir, M., Shaul, H.: Semialgebraic range reporting and emptiness searching with applications. SIAM Journal on Computing\u00a040(4), 1045\u20131074 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Tang, Y., Chowdhury, R., Kuszmaul, B.C., Luk, C.K., Leiserson, C.E.: The Pochoir stencil compiler. In: SPAA, pp. 117\u2013128. ACM (2011)","DOI":"10.1145\/1989493.1989508"},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Space-time tradeoff for answering range queries. In: STOC, pp. 128\u2013136. ACM (1982)","DOI":"10.1145\/800070.802185"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Yuan, H., Atallah, M.J.: Data structures for range minimum queries in multidimensional arrays. In: SODA, pp. 150\u2013160 (2010)","DOI":"10.1137\/1.9781611973075.14"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08783-2_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T03:00:40Z","timestamp":1558926040000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08783-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319087825","9783319087832"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08783-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}