Pith. sign in

REVIEW 5 minor 54 references

Near-Optimal and Efficient Encoding for Two-Dimensional Range Minimum Queries

T0 review · 0 major / 5 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Two-dimensional range-maximum encodings can be near-optimal in space and still answer queries in sub-logarithmic time.

desk verdict Clean combinatorial tradeoff that finally bridges the 2012/2013 gap for 2D RMQ encodings; the co-active/origin + quarter-row machinery is new and the proofs hold up. read the letter →

arxiv 2607.04509 v1 pith:RO74UKHZ submitted 2026-07-05 cs.DS

Pawe{l} Gawrychowski , Adam Górkiewicz , Srinivasa Rao Satti This is my paper · ORCID
classification cs.DS MSC 68P0568W32
keywords 2DRMQrangemaximumqueriesencodingmodelsuccinctdatastructuresspace-querytrade-offCartesian-treeanaloguesactivepoints
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Given an m-by-n array, the encoding problem asks for a compact representation that reports the position of the maximum in any axis-aligned rectangle without reading the original array. Prior work offered either constant-time queries at substantially super-optimal space, or asymptotically optimal O(mn log m) space with no proven efficient query procedure. This paper closes that gap with a single-parameter trade-off: for every integer kappa between 1 and log log n, an encoding of O(kappa mn (log m + log log n)) bits answers every query in O(log to the power 1/kappa of n) time. The result shows that near-optimal space need not force sequential decoding of the whole representation, and that query speed can be dialed continuously against a mild space multiplier.

What carries the argument

Co-active pairs with origins in a binary column tree: every query is reduced to comparing two mutually visible points; each point is assigned an origin node, and a second tau-ary tree on depths organises local ranking and lifting structures so that each replacement moves the deeper origin across child blocks of a fixed ancestor, bounding the number of steps by the arity.

What would settle it

Exhibit a family of m-by-n arrays and rectangles for which the two candidates returned by the dyadic-block reduction are not co-active, or for which no encoding of the claimed size can answer all rectangles in the claimed time, violating the stated trade-off.

Watch

Extended reading notes

Core claim

For every integer kappa in [1, log log n] there exists a 2D-RMQ encoding of an m-by-n array that occupies O(kappa mn (log m + log log n)) bits and answers any range-maximum query in O(log^{1/kappa} n) time. In particular, constant kappa already yields near-optimal space whenever n is at most exponential in m, while kappa = log log n recovers constant query time at a log-log factor space cost.

Load-bearing premise

Every query rectangle can be answered by comparing exactly two mutually visible candidate points that a fixed O(mn log m)-bit preprocessing produces in constant time.

Editorial extensions

If this is right

  • Constant kappa already gives O(mn (log m + log log n))-bit encodings with polylogarithmic query time, asymptotically optimal whenever n is at most exponential in m.
  • Setting kappa = log log n recovers O(1) query time at only an O(log log n) multiplicative space blow-up over the information-theoretic lower bound.
  • The same co-active-origin and quarter-row machinery can be reused for other 2D range problems whose answers reduce to comparing structured pairs of points.
  • The gap between optimal encoding space and efficient support for 2D RMQ is no longer structural; only constant factors and lower-order terms remain open.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same depth-tree blocking idea may transfer to other encoding problems that currently possess only sequential optimal encodings (for example certain range top-k or range mode encodings).
  • If the O(mn log m) reduction itself can be made dynamic or partially dynamic, the whole trade-off would immediately yield dynamic near-optimal 2D RMQ encodings.
  • A matching lower-bound trade-off of the form “space O(mn log m + o(mn log log n)) forces super-constant query time” would settle whether the extra log-log factor is inherent.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies the encoding model for two-dimensional range maximum queries on an m imes n array (m≤n). It presents a family of encodings that, for every integer κ∈[1,loglogn], use O(κ mn(logm+loglogn)) bits and answer any axis-parallel range-maximum query in O(log^{1/κ}n) time (Theorem 1.1). The construction first reduces every query to a comparison of two mutually visible candidates via dyadic 1D-RMQ structures on rows, columns and power-of-two row blocks (Lemma 3.2). It then organises columns into a complete binary tree T, defines active sets and origins of points, and shows that the two candidates are always co-active. Co-active pairs are compared by a sequence of local ranking and lifting steps that move origins upward; a second τ-ary tree D on the depths of T (with τ=⌈log^{1/κ}n⌉) bounds the number of steps by O(τ). Both local primitives are realised by decomposing each active set into O(m) monotone quarter-rows and encoding them with standard rank/select and Elias-Fano structures. Space is controlled by the log-sum inequality applied level-wise on T and D.

