cp-algorithms
diff --git a/‎src/algebra/polynomial.md
Lines changed: 3 additions & 3 deletions b/‎src/algebra/polynomial.md
Lines changed: 3 additions & 3 deletions
diff --git a/‎src/data_structures/disjoint_set_union.md
Lines changed: 2 additions & 2 deletions b/‎src/data_structures/disjoint_set_union.md
Lines changed: 2 additions & 2 deletions
diff --git a/‎src/data_structures/fenwick.md
Lines changed: 17 additions & 17 deletions b/‎src/data_structures/fenwick.md
Lines changed: 17 additions & 17 deletions
diff --git a/‎src/data_structures/segment_tree.md
Lines changed: 2 additions & 2 deletions b/‎src/data_structures/segment_tree.md
Lines changed: 2 additions & 2 deletions
diff --git a/‎src/data_structures/sqrt_decomposition.md
Lines changed: 6 additions & 6 deletions b/‎src/data_structures/sqrt_decomposition.md
Lines changed: 6 additions & 6 deletions
diff --git a/‎src/geometry/convex_hull_trick.md
Lines changed: 1 addition & 1 deletion b/‎src/geometry/convex_hull_trick.md
Lines changed: 1 addition & 1 deletion
diff --git a/‎src/graph/hld.md
Lines changed: 1 addition & 1 deletion b/‎src/graph/hld.md
Lines changed: 1 addition & 1 deletion
@@ -172,9 +172,9 @@ It gives us an $O(n \log n)$ algorithm when you need to compute values in powers
 ### Multi-point Evaluation
 Assume you need to calculate $A(x_1), \dots, A(x_n)$. As mentioned earlier, $A(x) \equiv A(x_i) \pmod{x-x_i}$. Thus you may do the following:
 
-1. Compute a segment tree such that in the segment $[l;r)$ stands the product $P_{l, r}(x) = (x-x_l)(x-x_{l+1})\dots(x-x_{r-1})$.
-2. Starting with $l=1$ and $r=n$ at the root node. Let $m=\lfloor(l+r)/2\rfloor$. Let's move down to $[l;m)$ with the polynomial $A(x) \pmod{P_{l,m}(x)}$.
-3. This will recursively compute $A(x_l), \dots, A(x_{m-1})$, now do the same for $[m;r)$ with $A(x) \pmod{P_{m,r}(x)}$.
+1. Compute a segment tree such that in the segment $[l,r)$ stands the product $P_{l, r}(x) = (x-x_l)(x-x_{l+1})\dots(x-x_{r-1})$.
+2. Starting with $l=1$ and $r=n$ at the root node. Let $m=\lfloor(l+r)/2\rfloor$. Let's move down to $[l,m)$ with the polynomial $A(x) \pmod{P_{l,m}(x)}$.
+3. This will recursively compute $A(x_l), \dots, A(x_{m-1})$, now do the same for $[m,r)$ with $A(x) \pmod{P_{m,r}(x)}$.
 4. Concatenate the results from the first and second recursive call and return them.
 
 The whole procedure will run in $O(n \log^2 n)$.
 
@@ -275,7 +275,7 @@ With DSU you can find the end point, to which we get after following all edges f
 
 We have a segment of length $L$, each element initially has the color 0.
-We have to repaint the subarray $[l; r]$ with the color $c$ for each query $(l, r, c)$.
+We have to repaint the subarray $[l, r]$ with the color $c$ for each query $(l, r, c)$.
 At the end we want to find the final color of each cell.
 We assume that we know all the queries in advance, i.e. the task is offline.
 
@@ -284,7 +284,7 @@ Thus initially each cell points to itself.
 After painting one requested repaint of a segment, all cells from that segment will point to the cell after the segment.
 
 Now to solve this problem, we consider the queries **in the reverse order**: from last to first.
-This way when we execute a query, we only have to paint exactly the unpainted cells in the subarray $[l; r]$.
+This way when we execute a query, we only have to paint exactly the unpainted cells in the subarray $[l, r]$.
 All other cells already contain their final color.
 To quickly iterate over all unpainted cells, we use the DSU.
 We find the left-most unpainted cell inside of a segment, repaint it, and with the pointer we move to the next empty cell to the right.
 
