Notation: line -1 means the last line of a page, line -2 means the next-to-last,
and so on. Each entry is preceded by its page number.
Errata likely to compromise reader's understanding.
In the middle of the page, it says "As the k^2 children distribute
across k contiguous segments in the LOUDS layout, the cost that is
charged to v decreases to O(k)". This argument is correct when
reused for the nodes of type (2), but for nodes of type (1) all the children
are contained in the query, and then all the children are interesting, and
contiguous in the LOUDS layout. Therefore, the correct cost charged to
v is O(1). This allows us remove the factor k that
accompanies occ in the displayed formula of the final cost. Thanks
to Ariel Cáceres for noting this. Further, there is an extra closing
parenthesis at the end of this formula.
Near the bottom of the page,
by the same argument of the correction in page 361, the factor k^(d-1)
multiplying occ can be removed. Instead, q^(d-1) should rather
be d * q^(d-1) , which is the area of the query.
The method for finding the m closest points via successively enlarging
the area until at least m points are found is not complete. Once those
points are found, we must take the distance to the mth closest one, and
perform a final query with this distance. Then we capture at least m
points again and then take the m closest ones. This is because a box
around the query may capture points that, with Manhattan distance, are farther
than some points not included in the box. Thanks to Patricio Huepe for
pointing this out.
Errata that affect technical correctness but either the reader is most
likely to easily spot them, or the errors are not important for the matter.
Example 2.10 is not totally consistent with Example 2.8, because here we are
considering the terminator $ for the string S, and in Example 2.8 we
are not. As a consequence, it could have been that the high-order entropy was
larger than the zero-order entropy.
Thanks to Sebastian Maneth for noting this.
In line -3, "= 5" should be "= C".
Thanks to José Fuentes for noting this.
In Figure 4.4, the value "10" in the array R (on top) should not be grayed.
Thanks to Kajetan Johannes Hammerle for noting this.
In line 7 of Algorithm 4.6, the condition should be "<" instead of "≤".
Thanks to Kajetan Johannes Hammerle for noting this.
In the displayed formula, select_1(S,j) should be select_1(B,j).
Thanks to Rolando Kindelan for noting this.
In the middle of the page it says "If A contains zeros, we can instead
encode the values A[i]+i...". That "A[i]" should rather be
Thanks to Yusaku Kaneta for spotting this.
In line 2, it should have said n o(H_0(S)) bits, not
o(n H_0(S)) bits. Further, this can then be expressed as
o(n H_0(S)) + O(n) bits, which then matches correctly with the
rest of the analysis (see the small errata in page 127).
Right before Example 7.4, bwdsearch(B,i,-d-1) should be
bwdsearch(B,i,-d-1)+1, as implied by the formula of enclose(B,i)
in the previous page.
Thanks to Ariel Cáceres for noting this.
Before Example 7.10, we say we use fwdsearch(i-1,m). However, we have
described this algorithm only for the case m < 0, whereas it could be
that the minimum excess in the range is m=1. This exception can be
easily handled by noting that, in this case, fwdsearch(i-1,1) is always
i. The same holds a few lines later for fwdsearch(i-1,M) when
M = -1; the answer is i. Thanks to Ariel Cáceres for noting this.
In line 15, B should be V. Noted by Ariel Cáceres.
In line -10, V[i][j]+1 should be m[V[i][j]]+1. Communicated by
The code for adj(G,v,u) is much more complicated than necessary. One
can remove lines 6-9 and add a line "if v < u then
exchange u and v" between lines 2 and 3.
Also, in line 18, b+j should be b-v+j.
The definition of L, "Every run of k (equal) brackets in
B_s...", could be clearer: "Every run of brackets belonging to the
same node in B_s (note that those brackets must be equal)...". Thanks to
Simon Gog for noting this.
Algorithm 9.19 claims to correspond to the algorithm "Face-2" referenced in
page 342, but they have some subtle differences, since our algorithm never
uses an edge that crosses the imaginary line and sometimes this is necessary.
In fact, one must remember the point (not necessarily node) p where
the edge would cross the line (initially p is the source), and allow
following edges if the cross the line exactly at point p. This fixes
some special cases where the general algorithm would fail.
In lines 17-18 of Algorithm 12.4 (procedure insw), the algorithm needs to
decrease i to account for the bits skipped in the left child, that is,
insert the instruction i = i - v.num. Thanks to Jan-Philipp Tarnowski
for noting this.
The space given for Gagie et al. 2012, under "Kernelization", is in addition
to a context-free grammar for the text, not standalone.
In Example 13.14, the penultimate block of S should look "ade ae"
rather than "adeae". The string is the same, but the logic of its generation
is apparent when properly segmented. Similarly, there should be a space after
the underlined "b" in the last string.
Errata on references, language, fonts, and other not really compromising
Found an error? Please let us know
and enter our Hall of Fame!
In line 3 of Section 1.2, "fluorished" should be "flourished".
Thanks to Kunihiko Sadakane for noting this.
In the bibliographic discussion on compressible permutations,
we found that an old paper [T. Takaoka,
A New Measure of Disorder in Sorting, Proc. CATS, pp. 77-86, 1998]
had already given the idea of merging in the order induced by the Huffman tree
to perform MergeSort. Followups were pubished much later in a conference
[T. Takaoka, Partial solution and entropy, Proc. 34th MFCS, pp. 700-711, 2009]
and then in a journal
[T. Takaoka, Entropy as computational complexity, Journal of Information
Processing 18:227-241, 2010]. Thanks to Jérémy Barbay for this
In Footnote 1, it would be good to mention that a common way to express the
formula is o(n log sigma) + O(n).
In Secion 7.1.4, "deepest segments" should actually be "segments
with no children". Noted by Ariel Cáceres.
In line -12, "if have" should be "if we have". Further, we might note that the
access to C[.][l'] requires first shifting the bits of the last block
We cite Sadakane (2007), but not the correct one: Succinct data structures for
flexible text retrieval systems. Journal of Discrete Algorithms, 5, 12–22.
In this paper, he actually gives a general rmq_A solution using 4n+o(n)
bits by adding n-1 leaves to the Cartesian tree. Noted by Kunihiko
The bibliographic entry of Belazzougui et al. is missing its second author,
P. H. Cording.
Instead of "The exact entropy of planar graphs (without defining their mapping
to the plane) is unknown, but it must be less than 3.58e.", the
following would have been more accurate: "Planar graphs (without defining
their mapping to the plane) must have a lower entropy, but that value is
In line 14, "brand" should be "branch". Thanks to Kunihiko Sadakane for this.
The second bibliographic entry of Belazzougui et al. (the last in the page) is missing
its second author, P. H. Cording.