Significance. The result closes a long-standing gap between the O(mn min{m,logn})-bit constant-time encoding of Brodal et al. (Algorithmica 2012) and the asymptotically optimal but non-queryable O(mn logm)-bit encoding of Brodal et al. (ESA 2013). For any constant ε>0 one obtains near-optimal space with polylogarithmic query time; taking κ=loglogn recovers constant query time at a loglogn space factor. The argument is fully combinatorial, self-contained, and relies only on classical succinct primitives (1D RMQ, partial rank/select, Elias-Fano) together with the log-sum inequality. No machine-checked proofs or code are supplied, yet the derivation is transparent and the trade-off is clean. The work therefore constitutes a genuine advance in the encoding complexity of multidimensional range queries.

minor comments (5)
  1. In the statement of Theorem 1.1 and throughout Section 5 the query-time bound is written O(log^{1/κ}n); a short parenthetical remark that this is O(τ) with τ=⌈log^{1/κ}n⌉ would make the dependence on the arity of D immediately visible.
  2. Figure 1 is helpful but the caption does not define the colours of the two paths in T; a one-sentence clarification would improve readability.
  3. Lemma 2.4 (log-sum inequality) is proved in full; a citation to the classical form would suffice and free a few lines.
  4. The phrase "inherently sequential" in the abstract and introduction is informal; replacing it by "requires a linear scan of the encoding" would be more precise.
  5. A brief remark on whether the same trade-off extends to the indexing model (or why it does not) would help place the result in the broader literature.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: space/query trade-off is derived from first-principles encodings and the log-sum inequality.

full rationale

The paper is a self-contained algorithmic construction. Theorem 1.1 is obtained by (i) an independent reduction (Lemma 3.2) that produces two mutually visible candidates via standard 1D RMQ on rows, columns and dyadic row blocks, (ii) a tree-of-columns origin machinery that is proved to preserve co-activity (Lemmas 4.2–4.6), and (iii) local ranking/lifting primitives (Lemmas 5.1, 5.3) whose space is bounded by the classical log-sum inequality (Lemma 2.4) applied to pairwise-disjoint families of quarter-rows. No parameter is fitted to data; no uniqueness theorem is imported from the authors’ prior work; no quantity is defined in terms of the quantity it is claimed to predict. The only external ingredients are the well-known 1D RMQ encoding of Fischer–Heun and the rank/select and Elias–Fano encodings of Raman et al. and Elias–Fano, all of which are independent of the 2D claim. Consequently the derivation chain contains no circular step.

Assumptions & free parameters 0 free parameters · 6 assumptions · 4 invented entities

The result rests on standard word-RAM and succinct-data-structure primitives plus a handful of combinatorial definitions introduced for the proof. No free parameters are fitted; the only tunable quantity is the explicit integer κ supplied by the user. Invented entities are purely definitional scaffolding (active sets, origins, quarter-rows) with no physical or empirical content.

assumptions (6)
  • standard math Word-RAM model with word size Θ(log n) and constant-time bit operations for tree navigation.
    Stated in Section 2; used for all query-time claims.
  • standard math 1D RMQ can be encoded in O(n) bits with O(1) query time (Fischer-Heun).
    Lemma 2.1; used both for the reduction of Lemma 3.2 and for visibility tests inside quarter-rows.
  • standard math Rank/select on a set of size k over universe U uses O(k + k log(U/k)) bits with O(1) queries (Raman et al.).
    Lemma 2.2; building block of the local ranking and lifting structures.
  • standard math Elias-Fano encoding of a monotone sequence of length k over [U] uses O(k + k log(U/k)) bits with O(1) access.
    Lemma 2.3; used to store local-column sequences inside quarter-rows.
  • standard math Log-sum inequality: sum k_i log(U_i/k_i) ≤ K log(U/K).
    Lemma 2.4; the sole tool that aggregates per-node space into the global O(mn(log m + log log n)) bound.
  • domain assumption Input elements are totally ordered and all weights are distinct (ties broken arbitrarily).
    Stated at the opening of Section 2; required for unique maxima and for the predecessor/successor definitions.
