{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:25:38Z","timestamp":1760441138818},"reference-count":62,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,3,8]],"date-time":"2013-03-08T00:00:00Z","timestamp":1362700800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,11]]},"DOI":"10.1007\/s00224-013-9455-2","type":"journal-article","created":{"date-parts":[[2013,3,7]],"date-time":"2013-03-07T08:09:20Z","timestamp":1362643760000},"page":"719-741","source":"Crossref","is-referenced-by-count":16,"title":["Linear-Space Data Structures for Range Mode Query in Arrays"],"prefix":"10.1007","volume":"55","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[]},{"given":"Stephane","family":"Durocher","sequence":"additional","affiliation":[]},{"given":"Kasper Green","family":"Larsen","sequence":"additional","affiliation":[]},{"given":"Jason","family":"Morrison","sequence":"additional","affiliation":[]},{"given":"Bryan T.","family":"Wilkinson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,8]]},"reference":[{"key":"9455_CR1","first-page":"809","volume-title":"Handbook of Discrete and Computational Geometry","author":"P.K. Agarwal","year":"2004","unstructured":"Agarwal, P.K.: Range searching. In: Goodman, J., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 809\u2013837. CRC Press, New York (2004)","edition":"2"},{"key":"9455_CR2","unstructured":"Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Technical report 71\/87, Tel-Aviv University (1987)"},{"key":"9455_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/978-3-540-73437-6_29","volume-title":"Proceedings of the Symposium on Combinatorial Pattern Matching (CPM)","author":"A. Amir","year":"2007","unstructured":"Amir, A., Fischer, J., Lewenstein, M.: Two-dimensional range minimum queries. In: Proceedings of the Symposium on Combinatorial Pattern Matching (CPM). Lecture Notes in Computer Science, vol. 4580, pp. 286\u2013294. Springer, Berlin (2007)"},{"key":"9455_CR4","first-page":"745","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS)","author":"N. Bansal","year":"2009","unstructured":"Bansal, N., Williams, R.: Regularity lemmas and combinatorial algorithms. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 745\u2013754 (2009)"},{"key":"9455_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"Proceedings of the Latin American Theoretical Informatics Symposium (LATIN)","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of the Latin American Theoretical Informatics Symposium (LATIN). Lecture Notes in Computer Science, vol. 1776, pp. 88\u201394. Springer, Berlin (2000)"},{"key":"9455_CR6","first-page":"309","volume-title":"Proceedings of the ACM Symposium on the Theory of Computing (STOC)","author":"O. Berkman","year":"1989","unstructured":"Berkman, O., Breslauer, D., Galil, Z., Schieber, B., Vishkin, U.: Highly parallelizable problems. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC), pp. 309\u2013319 (1989)"},{"key":"9455_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/978-3-540-31856-9_31","volume-title":"Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"P. Bose","year":"2005","unstructured":"Bose, P., Kranakis, E., Morin, P., Tang, Y.: Approximate range mode and range median queries. In: Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 3404, pp. 377\u2013388. Springer, Berlin (2005)"},{"key":"9455_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"822","DOI":"10.1007\/978-3-642-10631-6_83","volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC)","author":"G.S. Brodal","year":"2009","unstructured":"Brodal, G.S., J\u00f8rgensen, A.G.: Data structures for range median queries. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 5878, pp. 822\u2013831. Springer, Berlin (2009)"},{"key":"9455_CR9","series-title":"Lecture Notes in Computer Science.","volume-title":"Proceedings of the European Symposium on Algorithms (ESA)","author":"G.S. Brodal","year":"2010","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: On space efficient two dimensional range minimum data structures. In: Proceedings of the European Symposium on Algorithms (ESA). Lecture Notes in Computer Science., vol. 6346\/6347. Springer, Berlin (2010)"},{"key":"9455_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/978-3-642-22300-6_25","volume-title":"Proceedings of the Workshop on Algorithms and Data Structures (WADS)","author":"G.S. Brodal","year":"2011","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: Path minima queries in dynamic weighted trees. In: Proceedings of the Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, vol. 6844, pp. 290\u2013301. Springer, Berlin (2011)"},{"issue":"24","key":"9455_CR11","doi-asserted-by":"crossref","first-page":"2588","DOI":"10.1016\/j.tcs.2010.05.003","volume":"412","author":"G.S. Brodal","year":"2011","unstructured":"Brodal, G.S., Gfeller, B., J\u00f8rgensen, A.G., Sanders, P.: Towards optimal range medians. Theor. Comput. Sci. 412(24), 2588\u20132601 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9455_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/978-3-642-33090-2_20","volume-title":"Proceedings of the European Symposium on Algorithms (ESA)","author":"G.S. Brodal","year":"2012","unstructured":"Brodal, G.S., Davoodi, P., Lewenstein, M., Raman, R., Rao, S.S.: Two dimensional range minimum queries and Fibonacci lattices. In: Proceedings of the European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 7501, pp. 217\u2013228. Springer, Berlin (2012)"},{"issue":"4","key":"9455_CR13","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1007\/s00454-012-9410-z","volume":"47","author":"T.M. Chan","year":"2012","unstructured":"Chan, T.M.: Optimal partition trees. Discrete Comput. Geom. 47(4), 661\u2013690 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"9455_CR14","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1137\/1.9781611973075.15","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"T.M. Chan","year":"2010","unstructured":"Chan, T.M., P\u0103tra\u015fcu, M.: Counting inversions, offline orthogonal range counting, and related problems. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 161\u2013173 (2010)"},{"key":"9455_CR15","series-title":"Leibniz International Proceedings in Informatics","first-page":"291","volume-title":"Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"T.M. Chan","year":"2012","unstructured":"Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. In: Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS). Leibniz International Proceedings in Informatics, vol. 14, pp. 291\u2013301 (2012)"},{"key":"9455_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/978-3-642-31155-0_26","volume-title":"Proceedings of the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)","author":"T.M. Chan","year":"2012","unstructured":"Chan, T.M., Durocher, S., Skala, M., Wilkinson, B.T.: Linear-space data structures for range minority query in arrays. In: Proceedings of the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT). Lecture Notes in Computer Science, vol. 7357, pp. 295\u2013306. Springer, Berlin (2012)"},{"issue":"2","key":"9455_CR17","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B. Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom. 9(2), 145\u2013158 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9455_CR18","first-page":"25.1","volume-title":"Handbook of Data Structures and Applications","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B.: Cuttings. In: Handbook of Data Structures and Applications, pp. 25.1\u201325.10. CRC Press, Boca Raton (2005)"},{"key":"9455_CR19","first-page":"131","volume-title":"Proceedings of the ACM Symposium on Computational Geometry (SoCG)","author":"B. Chazelle","year":"1989","unstructured":"Chazelle, B., Rosenberg, B.: Computing partial sums in multidimensional arrays. In: Proceedings of the ACM Symposium on Computational Geometry (SoCG), pp. 131\u2013139 (1989)"},{"key":"9455_CR20","unstructured":"Davoodi, P.: Data structures: range queries and space efficiency. Ph.D. thesis, Aarhus University (2011)"},{"key":"9455_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/978-3-642-32241-9_34","volume-title":"Proceedings of the International Computing and Combinatorics Conference (COCOON)","author":"P. Davoodi","year":"2012","unstructured":"Davoodi, P., Raman, R., Satti, S.R.: Succinct representations of binary trees for range minimum queries. In: Proceedings of the International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science, vol. 7434, pp. 396\u2013407. Springer, Berlin (2012)"},{"key":"9455_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"9455_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/978-3-642-02927-1_29","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)","author":"E.D. Demaine","year":"2009","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On Cartesian trees and range minimum queries. In: Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 5555, pp. 341\u2013353. Springer, Berlin (2009)"},{"key":"9455_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/3-540-51542-9_5","volume-title":"Proceedings of the Workshop on Algorithms and Data Structures (WADS)","author":"P.F. Dietz","year":"1989","unstructured":"Dietz, P.F.: Optimal algorithms for list indexing and subset rank. In: Proceedings of the Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, vol. 382, pp. 39\u201346. Springer, Berlin (1989)"},{"issue":"3","key":"9455_CR25","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0304-3975(80)90057-2","volume":"12","author":"D. Dobkin","year":"1980","unstructured":"Dobkin, D., Munro, J.I.: Determining the mode. Theor. Comput. Sci. 12(3), 255\u2013263 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"9455_CR26","unstructured":"Durocher, S.: A simple linear-space data structure for constant-time range minimum query. CoRR (2011). arXiv:1109.4460"},{"key":"9455_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1007\/978-3-642-22006-7_21","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)","author":"S. Durocher","year":"2011","unstructured":"Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range majority in constant time and linear space. In: Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 6755, pp. 244\u2013255. Springer, Berlin (2011)"},{"key":"9455_CR28","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.ic.2012.10.011","volume":"222","author":"S. Durocher","year":"2013","unstructured":"Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range majority in constant time and linear space. Inf. Comput. 222, 169\u2013179 (2013)","journal-title":"Inf. Comput."},{"key":"9455_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1007\/978-3-642-25591-5_17","volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC)","author":"A. Elmasry","year":"2011","unstructured":"Elmasry, A., He, M., Munro, J.I., Nicholson, P.: Dynamic range majority data structures. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 7074, pp. 150\u2013159. Springer, Berlin (2011)"},{"key":"9455_CR30","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":"Proceedings of the Latin American Theoretical Informatics Symposium (LATIN)","author":"J. Fischer","year":"2010","unstructured":"Fischer, J.: Optimal succinctness for range minimum queries. In: Proceedings of the Latin American Theoretical Informatics Symposium (LATIN). Lecture Notes in Computer Science, vol. 6034, pp. 158\u2013169. Springer, Berlin (2010)"},{"key":"9455_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/11780441_5","volume-title":"Proceedings of the Symposium on Combinatorial Pattern Matching (CPM)","author":"J. Fischer","year":"2006","unstructured":"Fischer, J., Heun, V.: Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE. In: Proceedings of the Symposium on Combinatorial Pattern Matching (CPM). Lecture Notes in Computer Science, vol. 4009, pp. 36\u201348. Springer, Berlin (2006)"},{"key":"9455_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/978-3-540-74450-4_41","volume-title":"Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE)","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: Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE). Lecture Notes in Computer Science, vol. 4614, pp. 459\u2013470. Springer, Berlin (2007)"},{"issue":"1","key":"9455_CR33","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/s11786-009-0007-8","volume":"3","author":"J. Fischer","year":"2010","unstructured":"Fischer, J., Heun, V.: Finding range minima in the middle: approximations and applications. Math. Comput. Sci. 3(1), 17\u201330 (2010)","journal-title":"Math. Comput. Sci."},{"key":"9455_CR34","first-page":"135","volume-title":"Proceedings of the ACM Symposium on the Theory of Computing (STOC)","author":"H.N. Gabow","year":"1984","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC), pp. 135\u2013143 (1984)"},{"key":"9455_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-642-03784-9_1","volume-title":"Proceedings of the String Processing and Information Retrieval Symposium (SPIRE)","author":"T. Gagie","year":"2009","unstructured":"Gagie, T., Puglisi, S.J., Turpin, A.: Range quantile queries: another virtue of wavelet trees. In: Proceedings of the String Processing and Information Retrieval Symposium (SPIRE). Lecture Notes in Computer Science, vol. 5721, pp. 1\u20136. Springer, Berlin (2009)"},{"key":"9455_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/978-3-642-24583-1_29","volume-title":"Proceedings of the Symposium on String Processing and Information Retrieval (SPIRE)","author":"T. Gagie","year":"2011","unstructured":"Gagie, T., He, M., Munro, J.I., Nicholson, P.: Finding frequent elements in compressed 2D arrays and strings. In: Proceedings of the Symposium on String Processing and Information Retrieval (SPIRE). Lecture Notes in Computer Science, vol. 7024, pp. 295\u2013300. Springer, Berlin (2011)"},{"key":"9455_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1007\/978-3-642-02927-1_40","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)","author":"B. Gfeller","year":"2009","unstructured":"Gfeller, B., Sanders, P.: Towards optimal range medians. In: Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 5555, pp. 475\u2013486. Springer, Berlin (2009)"},{"key":"9455_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/978-3-642-25591-5_20","volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC)","author":"M.J. Golin","year":"2011","unstructured":"Golin, M.J., Iacono, J., Krizanc, D., Raman, R., Rao, S.S.: Encoding 2D range maximum queries. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 7074, pp. 180\u2013189. Springer, Berlin (2011)"},{"key":"9455_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1007\/978-3-642-14165-2_51","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)","author":"M. Greve","year":"2010","unstructured":"Greve, M., J\u00f8rgensen, A.G., Larsen, K.D., Truelsen, J.: Cell probe lower bounds and approximations for range mode. In: Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 6198, pp. 605\u2013616. Springer, Berlin (2010)"},{"key":"9455_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/978-3-540-87744-8_42","volume-title":"Proceedings of the European Symposium on Algorithms (ESA)","author":"S. Har-Peled","year":"2008","unstructured":"Har-Peled, S., Muthukrishnan, S.: Range medians. In: Proceedings of the European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 5193, pp. 503\u2013514. Springer, Berlin (2008)"},{"key":"9455_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1007\/978-3-642-25591-5_18","volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC)","author":"M. He","year":"2011","unstructured":"He, M., Munro, J.I., Nicholson, P.: Dynamic range selection in linear space. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 7074, pp. 160\u2013169. Springer, Berlin (2011)"},{"key":"9455_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1007\/978-3-540-30551-4_49","volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC)","author":"J. J\u00e1J\u00e1","year":"2004","unstructured":"J\u00e1J\u00e1, J., Mortensen, C.W., Shi, Q.: Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 3341, pp. 558\u2013568. Springer, Berlin (2004)"},{"key":"9455_CR43","unstructured":"J\u00f8rgensen, A.G.: Data structures: sequence problems, range queries, and fault tolerance. Ph.D. thesis, Aarhus University (2010)"},{"key":"9455_CR44","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1137\/1.9781611973082.63","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"A.G. J\u00f8rgensen","year":"2011","unstructured":"J\u00f8rgensen, A.G., Larsen, K.D.: Range selection and median: tight cell probe lower bounds and adaptive data structures. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 805\u2013813 (2011)"},{"key":"9455_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1007\/978-3-540-24587-2_53","volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC)","author":"D. Krizanc","year":"2003","unstructured":"Krizanc, D., Morin, P., Smid, M.: Range mode and range median queries on lists and trees. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 2906, pp. 517\u2013526. Springer, Berlin (2003)"},{"key":"9455_CR46","first-page":"1","volume":"12","author":"D. Krizanc","year":"2005","unstructured":"Krizanc, D., Morin, P., Smid, M.: Range mode and range median queries on lists and trees. Nord. J. Comput. 12, 1\u201317 (2005)","journal-title":"Nord. J. Comput."},{"key":"9455_CR47","first-page":"85","volume-title":"Proceedings of the ACM Symposium on the Theory of Computing (STOC)","author":"K.G. Larsen","year":"2012","unstructured":"Larsen, K.G.: The cell probe complexity of dynamic range counting. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC), pp. 85\u201394 (2012)"},{"issue":"2","key":"9455_CR48","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J.: Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10(2), 157\u2013182 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9455_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"J.I. Munro","year":"1996","unstructured":"Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 1180, pp. 37\u201342. Springer, Berlin (1996)"},{"issue":"1","key":"9455_CR50","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0205001","volume":"5","author":"J.I. Munro","year":"1976","unstructured":"Munro, J.I., Spira, M.: Sorting and searching in multisets. SIAM J. Comput. 5(1), 1\u20138 (1976)","journal-title":"SIAM J. Comput."},{"key":"9455_CR51","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-540-73951-7_3","volume-title":"Proceedings of the Workshop on Algorithms and Data Structures (WADS)","author":"Y. Nekrich","year":"2007","unstructured":"Nekrich, Y.: Orthogonal range searching in linear and almost-linear space. In: Proceedings of the Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, vol. 4619, pp. 15\u201326. Springer, Berlin (2007)"},{"key":"9455_CR52","first-page":"603","volume-title":"Proceedings of the ACM Symposium on the Theory of Computing (STOC)","author":"M. P\u01cetra\u015fcu","year":"2010","unstructured":"P\u01cetra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC), pp. 603\u2013610 (2010)"},{"key":"9455_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1007\/978-3-540-77566-9_36","volume-title":"Proceedings of the Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)","author":"H. Petersen","year":"2008","unstructured":"Petersen, H.: Improved bounds for range mode and range median queries. In: Proceedings of the Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). Lecture Notes in Computer Science, vol. 4910, pp. 418\u2013423. Springer, Berlin (2008)"},{"key":"9455_CR54","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/j.ipl.2008.10.007","volume":"109","author":"H. Petersen","year":"2009","unstructured":"Petersen, H., Grabowski, S.: Range mode and range median queries in constant time and sub-quadratic space. Inf. Process. Lett. 109, 225\u2013228 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9455_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1007\/3-540-36285-1_11","volume-title":"Proceedings of the International Conference on Database Theory (ICDT)","author":"C.K. Poon","year":"2003","unstructured":"Poon, C.K.: Optimal range max datacub for fixed dimensions. In: Proceedings of the International Conference on Database Theory (ICDT). Lecture Notes in Computer Science, vol. 2572, pp. 158\u2013172. Springer, Berlin (2003)"},{"key":"9455_CR56","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.jda.2006.03.011","volume":"5","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct data structures for flexible text retrieval systems. J. Discrete Algorithms 5, 12\u201322 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"9455_CR57","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84800-070-4","volume-title":"The Algorithm Design Manual","author":"S. Skiena","year":"2008","unstructured":"Skiena, S.: The Algorithm Design Manual, 2nd edn. Springer, Berlin (2008)","edition":"2"},{"issue":"3","key":"9455_CR58","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6(3), 80\u201382 (1977)","journal-title":"Inf. Process. Lett."},{"key":"9455_CR59","first-page":"887","volume-title":"Proceedings of the ACM Symposium on the Theory of Computing (STOC)","author":"V. Vassilevska Williams","year":"2012","unstructured":"Vassilevska Williams, V.: Multiplying matrices faster than Coppersmith-Winograd. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC), pp. 887\u2013898 (2012)"},{"key":"9455_CR60","first-page":"128","volume-title":"Proceedings of the ACM Symposium on the Theory of Computing (STOC)","author":"A.C. Yao","year":"1982","unstructured":"Yao, A.C.: Space-time tradeoff for answering range queries. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC), pp. 128\u2013136 (1982)"},{"key":"9455_CR61","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0214022","volume":"14","author":"A.C. Yao","year":"1985","unstructured":"Yao, A.C.: On the complexity of maintaining partial sums. SIAM J. Comput. 14, 277\u2013288 (1985)","journal-title":"SIAM J. Comput."},{"key":"9455_CR62","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1137\/1.9781611973075.14","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"H. Yuan","year":"2010","unstructured":"Yuan, H., Atallah, M.J.: Data structures for range minimum queries. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 150\u2013160 (2010)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9455-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9455-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9455-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:25Z","timestamp":1558684465000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9455-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,8]]},"references-count":62,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,11]]}},"alternative-id":["9455"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9455-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,8]]}}}