Algorithmic Techniques#
Prefix Sum#
Index \(i\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|---|---|---|---|---|---|---|---|
\(\texttt{arr}[i]\) |
1 |
6 |
4 |
2 |
5 |
3 |
- |
\(\texttt{prefixSum}[i]\) |
0 |
1 |
7 |
11 |
13 |
18 |
21 |
Prefix sum can be calculated in \(\mathcal{O}(n)\) by the below formula:
\[
\texttt{prefixSum}[i] = \texttt{prefixSum}[i - 1] + \texttt{arr}[i - 1]
\]
Now, the sum of the elements of \(\texttt{arr}\) from \(\textit{L}\) to \(\textit{R}\) can be computed using:
\[
\sum_{i=L}^{R} \texttt{arr}[i] = \sum_{i=0}^{R} \texttt{arr}[i] - \sum_{i=0}^{L-1} \texttt{arr}[i]
\]
Using the prefix sum array, the same can be
\[
\sum_{i=L}^{R} \texttt{arr}[i] = \texttt{prefixSum}[R+1] - \texttt{prefixSum}[L]
\]
Example should make it more clearer:
\[
\sum_{1=1}^{4} \texttt{arr}[i] = \sum_{i=0}^{4} \texttt{arr}[i] - \sum_{i=0}^{0} \texttt{arr}[i] \\
\sum_{n=1}^{4} \texttt{arr}[i] = (1 + 6 + 4 + 2 + 5) - (1) = 18 - 1 = 17.
\]
Using prefix sums:
\[
\texttt{prefixSum}[5] - \texttt{prefixSum}[1] = 18 - 1 = 17.
\]
Read more at: https://usaco.guide/silver/prefix-sums and https://labuladong.gitbook.io/algo-en/iii.-algorithmic-thinking/prefix_sum
Backtracking#
Types of problems
Decision - Search for a solution.
Optimization - Search for best solution.
Enumeration - Find all possible/feasible solutions.