invented entities (4)
  • Active set A_u of a node u in the column tree
    purpose: Restricts the points that must be comparable at each node so that space stays near-optimal.
    Definition 4.1; purely combinatorial, no external evidence required.
  • Origin orig(p) of a point p
    purpose: Canonical highest node at which p is active; used to decide which lifting table to consult.
    Definition 4.3; derived from the downward-path property of Lemma 4.2.
  • Co-active pair
    purpose: Characterizes exactly the pairs that the encoding must be able to compare.
    Definition 4.4 and Lemma 4.6; links the reduction of Section 3 to the comparison structures of Section 5.
  • Quarter-row of an active set
    purpose: Decomposes A_u into O(m) monotone sequences so that rank and predecessor queries become 1-dimensional.
    Section 6; Observation 6.1 proves monotonicity from visibility.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Optimal and Efficient Encoding for Two-Dimensional Range Minimum Queries." pith.science (2026). https://pith.science/paper/RO74UKHZ

@misc{pith2026260704509,
  author       = {Pith},
  title        = {Pith review of: Near-Optimal and Efficient Encoding for Two-Dimensional Range Minimum Queries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RO74UKHZ}},
  note         = {Machine review of arXiv:2607.04509}
}
abstract

We consider the 2D RMQ encoding problem: given an $m\times n$ array of $mn$ elements over a total order, encode it such that, for any query rectangle, the position of its maximum element can be reported without accessing the original array. For $m \le n$, it is known how to encode the array in $O(mn \min\{m, \log n\})$ bits with $O(1)$-time queries [Brodal et al., Algorithmica 2012], and also how to obtain an asymptotically optimal encoding consisting of $O(mn \log m)$ bits [Brodal et al., ESA 2013]. However, the latter approach does not prove any guarantee on the query time, and it appears to be inherently sequential: it requires scanning the whole encoding to answer a query. We design a different encoding that uses near-optimal space while allowing for efficient queries. More concretely, for every parameter $\kappa\in[1, \log\log n]$, our encoding uses $O(\kappa mn(\log m+\log\log n))$ bits and answers 2D RMQ queries in $O(\log^{1/\kappa}n)$ time.

Figures

Figures reproduced from arXiv: 2607.04509 by the authors.