@@ -6,7 +6,7 @@ Let, $f$ be some _reversible_ function and $A$ be an array of integers of length
 
 Fenwick tree is a data structure which:
 
-* calculates the value of function $f$ in the given range $[l; r]$ (i.e. $f(A_l, A_{l+1}, \dots, A_r)$) in $O(\log n)$ time;
+* calculates the value of function $f$ in the given range $[l, r]$ (i.e. $f(A_l, A_{l+1}, \dots, A_r)$) in $O(\log n)$ time;
 * updates the value of an element of $A$ in $O(\log n)$ time;
 * requires $O(N)$ memory, or in other words, exactly the same memory required for $A$;
 * is easy to use and code, especially, in the case of multidimensional arrays.
@@ -24,7 +24,7 @@ Fenwick tree was first described in a paper titled "A new data structure for cum
 For the sake of simplicity, we will assume that function $f$ is just a *sum function*.
 
 Given an array of integers $A[0 \dots N-1]$.
-A Fenwick tree is just an array $T[0 \dots N-1]$, where each of its elements is equal to the sum of elements of $A$ in some range $[g(i); i]$:
+A Fenwick tree is just an array $T[0 \dots N-1]$, where each of its elements is equal to the sum of elements of $A$ in some range $[g(i), i]$:
 $$T_i = \sum_{j = g(i)}^{i}{A_j},$$
 where $g$ is some function that satisfies $0 \le g(i) \le i$.
 We will define the function in the next few paragraphs.
@@ -37,7 +37,7 @@ Many people will actually use a version of the Fenwick tree that uses one-based
 Therefore you will also find an alternative implementation using one-based indexing in the implementation section.
 Both versions are equivalent in terms of time and memory complexity.
 
-Now we can write some pseudo-code for the two operations mentioned above - get the sum of elements of $A$ in the range $[0; r]$ and update (increase) some element $A_i$:
+Now we can write some pseudo-code for the two operations mentioned above - get the sum of elements of $A$ in the range $[0, r]$ and update (increase) some element $A_i$:
 
 ```python
 def sum(int r):
@@ -54,19 +54,19 @@ def increase(int i, int delta):
 
 The function `sum` works as follows:
 
-1. first, it adds the sum of the range $[g(r); r]$ (i.e. $T[r]$) to the `result`
-2. then, it "jumps" to the range $[g(g(r)-1); g(r)-1]$, and adds this range's sum to the `result`
-3. and so on, until it "jumps" from $[0; g(g( \dots g(r)-1 \dots -1)-1)]$ to $[g(-1); -1]$; that is where the `sum` function stops jumping.
+1. first, it adds the sum of the range $[g(r), r]$ (i.e. $T[r]$) to the `result`
+2. then, it "jumps" to the range $[g(g(r)-1), g(r)-1]$, and adds this range's sum to the `result`
+3. and so on, until it "jumps" from $[0, g(g( \dots g(r)-1 \dots -1)-1)]$ to $[g(-1), -1]$; that is where the `sum` function stops jumping.
 
 The function `increase` works with the same analogy, but "jumps" in the direction of increasing indices:
 
-1. sums of the ranges $[g(j); j]$ that satisfy the condition $g(j) \le i \le j$ are increased by `delta` , that is `t[j] += delta`. Therefore we updated all elements in $T$ that corresponds to ranges in with $A_i$ lies.
+1. sums of the ranges $[g(j), j]$ that satisfy the condition $g(j) \le i \le j$ are increased by `delta` , that is `t[j] += delta`. Therefore we updated all elements in $T$ that corresponds to ranges in with $A_i$ lies.
 
 It is obvious that the complexity of both `sum` and `increase` depend on the function $g$.
 There are lots of ways to choose the function $g$, as long as $0 \le g(i) \le i$ for all $i$.
 For instance the function $g(i) = i$ works, which results just in $T = A$, and therefore summation queries are slow.
 We can also take the function $g(i) = 0$.
-This will correspond to prefix sum arrays, which means that finding the sum of the range $[0; i]$ will only take constant time, but updates are slow.
+This will correspond to prefix sum arrays, which means that finding the sum of the range $[0, i]$ will only take constant time, but updates are slow.
 The clever part of the Fenwick algorithm is, that there it uses a special definition of the function $g$ that can handle both operations in $O(\log N)$ time.
 
 ### Definition of $g(i)$
@@ -121,7 +121,7 @@ The nodes of the tree show the ranges they cover.
 
 Here we present an implementation of the Fenwick tree for sum queries and single updates.
 
-The normal Fenwick tree can only answer sum queries of the type $[0; r]$ using `sum(int r)`, however we can also answer other queries of the type $[l; r]$ by computing two sums $[0; r]$ and $[0; l-1]$ and subtract them.
+The normal Fenwick tree can only answer sum queries of the type $[0, r]$ using `sum(int r)`, however we can also answer other queries of the type $[l, r]$ by computing two sums $[0, r]$ and $[0, l-1]$ and subtract them.
 This is handled in the `sum(int l, int r)` method.
 
 Also this implementation supports two constructors.
@@ -160,9 +160,9 @@ struct FenwickTree {
 };
 ```
 
