Prefix Sums, Difference Arrays, and Range Queries

1D/2D prefix sums, prefix XOR, prefix frequency, suffix arrays for aggregate values, difference arrays, range updates, coordinate compression, and offline query processing.

Topics

1D/2D prefix sums, prefix XOR, prefix frequency, suffix arrays for aggregate values, difference arrays, range updates, coordinate compression, and offline query processing.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

The hash-map trick counts subarrays ending at each position whose sum is k: a subarray (i, j] sums to k exactly when prefix[j] − prefix[i] = k. It works with negative numbers, unlike the sliding window.

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<vector<int>> g = {{3, 0, 1, 4}, {5, 6, 3, 2}, {1, 2, 0, 1}, {4, 1, 0, 1}};
    int R = 4, C = 4;
    vector<vector<long long>> P(R + 1, vector<long long>(C + 1, 0));
    for (int r = 0; r < R; ++r) for (int c = 0; c < C; ++c)
        P[r + 1][c + 1] = g[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];          // inclusion-exclusion
    auto rect = [&](int r1, int c1, int r2, int c2) {                            // inclusive corners
        return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
    };
    cout << "sum of rows 1..2, cols 1..2 = 6+3+2+0 = " << rect(1, 1, 2, 2) << '\n';

    // subarrays with sum k: count prefix sums seen so far
    vector<int> a = {1, 2, 3, -3, 1, 2};
    int k = 3; long long count = 0, s = 0;
    unordered_map<long long, int> seen{{0, 1}};
    for (int x : a) { s += x; if (seen.count(s - k)) count += seen[s - k]; ++seen[s]; }
    cout << "subarrays of {1,2,3,-3,1,2} with sum 3: " << count << '\n';

    // coordinate compression: map large values to ranks 0..m-1
    vector<long long> raw = {1000000000, -5, 42, 42, 7};
    vector<long long> vals = raw;
    sort(vals.begi
…

sum of rows 1..2, cols 1..2 = 6+3+2+0 = 11
subarrays of {1,2,3,-3,1,2} with sum 3: 6
compressed: 3 0 2 2 1

Advanced range queries

Sparse table for idempotent static queries, Fenwick tree, segment tree, lazy propagation, merge-sort tree, persistent segment tree, wavelet tree, and Mo's algorithm.

Key distinction

Prefix sums are ideal for static range sums; Fenwick/segment trees support updates; sparse tables typically support static idempotent operations. Choose by query/update requirements.

Static range sum rebuild O(n) Static range min/max sparse table (Module 38) Range sum with point updates Fenwick tree (Module 36) Any associative op, range updates segment tree + lazy (Module 37) Many offline queries, add/remove cheap Mo's algorithm (Module 39) O((n + q)√n) total

Quiz

? How many subarrays of {1,2,3,−3,1,2} sum to 3, according to the run?
+ 6 :: The −3 lets several longer subarrays also sum to 3 (for example {1,2,3,−3} and {3,−3,1,2}); the prefix-sum map counts them all.
- 2 :: Only the obvious {1,2} and {3}; the negative value creates more.
- 4 :: The run printed 6.
- 3 :: No.

? Which structure answers static range-minimum queries in O(1)?
+ Sparse table :: min is idempotent, so two overlapping blocks cover any range.
- Prefix sums :: Min cannot be subtracted.
- Fenwick tree :: O(log n) and needs an invertible operation for ranges.
- Hash map :: No.

? Why does the 2-D prefix formula subtract P[r][c]?
+ That corner region was added twice (once in each strip). :: Inclusion–exclusion.
- To handle negative numbers. :: Unrelated.
- It is the base case. :: It is part of every step.
- To shift indices. :: No.