{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,15]],"date-time":"2026-11-15T15:23:41Z","timestamp":1794756221497,"version":"4.9.1"},"reference-count":61,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>Given a static array of n totally ordered objects, the range minimum query problem is to build a data structure that allows us to answer efficiently subsequent on-line queries of the form \u201cwhat is the position of a minimum element in the subarray ranging from i to j?\u201d. We focus on two settings, where (1) the input array is available at query time, and (2) the input array is available only at construction time. In setting (1), we show new data structures (a) of size $\\frac{2n}{c(n)}-\\Theta\\bigl(\\frac{n\\lg\\lg n}{c(n)\\lg n}\\bigr)$ bits and query time $O(c(n))$ for any positive integer function $c(n)\\in O\\bigl(n^\\varepsilon\\bigr)$ for an arbitrary constant $0&lt;\\varepsilon&lt;1$, or (b) with $O(nH_k)+o(n)$ bits and $O(1)$ query time, where $H_k$ denotes the empirical entropy of kth order of the input array. In setting (2), we give a data structure of size $2n+o(n)$ bits and query time $O(1)$. All data structures can be constructed in linear time and almost in-place.<\/jats:p>","DOI":"10.1137\/090779759","type":"journal-article","created":{"date-parts":[[2011,4,13]],"date-time":"2011-04-13T18:19:27Z","timestamp":1302718767000},"page":"465-492","source":"Crossref","is-referenced-by-count":191,"title":["Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays"],"prefix":"10.1137","volume":"40","author":[{"given":"Johannes","family":"Fischer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Volker","family":"Heun","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,4,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1155-5"},{"key":"R2","unstructured":"A. Amir, G. M. Landau, and U. Vishkin,\n                      Efficient pattern matching with scaling\n                      , in Proceedings of the First Annual Symposium on Discrete Algorithms (SODA), 1990, pp. 344\u2013357."},{"key":"R3","first-page":"1209","volume":"11","author":"Arlazarov V. L.","year":"1975","journal-title":"Dokl. Akad. Nauk. SSSR, 194 (1970), pp. 487\u2013488 (in Russian); Soviet Math. Dokl."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2005.08.001"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1146-6"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0222017"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"I. Bialynicka-Birula and R. Grossi,\n                      Amortized rigidness in dynamic Cartesian trees\n                      , in Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Comput. Sci. 3884, Springer, Berlin, 2006, pp. 80\u201391.","DOI":"10.1007\/11672142_5"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"G. S. Brodal, P. Davoodi, and S. S. Rao,\n                      On space efficient two dimensional range minimum data structures\n                      , in Proceedings of the 18th Annual European Symposium on Algorithms (ESA), Lecture Notes in Comput. Sci. 6347, Springer, Berlin, 2010, pp. 171\u2013182.","DOI":"10.1007\/978-3-642-15781-3_15"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/s11786-007-0024-4"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"K.Y. Chen and K.M. Chao,\n                      On the range maximum-sum segment query problem\n                      , in Proceedings of the 15th International Symposium of Algorithms and Computation (ISAAC), Lecture Notes in Comput. Sci. 3341, Springer, Berlin, 2004, pp. 294\u2013305.","DOI":"10.1007\/978-3-540-30551-4_27"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700370539"},{"key":"R12","unstructured":"M. Crochemore, C. S. Iliopoulos, M. Kubica, M. S. Rahman, and T. Walen,\n                      Improved algorithms for the range next value problem and applications\n                      , in Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS), IBFI Schloss Dagstuhl, 2008, pp. 205\u2013216."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"P. Ferragina, F. Luccio, G. Manzini, and S. Muthukrishnan,\n                      Structuring labeled trees for optimal succinctness, and beyond\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2005, pp. 184\u2013196.","DOI":"10.1109\/SFCS.2005.69"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240243"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.012"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"J. Fischer,\n                      Optimal succinctness for range minimum queries\n                      , in Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN), Lecture Notes in Comput. Sci. 6034, Springer, Berlin, 2010, pp. 158\u2013169.","DOI":"10.1007\/978-3-642-12200-2_16"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.02.010"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. Fischer and V. Heun,\n                      Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE\n                      , in Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching (CPM), Lecture Notes in Comput. Sci. 4009, Springer, Berlin, 2006, pp. 36\u201348.","DOI":"10.1007\/11780441_5"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"J. Fischer and V. Heun,\n                      A new succinct representation of RMQ-information and improvements in the enhanced suffix array\n                      , in Proceedings of the First International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE), Lecture Notes in Comput. Sci. 4614, Springer, Berlin, 2007, pp. 459\u2013470.","DOI":"10.1007\/978-3-540-74450-4_41"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"J. Fischer, V. Heun, and S. Kramer,\n                      Optimal string mining under frequency constraints\n                      , in Proceedings of the 10th European Conference on Principles and Practice of Knowledge and Discovery in Databases (PKDD), Lecture Notes in Comput. Sci. 4213, Springer, Berlin, 2006, pp. 139\u2013150.","DOI":"10.1007\/11871637_17"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"J. Fischer, V. Heun, and H. M. St\u00fchler,\n                      Practical entropy bounded schemes for $O(1)$-range minimum queries\n                      , in Proceedings of the 18th IEEE Data Compression Conference (DCC), 2008, pp. 272\u2013281.","DOI":"10.1109\/DCC.2008.45"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.09.012"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"G. Franceschini, S. Muthukrishnan, and M. Pa\u02c7tra\u015fcu,\n                      Radix sorting with no extra space\n                      , in Proceedings of the 15th Annual European Symposium on Algorithms (ESA), Lecture Notes in Comput. Sci. 4698, Springer, Berlin, 2007, pp. 194\u2013205.","DOI":"10.1007\/978-3-540-75520-3_19"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, J. L. Bentley, and R. E. Tarjan,\n                      Scaling and related techniques for geometry problems\n                      , in Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), 1984, pp. 135\u2013143.","DOI":"10.1145\/800057.808675"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.047"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.09.014"},{"key":"R28","unstructured":"L. Georgiadis and R. E. Tarjan,\n                      Finding dominators revisited: Extended abstract\n                      , in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004, pp. 869\u2013878."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.041"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"R. Gonz\u00e1lez and G. Navarro,\n                      Statistical encoding of succinct data structures\n                      , in Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching (CPM), Lecture Notes in Comput. Sci. 4009, Springer, Berlin, 2006, pp. 294\u2013305.","DOI":"10.1007\/11780441_27"},{"key":"R31","unstructured":"R. Grossi, A. Gupta, and J. S. Vitter,\n                      High-order entropy-compressed text indexes\n                      , in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 841\u2013850."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"W. K. Hon, R. Shah, and J. S. Vitter,\n                      \n                        Space-efficient framework for top-\n                        k\n                        string retrieval problems\n                      \n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2009, pp. 713\u2013722.","DOI":"10.1109\/FOCS.2009.19"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"G. Jacobson,\n                      Space-efficient static trees and graphs\n                      , in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1989, pp. 549\u2013554.","DOI":"10.1109\/SFCS.1989.63533"},{"key":"R36","unstructured":"J. Jansson, K. Sadakane, and W.K. Sung,\n                      Ultra-succinct representation of ordered trees\n                      , in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, pp. 575\u2013584."},{"key":"R37","unstructured":"D. E. Knuth,\n                      The Art of Computer Programming. Vol.\n                      4\n                      , Fasc.\n                      4:\n                      Generating All Trees\u2014History of Combinatorial Generation\n                      , Addison-Wesley, Upper Saddle River, NJ, 2006."},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.052"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382782"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"R42","unstructured":"S. Muthukrishnan,\n                      Efficient algorithms for document retrieval problems\n                      , in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002, pp. 657\u2013666."},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1145\/1216370.1216372"},{"key":"R44","doi-asserted-by":"crossref","unstructured":"E. Ohlebusch, J. Fischer, and S. Gog,\n                      CST++\n                      , in Proceedings of the 17th International Symposium on String Processing and Information Retrieval (SPIRE), Lecture Notes in Comput. Sci. 6393, Springer, Berlin, 2010, pp. 322\u2013333.","DOI":"10.1007\/978-3-642-16321-0_34"},{"key":"R45","doi-asserted-by":"crossref","unstructured":"D. Okanohara and K. Sadakane,\n                      An online algorithm for finding the longest previous factors\n                      , in Proceedings of the 16th Annual European Symposium on Algorithms (ESA), Lecture Notes in Comput. Sci. 5193, Springer, Berlin, 2008, pp. 696\u2013707.","DOI":"10.1007\/978-3-540-87744-8_58"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-7122-0"},{"key":"R48","doi-asserted-by":"crossref","unstructured":"M. Pa\u02c7tra\u015fcu,\n                      Succincter\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2008, pp. 305\u2013313.","DOI":"10.1109\/FOCS.2008.83"},{"key":"R49","doi-asserted-by":"crossref","unstructured":"V. Ramachandran and U. Vishkin,\n                      Efficient parallel triconnectivity in logarithmic time\n                      , in Proceedings of the Third Aegean Workshop on Computing (AWOC), Lecture Notes in Comput. Sci. 319, Springer, Berlin, 1988, pp. 33\u201342.","DOI":"10.1007\/BFb0040371"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00087-7"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1198-x"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.03.011"},{"key":"R54","doi-asserted-by":"crossref","unstructured":"K. Sadakane and R. Grossi,\n                      Squeezing succinct data structures into entropy bounds\n                      , in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006, pp. 1230\u20131239.","DOI":"10.1145\/1109557.1109693"},{"key":"R55","doi-asserted-by":"crossref","unstructured":"K. Sadakane and G. Navarro,\n                      Fully-functional succinct trees\n                      , in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010, pp. 134\u2013149.","DOI":"10.1137\/1.9781611973075.13"},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.12.006"},{"key":"R57","doi-asserted-by":"publisher","DOI":"10.1145\/357114.357116"},{"key":"R58","doi-asserted-by":"crossref","unstructured":"T. Shibuya and I. Kurochkin,\n                      Match chaining algorithms for cDNA mapping\n                      , in Proceedings of the Third International Workshop on Algorithms in Bioinformatics (WABI), Lecture Notes in Comput. Sci. 2812, Springer, Berlin, 2003, pp. 462\u2013475.","DOI":"10.1007\/978-3-540-39763-2_33"},{"key":"R59","doi-asserted-by":"crossref","unstructured":"N. V\u00e4lim\u00e4ki and V. M\u00e4kinen,\n                      Space-efficient algorithms for document retrieval\n                      , in Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM), Lecture Notes in Comput. Sci. 4580, Springer, Berlin, 2007, pp. 205\u2013215.","DOI":"10.1007\/978-3-540-73437-6_22"},{"key":"R60","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358852"},{"key":"R61","doi-asserted-by":"crossref","unstructured":"H. Yuan and M. J. Atallah,\n                      Data structures for range minimum queries in multidimensional arrays\n                      , in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010, pp. 150\u2013160.","DOI":"10.1137\/1.9781611973075.14"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090779759","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:36:22Z","timestamp":1787337382000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090779759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":61,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/090779759"],"URL":"https:\/\/doi.org\/10.1137\/090779759","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}