If <span class="arithmatex">$p$</span> is smaller than <span class="arithmatex">$\sqrt{n}$</span>, the repetition will likely start in <span class="arithmatex">$O(\sqrt[4]{n})$</span>.</p>

<p>Here is a visualization of such a sequence <span class="arithmatex">$\{x_i \bmod p\}$</span> with <span class="arithmatex">$n = 2206637$</span>, <span class="arithmatex">$p = 317$</span>, <span class="arithmatex">$x_0 = 2$</span> and <span class="arithmatex">$f(x) = x^2 + 1$</span>.

From the form of the sequence you can see very clearly why the algorithm is called Pollard's <span class="arithmatex">$\rho$</span> algorithm.</p>

<p>Yet, there is still an open question.

How can we exploit the properties of the sequence <span class="arithmatex">$\{x_i \bmod p\}$</span> to our advantage without even knowing the number <span class="arithmatex">$p$</span> itself?</p>

<p>It's actually quite easy.

The next unmarked number is 5, which is the next prime number, and we mark all proper multiples of it.

And we continue this procedure until we have processed all numbers in the row.</p>

<p>In the following image you can see a visualization of the algorithm for computing all prime numbers in the range <span class="arithmatex">$[1; 16]$</span>. It can be seen, that quite often we mark numbers as composite multiple times.</p>

<p>The idea behind is this:

A number is prime, if none of the smaller prime numbers divides it.

Since we iterate over the prime numbers in order, we already marked all numbers, which are divisible by at least one of the prime numbers, as divisible.

<p>where <span class="arithmatex">$|$</span> is the bitwise OR operator.</p>

<p>The following image shows a possible interpretation of the Fenwick tree as tree.

The nodes of the tree show the ranges they cover.</p>

<h2 id="implementation">Implementation<a class="headerlink" href="#implementation" title="Permanent link">&para;</a></h2>

<h3 id="finding-sum-in-one-dimensional-array">Finding sum in one-dimensional array<a class="headerlink" href="#finding-sum-in-one-dimensional-array" title="Permanent link">&para;</a></h3>

<p>Here we present an implementation of the Fenwick tree for sum queries and single updates.</p>

<p>More specifically, treap is a data structure that stores pairs <span class="arithmatex">$(X, Y)$</span> in a binary tree in such a way that it is a binary search tree by <span class="arithmatex">$X$</span> and a binary heap by <span class="arithmatex">$Y$</span>.

If some node of the tree contains values <span class="arithmatex">$(X_0, Y_0)$</span>, all nodes in the left subtree have <span class="arithmatex">$X \leq X_0$</span>, all nodes in the right subtree have <span class="arithmatex">$X_0 \leq X$</span>, and all nodes in both left and right subtrees have <span class="arithmatex">$Y \leq Y_0$</span>.</p>

<p>A treap is also often referred to as a "cartesian tree", as it is easy to embed it in a Cartesian plane:</p>

<img src="https://upload.wikimedia.org/wikipedia/commons/e/e4/Treap.svg" width="350px"/>

<p>Treaps have been proposed by Raimund Siedel and Cecilia Aragon in 1989.</p>

<h2 id="advantages-of-such-data-organisation">Advantages of such data organisation<a class="headerlink" href="#advantages-of-such-data-organisation" title="Permanent link">&para;</a></h2>

<p>In such implementation, <span class="arithmatex">$X$</span> values are the keys (and at same time the values stored in the treap), and <span class="arithmatex">$Y$</span> values are called <strong>priorities</strong>. Without priorities, the treap would be a regular binary search tree by <span class="arithmatex">$X$</span>, and one set of <span class="arithmatex">$X$</span> values could correspond to a lot of different trees, some of them degenerate (for example, in the form of a linked list), and therefore extremely slow (the main operations would have <span class="arithmatex">$O(N)$</span> complexity).</p>

<p>In terms of implementation, each node contains <span class="arithmatex">$X$</span>, <span class="arithmatex">$Y$</span> and pointers to the left (<span class="arithmatex">$L$</span>) and right (<span class="arithmatex">$R$</span>) children.</p>

<p>We will implement all the required operations using just two auxiliary operations: Split and Merge.</p>

<h3 id="split">Split<a class="headerlink" href="#split" title="Permanent link">&para;</a></h3>