-### Finding minimum of $[0; r]$ in one-dimensional array
+### Finding minimum of $[0, r]$ in one-dimensional array
 
-It is obvious that there is no easy way of finding minimum of range $[l; r]$ using Fenwick tree, as Fenwick tree can only answer queries of type $[0; r]$.
+It is obvious that there is no easy way of finding minimum of range $[l, r]$ using Fenwick tree, as Fenwick tree can only answer queries of type $[0, r]$.
 Additionally, each time a value is `update`'d, the new value has to be smaller than the current value (because the $min$ function is not reversible).
 These, of course, are significant limitations.
 
@@ -317,13 +317,13 @@ This is just the ordinary Fenwick tree as explained above.
 Using simple tricks we can also do the reverse operations: increasing ranges and querying for single values.
 
 Let the Fenwick tree be initialized with zeros.
-Suppose that we want to increment the interval $[l; r]$ by $x$.
+Suppose that we want to increment the interval $[l, r]$ by $x$.
 We make two point update operations on Fenwick tree which are `add(l, x)` and `add(r+1, -x)`.
 
 If we want to get the value of $A[i]$, we just need to take the prefix sum using the ordinary range sum method.
 To see why this is true, we can just focus on the previous increment operation again.
 If $i < l$, then the two update operations have no effect on the query and we get the sum $0$.
-If $i \in [l; r]$, then we get the answer $x$ because of the first update operation.
+If $i \in [l, r]$, then we get the answer $x$ because of the first update operation.
 And if $i > r$, then the second update operation will cancel the effect of first one.
 
 The following implementation uses one-based indexing.
@@ -353,7 +353,7 @@ Note: of course it is also possible to increase a single point $A[i]$ with `rang
 
 To support both range updates and range queries we will use two BITs namely $B_1[]$ and $B_2[]$, initialized with zeros.
 
-Suppose that we want to increment the interval $[l; r]$ by the value $x$.
+Suppose that we want to increment the interval $[l, r]$ by the value $x$.
 Similarly as in the previous method, we perform two point updates on $B_1$: `add(B1, l, x)` and `add(B1, r+1, -x)`.
 And we also update $B_2$. The details will be explained later.
 
@@ -366,7 +366,7 @@ def range_add(l, r, x):
 ```
 After the range update $(l, r, x)$ the range sum query should return the following values:
 $$
-sum[0; i]=
+sum[0, i]=
 \begin{cases}
 0 & i < l \\\\
 x \cdot (i-(l-1)) & l \le i \le r \\\\
@@ -375,9 +375,9 @@ x \cdot (r-l+1) & i > r \\\\
 $$
 
 We can write the range sum as difference of two terms, where we use $B_1$ for first term and $B_2$ for second term.
-The difference of the queries will give us prefix sum over $[0; i]$.
+The difference of the queries will give us prefix sum over $[0, i]$.
 $$\begin{align}
-sum[0; i] &= sum(B_1, i) \cdot i - sum(B_2, i) \\\\
+sum[0, i] &= sum(B_1, i) \cdot i - sum(B_2, i) \\\\
 &= \begin{cases}
 0 \cdot i - 0 & i < l\\\\
 x \cdot i - x \cdot (l-1) & l \le i \le r \\\\
 
@@ -227,9 +227,9 @@ The memory consumption is limited by $4n$, even though a Segment Tree of an arra
 However it can be reduced. 
 We renumber the vertices of the tree in the order of an Euler tour traversal (pre-order traversal), and we write all these vertices next to each other.
 
