> ## Documentation Index
> Fetch the complete documentation index at: https://docs.hnuicpc.tech/llms.txt
> Use this file to discover all available pages before exploring further.
# Static range queries
> Tutorial for Sheet 7 — Prefix sums, difference arrays, and other range query techniques.
## Prefix Sum
Allows $O(1)$ range sum queries after $O(n)$ preprocessing.
```cpp theme={null}
// 1-based indexing is often easier
for (int i = 1; i <= n; i++) {
pref[i] = pref[i-1] + a[i];
}
// Sum of range [L, R]
long long sum = pref[R] - pref[L-1];
```
## 2D Prefix Sum
Sum of a rectangle from $(x1, y1)$ to $(x2, y2)$.
```cpp theme={null}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
pref[i][j] = a[i][j] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
}
}
// Query
long long sum = pref[x2][y2] - pref[x1-1][y2] - pref[x2][y1-1] + pref[x1-1][y1-1];
```
## Difference Array
Used for range updates (add $V$ to $[L, R]$) in $O(1)$. After all updates, calculate prefix sums to get the final values.
```cpp theme={null}
diff[L] += V;
diff[R+1] -= V;
// Recover original array
for (int i = 1; i <= n; i++) {
val[i] = val[i-1] + diff[i];
}
```
## Practice
Practice problems for this tutorial.