Figure 1
Figure 1. The query algorithm. The red and blue paths in [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 34 canonical work pages

  1. [1]

    Two-dimensionalrangeminimum queries

    AmihoodAmir, JohannesFischer, andMosheLewenstein. Two-dimensionalrangeminimum queries. InBinMaandKaizhongZhang, editors,Combinatorial Pattern Matching, 18th An- nual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings, Lecture Notes in Computer Science, pages 286–294. Springer, 2007.doi:10.1007/978-3-540-73437-6\ _29

    work page doi:10.1007/978-3-540-73437-6 2007

  2. [2]

    Lrm-trees: Compressed in- dices, adaptive sorting, and compressed permutations.Theor

    Jérémy Barbay, Johannes Fischer, and Gonzalo Navarro. Lrm-trees: Compressed in- dices, adaptive sorting, and compressed permutations.Theor. Comput. Sci., 459:26–41,

  3. [3]

    URL:https://doi.org/10.1016/j.tcs.2012.08.010,doi:10.1016/J.TCS.2012. 08.010

    doi:10.1016/j.tcs.2012.08.010 2012

  4. [4]

    Ian Munro, Gonzalo Navarro, and Yakov Nekrich

    Djamal Belazzougui, Travis Gagie, J. Ian Munro, Gonzalo Navarro, and Yakov Nekrich. Range majorities and minorities in arrays.Algorithmica, 83(6):1707–1733, 2021. URL: https://doi.org/10.1007/s00453-021-00799-7,doi:10.1007/S00453-021-00799-7

    work page doi:10.1007/s00453-021-00799-7 2021

  5. [5]

    Bender and Martin Farach-Colton

    Michael A. Bender and Martin Farach-Colton. The LCA problem revisited. In Gaston H. Gonnet, Daniel Panario, and Alfredo Viola, editors,LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings, Lecture Notes in Computer Science, pages 88–94. Springer, 2000.doi:10.1007/10719839\ _9

    doi:10.1007/10719839

  6. [6]

    Approximate range mode and range median queries

    Prosenjit Bose, Evangelos Kranakis, Pat Morin, and Yihui Tang. Approximate range mode and range median queries. In Volker Diekert and Bruno Durand, editors,STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings, Lecture Notes in Computer Science, pages 377–388. Springer, 2005.doi...

    work page doi:10.1007/978-3-540-31856-9 2005

  7. [7]

    The encoding complexity of two dimensional range minimum data structures

    Gerth Stølting Brodal, Andrej Brodnik, and Pooya Davoodi. The encoding complexity of two dimensional range minimum data structures. In Hans L. Bodlaender and Giuseppe F. Italiano, editors,Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia An- tipolis, France, September 2-4, 2013. Proceedings, Lecture Notes in Computer Science, pages 229–240. S...

    doi:10.1007/978-3-642-40450-4 2013

  8. [8]

    Two dimensional range minimum queries and fibonacci lattices.Theor

    Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, and Srini- vasa Rao Satti. Two dimensional range minimum queries and fibonacci lattices.Theor. Comput. Sci., 638:33–43, 2016. URL:https://doi.org/10.1016/j.tcs.2016.02.016, doi:10.1016/J.TCS.2016.02.016

    work page doi:10.1016/j.tcs.2016.02.016 2016

Show all 54 references
  1. [9]

    Srinivasa Rao

    Gerth Stølting Brodal, Pooya Davoodi, and S. Srinivasa Rao. On space efficient two dimensional range minimum data structures.Algorithmica, 63(4):815–830, 2012. URL: https://doi.org/10.1007/s00453-011-9499-0,doi:10.1007/S00453-011-9499-0

    2012 doi

  2. [10]

    Wilkinson

    TimothyM.Chan, StephaneDurocher, KasperGreenLarsen, JasonMorrison, andBryanT. Wilkinson. Linear-space data structures for range mode query in arrays.Theory Comput. Syst., 55(4):719–741, 2014. URL:https://doi.org/10.1007/s00224-013-9455-2,doi: 10.1007/S00224-013-9455-2

    2014 doi

  3. [11]

    Chan, Stephane Durocher, Matthew Skala, and Bryan T

    Timothy M. Chan, Stephane Durocher, Matthew Skala, and Bryan T. Wilkin- son. Linear-space data structures for range minority query in arrays.Algorithmica, 72(4):901–913, 2015. URL:https://doi.org/10.1007/s00453-014-9881-9,doi:10. 1007/S00453-014-9881-9

    2015 doi

  4. [12]

    Srinivasa Rao

    Pooya Davoodi, Gonzalo Navarro, Rajeev Raman, and S. Srinivasa Rao. Encoding range minima and range top-2 queries.Philosophical Transactions of the Royal Soci- ety A: Mathematical, Physical and Engineering Sciences, 372(2016):20130131, 2014.doi: 10.1098/rsta.2013.0131

    2016 doi

  5. [13]

    On succinct representations of binary trees.Math

    Pooya Davoodi, Rajeev Raman, and Srinivasa Rao Satti. On succinct representations of binary trees.Math. Comput. Sci., 11(2):177–189, 2017. URL:https://doi.org/10.1007/ s11786-017-0294-4,doi:10.1007/S11786-017-0294-4

    2017 doi

  6. [14]

    Demaine, Gad M

    Erik D. Demaine, Gad M. Landau, and Oren Weimann. On cartesian trees and range minimum queries.Algorithmica, 68(3):610–625, 2014. URL:https://doi.org/10.1007/ s00453-012-9683-x,doi:10.1007/S00453-012-9683-X

    2014 doi

  7. [15]

    Ian Munro, Patrick K

    Stephane Durocher, Meng He, J. Ian Munro, Patrick K. Nicholson, and Matthew Skala. Range majority in constant time and linear space.Inf. Comput., 222:169–179, 2013. URL: https://doi.org/10.1016/j.ic.2012.10.011,doi:10.1016/J.IC.2012.10.011

    2013 doi

  8. [16]

    Ian Munro, Yakov Nekrich, and Bryce Sandlund

    Hicham El-Zein, Meng He, J. Ian Munro, Yakov Nekrich, and Bryce Sandlund. On ap- proximate range mode and range selection. In Pinyan Lu and Guochuan Zhang, editors, 30th International Symposium on Algorithms and Computation, ISAAC 2019, Shanghai University of Finance and Econo...

    2019 doi

  9. [17]

    Compressibility measures and succinct data structures for piecewise linear approximations

    Paolo Ferragina and Filippo Lari. Compressibility measures and succinct data structures for piecewise linear approximations. In Ho-Lin Chen, Wing-Kai Hon, and Meng-Tsung Tsai, editors,36th International Symposium on Algorithms and Computation, ISAAC 2025, Tainan, Taiwan, Decem...

    2025 doi

  10. [18]

    Finding range minima in the middle: Approximations and applications.Math

    Johannes Fischer and Volker Heun. Finding range minima in the middle: Approximations and applications.Math. Comput. Sci., 3(1):17–30, 2010. URL:https://doi.org/10.1007/ s11786-009-0007-8,doi:10.1007/S11786-009-0007-8. 17

    2010 doi

  11. [19]

    Space-efficient preprocessing schemes for range min- imum queries on static arrays.SIAM J

    Johannes Fischer and Volker Heun. Space-efficient preprocessing schemes for range min- imum queries on static arrays.SIAM J. Comput., 40(2):465–492, 2011.doi:10.1137/ 090779759

    2011

  12. [20]

    An(other) entropy-bounded compressed suffix tree

    Johannes Fischer, Veli Mäkinen, and Gonzalo Navarro. An(other) entropy-bounded compressed suffix tree. In Paolo Ferragina and Gad M. Landau, editors,Combinato- rial Pattern Matching, 19th Annual Symposium, CPM 2008, Pisa, Italy, June 18-20, 2008, Proceedings, Lecture Notes in ...

    2008 doi

  13. [21]

    Gabow, Jon Louis Bentley, and Robert Endre Tarjan

    Harold N. Gabow, Jon Louis Bentley, and Robert Endre Tarjan. Scaling and related tech- niquesforgeometry problems. InRichard A.DeMillo, editor,Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pages 135–143. ACM, ...

    1984 doi

  14. [22]

    Ian Munro, and Patrick K

    Travis Gagie, Meng He, J. Ian Munro, and Patrick K. Nicholson. Finding frequent ele- ments in compressed 2d arrays and strings. In Roberto Grossi, Fabrizio Sebastiani, and Fabrizio Silvestri, editors,String Processing and Information Retrieval, 18th International Symposium, SP...

    2011 doi

  15. [23]

    Compressed dynamic range majority and minority data structures.Algorithmica, 82(7):2063–2086, 2020

    Travis Gagie, Meng He, and Gonzalo Navarro. Compressed dynamic range majority and minority data structures.Algorithmica, 82(7):2063–2086, 2020. URL:https://doi.org/ 10.1007/s00453-020-00687-6,doi:10.1007/S00453-020-00687-6

    doi

  16. [24]

    Compressed range minimum queries.Theor

    Pawel Gawrychowski, Seungbum Jo, Shay Mozes, and Oren Weimann. Compressed range minimum queries.Theor. Comput. Sci., 812:39–48, 2020. URL:https://doi.org/10. 1016/j.tcs.2019.07.002,doi:10.1016/J.TCS.2019.07.002

    2020 doi

  17. [25]

    Submatrix maximum queries in monge and partial monge matrices are equivalent to predecessor search.ACM Trans

    Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Submatrix maximum queries in monge and partial monge matrices are equivalent to predecessor search.ACM Trans. Al- gorithms, 16(2):16:1–16:24, 2020.doi:10.1145/3381416

    2020 doi

  18. [26]

    Nicholson

    Pawel Gawrychowski and Patrick K. Nicholson. Optimal encodings for range top- k k , selec- tion, and min-max. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bet- tinaSpeckmann, editors,Automata, Languages, and Programming - 42nd International Col- loquium, ICALP 2...

    2015 doi

  19. [27]

    Nicholson

    Pawel Gawrychowski and Patrick K. Nicholson. Optimal query time for encoding range majority. In Faith Ellen, Antonina Kolokolova, and Jörg-Rüdiger Sack, editors,Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 - August 2...

    2017 doi

  20. [28]

    Golin, John Iacono, Danny Krizanc, Rajeev Raman, Srinivasa Rao Satti, and Sunil M

    Mordecai J. Golin, John Iacono, Danny Krizanc, Rajeev Raman, Srinivasa Rao Satti, and Sunil M. Shende. Encoding 2d range maximum queries.Theor. Comput. Sci., 609:316–327,

  21. [29]

    URL:https://doi.org/10.1016/j.tcs.2015.10.012,doi:10.1016/J.TCS.2015. 10.012

    2015 doi

  22. [30]

    Cell probe lower bounds and approximations for range mode

    Mark Greve, Allan Grønlund Jørgensen, Kasper Dalgaard Larsen, and Jakob Truelsen. Cell probe lower bounds and approximations for range mode. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, 18 Automata, Language...

    2010 doi

  23. [31]

    Srinivasa Rao

    Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, and S. Srinivasa Rao. Asymptotically optimal encodings of range data structures for selection and top-kqueries. ACM Trans. Algorithms, 13(2):28:1–28:31, 2017.doi:10.1145/3012939

    2017 doi

  24. [32]

    Fast algorithms for finding nearest common ancestors

    Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13(2):338–355, 1984.doi:10.1137/0213024

    1984 doi

  25. [33]

    Space-efficient data structure for next/previous larger/smaller value queries.Algorithmica, 87(10):1369–1392, 2025

    Seungbum Jo and Geunho Kim. Space-efficient data structure for next/previous larger/smaller value queries.Algorithmica, 87(10):1369–1392, 2025. URL:https://doi. org/10.1007/s00453-025-01325-9,doi:10.1007/S00453-025-01325-9

    2025 doi

  26. [34]

    Encoding two-dimensional range top-k queries.Algorithmica, 83(11):3379–3402, 2021

    Seungbum Jo, Rahul Lingala, and Srinivasa Rao Satti. Encoding two-dimensional range top-k queries.Algorithmica, 83(11):3379–3402, 2021. URL:https://doi.org/10.1007/ s00453-021-00856-1,doi:10.1007/S00453-021-00856-1

    2021 doi

  27. [35]

    Simultaneous encodings for range and next/previous larger/smaller value queries.Theor

    Seungbum Jo and Srinivasa Rao Satti. Simultaneous encodings for range and next/previous larger/smaller value queries.Theor. Comput. Sci., 654:80–91, 2016. URL:https://doi. org/10.1016/j.tcs.2016.01.043,doi:10.1016/J.TCS.2016.01.043

    2016 doi

  28. [36]

    Encoding data structures for range queries on arrays

    Seungbum Jo and Srinivasa Rao Satti. Encoding data structures for range queries on arrays. In Alessio Conte, Andrea Marino, Giovanna Rosone, and Jeffrey Scott Vitter, ed- itors,From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi’s 60th Birthday, Grossi’s F...

    2025 doi

  29. [37]

    Encodings for range minimum queries over bounded alphabets.Theor

    Seungbum Jo and Srinivasa Rao Satti. Encodings for range minimum queries over bounded alphabets.Theor. Comput. Sci., 1070:115824, 2026. URL:https://doi.org/10.1016/j. tcs.2026.115824,doi:10.1016/J.TCS.2026.115824

    2026 doi

  30. [38]

    Submatrix maximum queries in monge matrices and partial monge matrices, and their applications.ACM Trans

    Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir. Submatrix maximum queries in monge matrices and partial monge matrices, and their applications.ACM Trans. Algorithms, 13(2):26:1–26:42, 2017.doi:10.1145/3039873

    2017 doi

  31. [39]

    Searching for frequent colors in rectangles

    Marek Karpinski and Yakov Nekrich. Searching for frequent colors in rectangles. InPro- ceedings of the 20th Annual Canadian Conference on Computational Geometry, Montréal, Canada, August 13-15, 2008, 2008

    2008

  32. [40]

    Danny Krizanc, Pat Morin, and Michiel H. M. Smid. Range mode and range median queries on lists and trees.Nord. J. Comput., 12(1):1–17, 2005

    2005

  33. [41]

    Nearly tight lower bounds for succinct range minimum query.CoRR, abs/2111.02318, 2021

    Mingmou Liu. Nearly tight lower bounds for succinct range minimum query.CoRR, abs/2111.02318, 2021. URL:https://arxiv.org/abs/2111.02318,arXiv:2111.02318

    2021 arXiv

  34. [42]

    Lower bound for succinct range minimum query

    Mingmou Liu and Huacheng Yu. Lower bound for succinct range minimum query. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors,Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, ...

    2020 doi

  35. [43]

    Ian Munro, Patrick K

    J. Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner, and Sebastian Wild. Hy- persuccinct trees - new universal tree source codes for optimal compressed tree data struc- tures and range minima. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual Euro...

    2021 doi

  36. [44]

    Thankachan

    Gonzalo Navarro and Sharma V. Thankachan. Optimal encodings for range major- ity queries.Algorithmica, 74(3):1082–1098, 2016. URL:https://doi.org/10.1007/ s00453-015-9987-8,doi:10.1007/S00453-015-9987-8

    2016 doi

  37. [45]

    Improved bounds for range mode and range median queries

    Holger Petersen. Improved bounds for range mode and range median queries. In Vil- iam Geffert, Juhani Karhumäki, Alberto Bertoni, Bart Preneel, Pavol Návrat, and Mária Bieliková, editors,SOFSEM 2008: Theory and Practice of Computer Science, 34th Con- ference on Current Trends ...

    2008 doi

  38. [46]

    Range mode and range median queries in constant time and sub-quadratic space.Inf

    Holger Petersen and Szymon Grabowski. Range mode and range median queries in constant time and sub-quadratic space.Inf. Process. Lett., 109(4):225–228, 2009. URL:https: //doi.org/10.1016/j.ipl.2008.10.007,doi:10.1016/J.IPL.2008.10.007

    2009 doi

  39. [47]

    Optimal range max datacube for fixed dimensions

    Chung Keung Poon. Optimal range max datacube for fixed dimensions. In Diego Cal- vanese, Maurizio Lenzerini, and Rajeev Motwani, editors,Database Theory - ICDT 2003, 9th International Conference, Siena, Italy, January 8-10, 2003, Proceedings, Lecture Notes in Computer Science,...

    2003 doi

  40. [48]

    Encoding data structures

    Rajeev Raman. Encoding data structures. In M. Sohel Rahman and Etsuji Tomita, editors, WALCOM: Algorithms and Computation - 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings, Lecture Notes in Computer Science, pages 1–7. Springer, 20...

    2015 doi

  41. [49]

    Srinivasa Rao

    Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct indexable dictionaries with applications to encodingk-ary trees, prefix sums and multisets.ACM Transactions on Algorithms, 3(4):43, 2007.doi:10.1145/1290672.1290680

    2007 doi

  42. [50]

    Succinct data structures for flexible text retrieval systems.J

    Kunihiko Sadakane. Succinct data structures for flexible text retrieval systems.J. Discrete Algorithms, 5(1):12–22, 2007. URL:https://doi.org/10.1016/j.jda.2006.03.011,doi: 10.1016/J.JDA.2006.03.011

    2007 doi

  43. [51]

    On finding lowest common ancestors: Simplification and parallelization

    Baruch Schieber and Uzi Vishkin. On finding lowest common ancestors: Simplification and parallelization. In John H. Reif, editor,VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, AWOC 88, Corfu, Greece, June 28 - July 1, 1988, Proceedings, Lecture Notes in C...

    1988 doi

  44. [52]

    Array range queries

    Matthew Skala. Array range queries. In Andrej Brodnik, Alejandro López-Ortiz, Venkatesh Raman, and Alfredo Viola, editors,Space-Efficient Data Structures, Streams, and Al- gorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, Lecture Notes in Compute...

    2013

  45. [53]

    Theeffectiveentropyofnext/previouslarger/smallervaluequeries.Inf

    DekelTsur. Theeffectiveentropyofnext/previouslarger/smallervaluequeries.Inf. Process. Lett., 145:39–43, 2019. URL:https://doi.org/10.1016/j.ipl.2019.01.011,doi:10. 1016/J.IPL.2019.01.011

    2019 doi

  46. [54]

    Hao Yuan and Mikhail J. Atallah. Data structures for range minimum queries in mul- tidimensional arrays. In Moses Charikar, editor,Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 150–16...

    2010 doi

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.