-Lets look at a vertex at index $v$, and let him be responsible for the segment $[l; r]$, and let $mid = \dfrac{l + r}{2}$.
+Lets look at a vertex at index $v$, and let him be responsible for the segment $[l, r]$, and let $mid = \dfrac{l + r}{2}$.
 It is obvious that the left child will have the index $v + 1$.
-The left child is responsible for the segment $[l; mid]$, i.e. in total there will be $2 * (mid - l + 1) - 1$ vertices in the left child's subtree.
+The left child is responsible for the segment $[l, mid]$, i.e. in total there will be $2 * (mid - l + 1) - 1$ vertices in the left child's subtree.
 Thus we can compute the index of the right child of $v$. The index will be $v + 2 * (mid - l + 1)$.
 By this numbering we achieve a reduction of the necessary memory to $2n$.
 
 
@@ -27,17 +27,17 @@ Thus, for each block $k$, we know the sum of elements on it $b[k]$:
 
 $$ b[k] = \sum\limits_{i=k\cdot s}^{\min {(n-1,(k+1)\cdot s - 1})} a[i] $$
 
-So, we have calculated the values of $b[k]$ (this required $O(n)$ operations). How can they help us to answer each query $[l; r]$ ?
-Notice that if the interval $[l; r]$ is long enough, it will contain several whole blocks, and for those blocks we can find the sum of elements in them in a single operation. As a result, the interval $[l; r]$ will contain parts of only two blocks, and we'll have to calculate the sum of elements in these parts trivially.
+So, we have calculated the values of $b[k]$ (this required $O(n)$ operations). How can they help us to answer each query $[l, r]$ ?
+Notice that if the interval $[l, r]$ is long enough, it will contain several whole blocks, and for those blocks we can find the sum of elements in them in a single operation. As a result, the interval $[l, r]$ will contain parts of only two blocks, and we'll have to calculate the sum of elements in these parts trivially.
 
-Thus, in order to calculate the sum of elements on the interval $[l; r]$ we only need to sum the elements of the two "tails":
+Thus, in order to calculate the sum of elements on the interval $[l, r]$ we only need to sum the elements of the two "tails":
 $[l\dots (k + 1)\cdot s-1]$ and $[p\cdot s\dots r]$ , and sum the values $b[i]$ in all the blocks from $k + 1$ to $p-1$:
 
 $$ \sum\limits\_{i=l}^r a[i] = \sum\limits\_{i=l}^{(k+1) \cdot s-1} a[i] + \sum\limits\_{i=k+1}^{p-1} b[i] + \sum\limits\_{i=p\cdot s}^r a[i] $$
 
 _Note: When $k = p$, i.e. $l$ and $r$ belong to the same block, the formula can't be applied, and the sum should be calculated trivially._
 
-This approach allows us to significantly reduce the number of operations. Indeed, the size of each "tail" does not exceed the block length $s$, and the number of blocks in the sum does not exceed $s$. Since we have chosen $s \approx \sqrt n$, the total number of operations required to find the sum of elements on the interval $[l; r]$ is $O(\sqrt n)$.
+This approach allows us to significantly reduce the number of operations. Indeed, the size of each "tail" does not exceed the block length $s$, and the number of blocks in the sum does not exceed $s$. Since we have chosen $s \approx \sqrt n$, the total number of operations required to find the sum of elements on the interval $[l, r]$ is $O(\sqrt n)$.
 
 ### Implementation
 
