Prefix Sum Matrix
AlgorithmsMediumPrecompute subgrid sums for O(1) range queries and visualize regions.
Alt+Shift+6
Configuration Panel
Subgrid Range Query Bounds (1-based index)
Complexity Indices
Time ComplexityO(R * C) build, O(1) query
Auxiliary SpaceO(R * C) prefix grid
Conceptual Overview
2D Prefix Sum precalculates region totals such that any subgrid sum query is evaluated in O(1) constant time, avoiding double loops.
Source: CP-Algorithms reference guide