<h2>1D Prefix Sum</h2>

<h3>Definition</h3>

Given an array $A[n]$, let's define an array $S$ where $S[i]$ as the sum of the first $i$ elements of $A$:
$$S[0] = 0, \\ S[i] = \sum_{k=0}^{i}a[k] = S[i-1] + A[i]$$

S[0] = 0;
for (int i = 1; i <= n; i++) S[i] = S[i - 1] + A[i];

<h3>Usage</h3>

**Prefix Sum is used to calculate the sum of the subsegment $A[l..r]$ in $O(1)$ with $O(n)$ preprocessing:**

$$A[l] + A[l + 1] + ... + A[r] = S[r] - S[l - 1]$$

long long get(int l, int r) {
    return S[r] - S[l - 1];
}

<h3>Exercises</h3>

1. Write a function to calculate the array $S$.
3. Find a non-empty subsegment $A[1..n], n \leq 100000$ with largest sum.
2. Find the longest subsegment of $A[1..n], n \leq 100000$ whose sum equals to $x$.
3. Find the longest subsegment of $A[1..n], n \leq 100000$ whose mean equals to $x$.

<h2>2D Prefix Sum</h2>

<h3>Definition</h3>

$S[i][j]$ is the sum of the subrectangle of the board whose upper-left corner is $(1, 1)$ and bottom right corner is $(i, j)$.

$$S[i][j] = \sum_{t_i=1}^{i}{\sum_{t_j=1}^{j}{A[t_i][t_j]}},$$ $$S[i][j] = A[i][j] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1]$$

for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        S[i][j] = A[i][j] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
    }
}

<h3>Usage</h3>

2D Prefix Sum is used to calculate the sum of the rectangle whose upper-left and bottom-right corner are $(r1, c1)$ and $(r2, c2)$, respectively.

$$ sum(r1, c1, r2, c2) = \sum_{i=r1}^{r2}{\sum_{j=c1}^{c2}{A[i][j]}} = S[r2][c2] - S[r1 - 1][c2] - S[r2][c1 - 1] + S[r1 - 1][c1 - 1]$$

long long sum(int r1, int c1, int r2, int c2) {
    return S[r2][c2] - S[r1 - 1][c2] - S[r2][c1 - 1] + S[r1 - 1][c1 - 1];
}

<h3>Exercises</h3>

1. Given a board of size $m*n (m, n \leq 300)$, find the largest rectangle whose accumulative sum is less then $x$ (Binary Search).

<h3>References</h3>

* https://vnoi.info/wiki/algo/data-structures/prefix-sum-and-difference-array.md
* https://usaco.guide/silver/prefix-sums?lang=cpp