@@ -61,7 +61,7 @@ for (;;) {
     int sum = 0;
     for (int i=l; i<=r; )
         if (i % len == 0 && i + len - 1 <= r) {
-            // if the whole block starting at i belongs to [l; r]
+            // if the whole block starting at i belongs to [l, r]
             sum += b[i / len];
             i += len;
         }
@@ -102,7 +102,7 @@ Sqrt decomposition can be applied in a similar way to a whole class of other pro
 
 Another class of problems appears when we need to **update array elements on intervals**: increment existing elements or replace them with a given value.
 
-For example, let's say we can do two types of operations on an array: add a given value $\delta$ to all array elements on interval $[l; r]$ or query the value of element $a[i]$. Let's store the value which has to be added to all elements of block $k$ in $b[k]$ (initially all $b[k] = 0$). During each "add" operation we need to add $\delta$ to $b[k]$ for all blocks which belong to interval $[l; r]$ and to add $\delta$ to $a[i]$ for all elements which belong to the "tails" of the interval. The answer a query $i$ is simply $a[i] + b[i/s]$. This way "add" operation has $O(\sqrt{n})$ complexity, and answering a query has $O(1)$ complexity.
+For example, let's say we can do two types of operations on an array: add a given value $\delta$ to all array elements on interval $[l, r]$ or query the value of element $a[i]$. Let's store the value which has to be added to all elements of block $k$ in $b[k]$ (initially all $b[k] = 0$). During each "add" operation we need to add $\delta$ to $b[k]$ for all blocks which belong to interval $[l, r]$ and to add $\delta$ to $a[i]$ for all elements which belong to the "tails" of the interval. The answer a query $i$ is simply $a[i] + b[i/s]$. This way "add" operation has $O(\sqrt{n})$ complexity, and answering a query has $O(1)$ complexity.
 
 Finally, those two classes of problems can be combined if the task requires doing **both** element updates on an interval and queries on an interval. Both operations can be done with $O(\sqrt{n})$ complexity. This will require two block arrays $b$ and $c$: one to keep track of element updates and another to keep track of answers to the query.
 
 
@@ -83,7 +83,7 @@ int get(ftype x) {
 
 Assume you're given a set of functions such that each two can intersect at most once. Let's keep in each vertex of a segment tree some function in such way, that if we go from root to the leaf it will be guaranteed that one of the functions we met on the path will be the one giving the minimum value in that leaf. Let's see how to construct it.
 
-Assume we're in some vertex corresponding to half-segment $[l;r)$ and the function $f_{old}$ is kept there and we add the function $f_{new}$. Then the intersection point will be either in $[l;m)$ or in $[m;r)$ where $m=\left\lfloor\tfrac{l+r}{2}\right\rfloor$. We can efficiently find that out by comparing the values of the functions in points $l$ and $m$. If the dominating function changes, then it is in $[l;m)$ otherwise it is in $[m;r)$. Now for the half of the segment with no intersection we will pick the lower function and write it in the current vertex. You can see that it will always be the one which is lower in point $m$. After that we recursively go to the other half of the segment with the function which was the upper one. As you can see this will keep correctness on the first half of segment and in the other one correctness will be maintained during the recursive call. Thus we can add functions and check the minimum value in the point in $O(\log [C\varepsilon^{-1}])$.
+Assume we're in some vertex corresponding to half-segment $[l,r)$ and the function $f_{old}$ is kept there and we add the function $f_{new}$. Then the intersection point will be either in $[l;m)$ or in $[m;r)$ where $m=\left\lfloor\tfrac{l+r}{2}\right\rfloor$. We can efficiently find that out by comparing the values of the functions in points $l$ and $m$. If the dominating function changes, then it is in $[l;m)$ otherwise it is in $[m;r)$. Now for the half of the segment with no intersection we will pick the lower function and write it in the current vertex. You can see that it will always be the one which is lower in point $m$. After that we recursively go to the other half of the segment with the function which was the upper one. As you can see this will keep correctness on the first half of segment and in the other one correctness will be maintained during the recursive call. Thus we can add functions and check the minimum value in the point in $O(\log [C\varepsilon^{-1}])$.
 
 Here is the illustration of what is going on in the vertex when we add new function:
 
 
@@ -10,7 +10,7 @@ Let there be a tree $G$ of $n$ vertices, with an arbitrary root.
 
 The essence of this tree decomposition is to **split the tree into several paths** so that we can reach the root vertex from any $v$ by traversing at most $\log n$ paths. In addition, none of these paths should intersect with another.
 
-It is clear that if we find such a decomposition for any tree, it will allow us to reduce certain single queries of the form *“calculate something on the path from $a$ to $b$”* to several queries of the type *”calculate something on the segment $[l;r]$ of the $k^{th}$ path”*.
+It is clear that if we find such a decomposition for any tree, it will allow us to reduce certain single queries of the form *“calculate something on the path from $a$ to $b$”* to several queries of the type *”calculate something on the segment $[l, r]$ of the $k^{th}$ path”*.
 
 
 ### Construction algorithm