📐 2D Prefix Sum — Build & Rectangle Query
USACO C++ Book · Interactive Visualizer
📐 2D Prefix Sum — Build & Query Demo
2D Prefix Sum
O(RC) build / O(1) query
Step 0/21
📊 Visualization
🗂 Data Structures
Current Computation
P[][] Grid
Build:
O(R×C)
Query:
O(1)
per rectangle
💻 Code
Hint
Click
Next Step ▶
to build the 2D prefix sum array, then see the O(1) rectangle query using inclusion-exclusion.
◀ Prev
Next Step ▶
↺ Reset
0/21
Keyboard:
→
Next
←
Prev
R
Reset