1. Prefix Sum Technique

1.1 One-Dimensional Prefix Sum

The prefix sum algorithm is an optimization technique used to calculate the sum of elements within a specific range $[L, R]$ in $O(1)$ time after an $O(N)$ preprocessing step. In a naive approach, calculating range sums repeatedly would result in $O(N \times M)$ complexity for $M$ queries; prefix sums reduce this to $O(N + M)$.

Given an array data, the prefix sum array S is defined such that S[i] stores the sum of the first $i$ elements. The sum of the range $[L, R]$ (1-indexed) is calculated as: S[R] - S[L-1].

#include <iostream>
#include <vector>

int main() {
    int n, queries;
    if (scanf("%d %d", &n, &queries) != 2) return 0;

    std::vector<long long> prefixSum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int val;
        scanf("%d", &val);
        prefixSum[i] = prefixSum[i - 1] + val;
    }

    while (queries--) {
        int left, right;
        scanf("%d %d", &left, &right);
        printf("%lld\n", prefixSum[right] - prefixSum[left - 1]);
    }
    return 0;
}

1.2 Two-Dimensional Prefix Sum

In a 2D matrix, a prefix sum S[i][j] represents the sum of all elements in the rectangle from (1, 1) to (i, j). To construct the 2D prefix sum matrix, we use the principle of inclusion-exclusion:

S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + matrix[i][j]

To query the sum of a submatrix with top-left corner (x1, y1) and bottom-right corner (x2, y2):

Result = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 1005;
long long s[MAX][MAX];

int main() {
    int rows, cols, q;
    scanf("%d %d %d", &rows, &cols, &q);
    
    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            int val;
            scanf("%d", &val);
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + val;
        }
    }

    while (q--) {
        int r1, c1, r2, c2;
        scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
        printf("%lld\n", s[r2][c2] - s[r1-1][c2] - s[r2][c1-1] + s[r1-1][c1-1]);
    }
    return 0;
}

2. Difference Array Technique

2.1 One-Dimensional Difference Array

A difference array is used for frequent range updates. If we need to add a value $C$ to every element in the range $[L, R]$, updating each element individually takes $O(N)$. A difference array D allows us to perform this udpate in $O(1)$.

Let A be the original array. The difference array D is defined as D[i] = A[i] - A[i-1]. Adding $C$ to A[L...R] is equivalent to:

• D[L] += C
• D[R+1] -= C

The updated original array can be recovered by calculating the prefix sum of D.

#include <iostream>
#include <vector>

void modify(std::vector<int>& diff, int l, int r, int val) {
    diff[l] += val;
    if (r + 1 < diff.size()) diff[r + 1] -= val;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    std::vector<int> a(n + 1), d(n + 2, 0);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        modify(d, i, i, a[i]);
    }
    while (m--) {
        int l, r, c;
        scanf("%d %d %d", &l, &r, &c);
        modify(d, l, r, c);
    }
    for (int i = 1; i <= n; ++i) {
        d[i] += d[i - 1];
        printf("%d%c", d[i], i == n ? '\n' : ' ');
    }
    return 0;
}

2.2 Two-Dimensional Difference Array

To update a submatrix from (x1, y1) to (x2, y2) with a value C in a 2D matrix, we apply the following modifications to the difference matrix B:

1. B[x1][y1] += C
2. B[x2+1][y1] -= C
3. B[x1][y2+1] -= C
4. B[x2+1][y2+1] += C

#include <iostream>

const int N = 1010;
int diff_matrix[N][N];

void add_submatrix(int x1, int y1, int x2, int y2, int c) {
    diff_matrix[x1][y1] += c;
    diff_matrix[x2+1][y1] -= c;
    diff_matrix[x1][y2+1] -= c;
    diff_matrix[x2+1][y2+1] += c;
}

int main() {
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int val;
            scanf("%d", &val);
            add_submatrix(i, j, i, j, val);
        }
    }
    while (q--) {
        int x1, y1, x2, y2, c;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
        add_submatrix(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            diff_matrix[i][j] += diff_matrix[i-1][j] + diff_matrix[i][j-1] - diff_matrix[i-1][j-1];
            printf("%d ", diff_matrix[i][j]);
        }
        printf("\n");
    }
    return 0;
}

3. Algorithmic Applications

3.1 Array Equalization (IncDec Sequence)

Given an array, what is the minimum number of operations (incrementing or decrementing a range) required to make all elements equal? And how many different sequences can be achieved with this minimum number of operations?

By transforming the array into a difference array $B$, the goal is to make $B[2...n]$ all zeros. Each range operation modifies two points in the difference array: $B[i]$ and $B[j]$. We aim to pair positive values in $B$ with negative values to eliminate them efficiently.

• Let $P$ be the sum of all positive values in $B[2...n]$.
• Let $Q$ be the absolute sum of all negative values in $B[2...n]$.
• Minimum operations: $\max(P, Q)$.
• Possible resulting values: $|P - Q| + 1$.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<long long> arr(n + 1);
    for (int i = 1; i <= n; ++i) scanf("%lld", &arr[i]);

    long long pos_sum = 0, neg_sum = 0;
    for (int i = 2; i <= n; ++i) {
        long long diff = arr[i] - arr[i-1];
        if (diff > 0) pos_sum += diff;
        else neg_sum -= diff;
    }

    printf("%lld\n", max(pos_sum, neg_sum));
    printf("%lld\n", abs(pos_sum - neg_sum) + 1);
    return 0;
}

3.2 Height Constraints (Tallest Cow)

Given $N$ cows and the height $H$ of tallest cow at index $P$, and $M$ pairs of cows $(A, B)$ that can see each other, find the maximum possible height for each cow. Two cows can see each other if all cows between them are strictly shorter.

To maximize heights, we assume every cow starts at height $H$. For each unique pair $(A, B)$, we decrement the height of every cow in the open interval $(min(A,B), max(A,B))$ by 1 using a difference array.

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main() {
    int n, p, h, m;
    scanf("%d %d %d %d", &n, &p, &h, &m);
    vector<int> diff(n + 2, 0);
    set<pair<int, int>> seen;

    diff[1] = h; 
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        if (a > b) swap(a, b);
        if (seen.count({a, b})) continue;
        seen.insert({a, b});
        
        // Decrease interval (a, b) by 1
        if (a + 1 <= b - 1) {
            diff[a + 1] -= 1;
            diff[b] += 1;
        }
    }

    int current_h = 0;
    for (int i = 1; i <= n; ++i) {
        current_h += diff[i];
        printf("%d\n", current_h);
    }
    return 0;
}