<img src="https://upload.wikimedia.org/wikipedia/commons/6/69/Treap_split.svg" width="450px"/>

<p><strong>Split (<span class="arithmatex">$T$</span>, <span class="arithmatex">$X$</span>)</strong> separates tree <span class="arithmatex">$T$</span> in 2 subtrees <span class="arithmatex">$L$</span> and <span class="arithmatex">$R$</span> trees (which are the return values of split) so that <span class="arithmatex">$L$</span> contains all elements with key <span class="arithmatex">$X_L \le X$</span>, and <span class="arithmatex">$R$</span> contains all elements with key <span class="arithmatex">$X_R &gt; X$</span>. This operation has <span class="arithmatex">$O (\log N)$</span> complexity and is implemented using a clean recursion:</p>

<li>If the value of the root node (R) is <span class="arithmatex">$\le X$</span>, then <code>L</code> would at least consist of <code>R-&gt;L</code> and <code>R</code>. We then call split on <code>R-&gt;R</code>, and note its split result as <code>L'</code> and <code>R'</code>. Finally, <code>L</code> would also contain <code>L'</code>, whereas <code>R = R'</code>.</li>

<li>create the final result by reusing the recursive split call.</li>

<h3 id="merge">Merge<a class="headerlink" href="#merge" title="Permanent link">&para;</a></h3>

<img src="https://upload.wikimedia.org/wikipedia/commons/a/a8/Treap_merge.svg" width="500px"/>

<p><strong>Merge (<span class="arithmatex">$T_1$</span>, <span class="arithmatex">$T_2$</span>)</strong> combines two subtrees <span class="arithmatex">$T_1$</span> and <span class="arithmatex">$T_2$</span> and returns the new tree. This operation also has <span class="arithmatex">$O (\log N)$</span> complexity. It works under the assumption that <span class="arithmatex">$T_1$</span> and <span class="arithmatex">$T_2$</span> are ordered (all keys <span class="arithmatex">$X$</span> in <span class="arithmatex">$T_1$</span> are smaller than keys in <span class="arithmatex">$T_2$</span>). Thus, we need to combine these trees without violating the order of priorities <span class="arithmatex">$Y$</span>. To do this, we choose as the root the tree which has higher priority <span class="arithmatex">$Y$</span> in the root node, and recursively call Merge for the other tree and the corresponding subtree of the selected root node.</p>

<h3 id="insert">Insert<a class="headerlink" href="#insert" title="Permanent link">&para;</a></h3>

<img src="https://upload.wikimedia.org/wikipedia/commons/3/35/Treap_insert.svg" width="500px"/>

<p>Now implementation of <strong>Insert (<span class="arithmatex">$X$</span>, <span class="arithmatex">$Y$</span>)</strong> becomes obvious. First we descend in the tree (as in a regular binary search tree by X), and stop at the first node in which the priority value is less than <span class="arithmatex">$Y$</span>. We have found the place where we will insert the new element. Next, we call <strong>Split (T, X)</strong> on the subtree starting at the found node, and use returned subtrees <span class="arithmatex">$L$</span> and <span class="arithmatex">$R$</span> as left and right children of the new node.</p>

<p>Alternatively, insert can be done by splitting the initial treap on <span class="arithmatex">$X$</span> and doing <span class="arithmatex">$2$</span> merges with the new node (see the picture).</p>

<h3 id="erase">Erase<a class="headerlink" href="#erase" title="Permanent link">&para;</a></h3>

<img src="https://upload.wikimedia.org/wikipedia/commons/6/62/Treap_erase.svg" width="500px"/>

<p>Implementation of <strong>Erase (<span class="arithmatex">$X$</span>)</strong> is also clear. First we descend in the tree (as in a regular binary search tree by <span class="arithmatex">$X$</span>), looking for the element we want to delete. Once the node is found, we call <strong>Merge</strong> on it children and put the return value of the operation in the place of the element we're deleting.</p>

<p>Alternatively, we can factor out the subtree holding <span class="arithmatex">$X$</span> with <span class="arithmatex">$2$</span> split operations and merge the remaining treaps (see the picture).</p>

<h3 id="build">Build<a class="headerlink" href="#build" title="Permanent link">&para;</a></h3>