Intro

This page introduces to the algorithms and data structures section.

Prefix sum

Prefix sum for sequence \(x_1, x_2, \ldots, x_n\) is a sequence \(y_1, y_2, \ldots, y_{n+1}\).

Where: \(y_i = \sum^{i-1}_{j=1} x_j, i = \overline{1, n+1}\)

From this the statement \(y_i = y_{i-1} + x_{i-1}\) will be correct.

The following cell shows the prefix sum idea in table format.

\(i\)	\(1\)	\(2\)	\(3\)	\(4\)	\(\ldots\)	\(n\)	\(n+1\)
\(x_i\)	\(x_1\)	\(x_2\)	\(x_3\)	\(x_4\)	\(\ldots\)	\(x_n\)
\(y_i\)	\(0\)	\(x_1\)	\(x_1 + x_2 = y_2 + x_2\)	\(x_1 + x_2 + x_3 = y_3 + x_3\)	\(\ldots\)	\(\sum^{n-1}_{j=1} x_j = y_{n-1} + x_{n-1}\)	\(\sum^{n}_{j=1} x_j = y_n + x_n\)

The prefix sum can be computed from the original sequence in \(O(n)\) time.

---

The following cell illustrates the implementation of the counting prefix sum.

def count_prefix_sum(seq: list[float | int]):
    ans = [0]
    for x in seq:
        ans.append(ans[-1] + x)
    return ans

count_prefix_sum([1, 2, 3, 4])

[0, 1, 3, 6, 10]

Sum of subset

Calculate the sum of the elements of the sequence from the \(a\)-th to the \(b\)-th position using formula:

\[\sum_{i=a}^b x_i = y_{b + 1} - y_a\]

If you have the prefix sum precomputed, you can compute the sum of a subset with complexity of \(O(1)\).

To prove this just describe the difference \(y_{b+1} - y_a\):

\[y_{b+1} - y_a = \sum_{i=1}^{b} x_i - \sum_{i=1}^{a-1} x_i = \sum_{i=a}^b x_i\]

Transformation

The prefix sum is a really useful data structure. To fulfill its potential, you must apply a transformation to the original set - \(f(x)\).

For example, if the task requires counting the number of elements \(x_i > k\) for \(i=\overline{a,b}\), then cae apply the following transformation:

\[\begin{split} f(x_i) = \begin{cases} 1, x_i > k; \\ 0, x_i \leq k. \end{cases} \end{split}\]

Count and use the prefix sum for the transformed sequence.

Two pointers

In the two-pointers technique uses two indexes (pointers) that access the elements of an array during the same iteration.

Example of task:

There is a sorted array of numbers. You need to count all pairs of the elements, \((a,b)\), for which the statemene \(a - b > D\) is true.

---

The following cell shows the approach to solve this using the two pointers technique.

def find_pair(lst: list[int], D: int):
    l, r = 0, 1
    count = 0
    lst_len = len(lst)
    while True:
        if r >= lst_len:
            break
        if (lst[r] - lst[l] > D) and (l < r):
            count += (lst_len - r)
            l += 1
        else:
            r += 1
    return count

The idea is to compare items under indices \(l\) and \(r\).

If \(x_r - x_l > D\), then count all pairs \((l,r), (l, r+1), \ldots (l, N)\), as garanteeed that \(x_{r+t} - x_l > D\) due to \(x_{r+t} > x_{r}\). then move \(l\) pointer.

Otherwise just move \(r\).

It ensures \(O(2N)\) compexity of the algorithm.

The following cell shows the result of the applying the algorithm.

lst = [1, 2, 3, 4, 5, 6]
find_pair(lst, 2)

3