Two pointers are useful when performing operations on a range: two indices traverse the data simultaneously and exploit the range’s structure. The technique can often reduce $\mathcal{O}(n^2)$ time complexity to $\mathcal{O}(n)$.
Opposite-Direction Scan The left pointer starts at the beginning and continuously moves to the right, while the right pointer starts at the end and continuously moves to the left, until they meet and stop. This is generally used for problems involving sorted arrays or strings.
Read note →Prefix Sum A prefix sum array p is a data structure that helps answer range sum queries efficiently. Given an input array a of length $n$, its prefix sum array p (also of length $n$) is defined as: $$ p[i] = a[0] + a[1] + \dots + a[i] = \sum_{k=0}^{i} a[k] $$ This means $p[i]$ stores the cumulative sum of all elements from the start of the array up to and including index $i$. For example, if:
Read note →Difference Arrays For an array $a$, the difference array $\mathrm{diff}$ is defined as: $$ \mathrm{diff}[i] = a[i] - a[i - 1], \quad \text{where } a[0] = 0. $$ Computing the prefix sums of the difference array restores the original array: $$ \mathrm{diff}[1] + \mathrm{diff}[2] + \dots + \mathrm{diff}[i] = a[1] + (a[2] - a[1]) + \dots + (a[i] - a[i - 1]) = a[i]. $$ To perform range addition on the original array (adding $x$ to all elements in the interval $[l, r]$), the operations on the difference array are: $$ \mathrm{diff}[l] \mathrel{+}= x, \quad \mathrm{diff}[r + 1] \mathrel{-}= x. $$ Two-dimensional Difference Arrays $$ \mathrm{diff}_{i, j} = a_{i, j} - a_{i - 1, j} - a_{i, j - 1} + a_{i - 1, j - 1} $$ To perform range addition between $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$, do
Read note →