Pith. sign in

REVIEW 5 minor 54 references

Two-dimensional range-maximum encodings can be near-optimal in space and still answer queries in sub-logarithmic time.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-11 18:21 UTC pith:RO74UKHZ

load-bearing objection 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.

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

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

Pawe{\l} Gawrychowski , Adam G\'orkiewicz , Srinivasa Rao Satti This is my paper
classification cs.DS MSC 68P0568W32
keywords 2D RMQrange maximum queriesencoding modelsuccinct data structuresspace-query trade-offCartesian-tree analoguesactive points
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

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.

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.

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.

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.

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 this falsifier — get emailed when new claim-graph text bears on it.

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.

Where Pith is reading between the lines

These are 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, 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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 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.

axioms (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 no independent evidence
    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 no independent evidence
    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 no independent evidence
    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 no independent evidence
    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.

pith-pipeline@v1.1.0-grok45 · 25345 in / 3162 out tokens · 41487 ms · 2026-07-11T18:21:44.144226+00:00 · methodology

0 comments
read the original 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 Adam G\'orkiewicz, Pawe{\l} Gawrychowski, Srinivasa Rao Satti.

Figure 1
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)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

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 2000

  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

  9. [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

    work page doi:10.1007/s00453-011-9499-0 2012

  10. [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

    doi:10.1007/s00224-013-9455-2 2014

  11. [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

    work page doi:10.1007/s00453-014-9881-9 2015

  12. [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

    work page doi:10.1098/rsta.2013.0131 2016

  13. [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

    work page doi:10.1007/s11786-017-0294-4 2017

  14. [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

    work page doi:10.1007/s00453-012-9683-x 2014

  15. [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

    work page doi:10.1016/j.ic.2012.10.011 2013

  16. [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 Economics, Shanghai, China, December 8-11, 2019, LIPIcs, pages 57:1–57:14. Schloss Da...

    work page doi:10.4230/lipics.isaac.2019.57 2019

  17. [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, December 7-10, 2025, LIPIcs, pages31:1–31:15.SchlossDagstuhl-Leibniz- Zentrum für Inf...

    work page doi:10.4230/lipics.isaac.2025.31 2025

  18. [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

    work page doi:10.1007/s11786-009-0007-8 2010

  19. [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

  20. [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 Computer Science, pages 152–165. Springer, 2008. doi:10.1007/978-3-540-69068-9\_16

    work page doi:10.1007/978-3-540-69068-9 2008

  21. [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:10.1145/800057.808675

    work page doi:10.1145/800057.808675 1984

  22. [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, SPIRE 2011, Pisa, Italy, October 17-21, 2011. Proceedings, Lecture Notes in Comput...

    work page doi:10.1007/978-3-642-24583-1 2011

  23. [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

    work page doi:10.1007/s00453-020-00687-6 2063

  24. [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

    work page doi:10.1016/j.tcs.2019.07.002 2020

  25. [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

    work page doi:10.1145/3381416 2020

  26. [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 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, Lecture Notes in Comput...

    doi:10.1007/978-3-662-47672-7 2015

  27. [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, Proceedings, Lecture Notes in Computer Science, pages 409–420. Springer,...

    work page doi:10.1007/978-3-319-62127-2 2017

  28. [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,

  29. [29]

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

    work page doi:10.1016/j.tcs.2015.10.012 2015

  30. [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, Languages and Programming, 37th International Colloquium, ICALP 2010, Bor- deaux, France...

    doi:10.1007/978-3-642-14165-2 2010

  31. [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

    work page doi:10.1145/3012939 2017

  32. [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

    doi:10.1137/0213024 1984

  33. [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

    work page doi:10.1007/s00453-025-01325-9 2025

  34. [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

    work page doi:10.1007/s00453-021-00856-1 2021

  35. [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

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

  36. [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 Festschrift, Venice, Italy, July 25, 2025, OASIcs, pages 12:1–12:12. Schloss Dags...

    work page doi:10.4230/oasics.grossi.12 2025

  37. [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

    doi:10.1016/j 2026

  38. [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

    work page doi:10.1145/3039873 2017

  39. [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

  40. [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

  41. [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

    Pith/arXiv arXiv 2021

  42. [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, USA, June 22-26, 2020, pages 1402–1415. ACM, 2020.doi:10.1145/3357713.3384260. 19

    doi:10.1145/3357713.3384260 2020

  43. [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 European Symposium on Algorithms, ESA 2021, Lisbon, Portugal (Virtual Conference), S...

    doi:10.4230/lipics.esa.2021.70 2021

  44. [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

    work page doi:10.1007/s00453-015-9987-8 2016

  45. [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 in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-...

    doi:10.1007/978-3-540-77566-9 2008

  46. [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

    doi:10.1016/j.ipl.2008.10.007 2009

  47. [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, pages 158–172. Springer, 2003.doi:10.1007/3-540-36285-1\_11

    work page doi:10.1007/3-540-36285-1 2003

  48. [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, 2015.doi:10.1007/978-3-319-15612-5\_1

    work page doi:10.1007/978-3-319-15612-5 2015

  49. [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

    doi:10.1145/1290672.1290680 2007

  50. [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

    work page doi:10.1016/j.jda.2006.03.011 2007

  51. [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 Computer Science, pages 111–123. Springer, 1988. URL:https://doi. org/10.1007/BFb...

    work page doi:10.1007/bfb0040379 1988

  52. [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 Computer Science, pages 333–350. Springer, 2013.doi:10.1007/ 978-3-642-40273-9\_21. 20

    2013

  53. [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

    work page doi:10.1016/j.ipl.2019.01.011 2019

  54. [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–160. SIAM, 2010.doi:10.1137/1.9781611973075.14. 21

    work page doi:10.1137/1.9781611973075.14 2010