Errata

Serious ones

1. 361 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.
2. 371 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 surface of the query.
3. 374 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.

Medium ones

1. 22 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.
2. 68 In line -3, "= 5" should be "= C[5]". Thanks to José Fuentes for noting this.
3. 79 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.
4. 80 In line 7 of Algorithm 4.6, the condition should be "<" instead of "≤". Thanks to Kajetan Johannes Hammerle for noting this.
5. 83 In the displayed formula, select_1(S,j) should be select_1(B,j). Thanks to Rolando Kindelan for noting this.
6. 88 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 "sum(A,i)". Thanks to Yusaku Kaneta for spotting this.
7. 154 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).
8. 169 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.
9. 186 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.
10. 193 In line 15, B should be V. Noted by Ariel Cáceres.
11. 195 In line -10, V[i][j]+1 should be m[V[i][j]]+1. Communicated by Kunihiko Sadakane.
12. 284 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.
13. 316 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.
14. 334 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.
15. 458 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.
16. 518 The space given for Gagie et al. 2012, under "Kernelization", is in addition to a context-free grammar for the text, not standalone.
17. 520 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.
18. 536 On the right of Figure 13.7, the trie node reached by "a" should have 5 inside, not a 4.

Small ones

1. 3 In line 3 of Section 1.2, "fluorished" should be "flourished". Thanks to Kunihiko Sadakane for noting this.
2. 118 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 pointer.
3. 127 In Footnote 1, it would be good to mention that a common way to express the formula is o(n log sigma) + O(n).
4. 188 In Secion 7.1.4, "deepest segments" should actually be "segments with no children". Noted by Ariel Cáceres.
5. 190 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 covering B[i,j].
6. 201 In lines 13 and 14 we could have used i-1 instead of i and the method would also work when t is of the same type of P[i]. 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 Sadakane.
7. 209 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 Sadakane.
8. 232 In line 5, it would be better to exchange u and v in this comment, because we have just discussed how to compute the area below v. Noted by Kunihiko Sadakane.
9. 276 The bibliographic entry of Belazzougui et al. is missing its second author, P. H. Cording.
10. 308 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 unknown."
11. 330 In line 14, "brand" should be "branch". Thanks to Kunihiko Sadakane for this.
12. 542 The second bibliographic entry of Belazzougui et al. (the last in the page) is missing its second author, P. H. Cording.