Prefix Sum

In one sentence

Spend \(O(n)\) once to precompute running totals. After that, every "sum of a range" question is answered in \(O(1)\) with one subtraction.

1. What problem does it solve?

Example — 1807D · Odd Queries (1 · A, 4-Misc · A, rating 900)

You have an array \(a_1, \dots, a_n\) and \(q\) independent queries \(l, r, k\): if every element in \(a_l, \dots, a_r\) were replaced by \(k\), would the sum of the whole array be odd? Print YES or NO.

Limits: \(t \le 10^4\); \(n, q \le 2 \cdot 10^5\) (sums over all tests too).

Input          Output
2
5 5
2 2 1 3 2
2 3 3          YES
2 3 4          YES
1 5 5          YES
1 4 9          NO
2 4 3          YES
10 5
1 1 1 1 1 1 1 1 1 1
3 8 13         NO
2 5 10         NO
3 8 10         NO
1 10 2         NO
1 9 100        YES

After replacing, the new total is

\[ \text{new sum} = \underbrace{(a_1 + \dots + a_n)}_{\text{old total}} \;-\; \underbrace{(a_l + \dots + a_r)}_{\text{removed}} \;+\; \underbrace{k \cdot (r - l + 1)}_{\text{added}} . \]

The old total is computed once. The only hard part is the sum of \(a_l..a_r\), many times.

The naive way. For each query, loop from \(l\) to \(r\) and add. One query can cost \(n\) steps, so all queries cost up to \(n \cdot q = 4 \cdot 10^{10}\) steps. Far too slow.

The key observation. Every range is a long prefix with a short prefix cut off:

\[ \underbrace{a_l + \dots + a_r}_{\text{what we want}} \;=\; \underbrace{a_1 + \dots + a_r}_{\text{prefix up to } r} \;-\; \underbrace{a_1 + \dots + a_{l-1}}_{\text{prefix up to } l-1} \]

So if we already know the sum of every prefix, any range is one subtraction away.

2. The math

2.1 Definition

For a 1-indexed array \(a_1, \dots, a_n\), define

\[ \mathrm{pre}_i = a_1 + a_2 + \dots + a_i = \sum_{j=1}^{i} a_j, \qquad \mathrm{pre}_0 = 0 . \]

We never add the whole prefix from scratch. Each prefix is the previous prefix plus one element:

\[ \mathrm{pre}_i = \mathrm{pre}_{i-1} + a_i . \]

That is one pass over the array, \(O(n)\) in total.

Take \(a = [3, 1, 4, 1, 5, 9]\):

\(i\)	0	1	2	3	4	5	6
\(a_i\)	—	3	1	4	1	5	9
\(\mathrm{pre}_i\)	0	3	4	8	9	14	23

Read the last row left to right: \(0 \to 0+3 \to 3+1 \to 4+4 \to 8+1 \to 9+5 \to 14+9\).

2.2 The query formula

\[ \boxed{\;\sum_{i=l}^{r} a_i = \mathrm{pre}_r - \mathrm{pre}_{l-1}\;} \]

Proof: write both prefixes out and cancel.

\[ \begin{aligned} \mathrm{pre}_r - \mathrm{pre}_{l-1} &= (a_1 + \dots + a_{l-1} + a_l + \dots + a_r) - (a_1 + \dots + a_{l-1}) \\ &= a_l + \dots + a_r . \end{aligned} \]

Here is the query \(l = 2,\ r = 5\) on the array above:

Why \(\mathrm{pre}_{l-1}\) and not \(\mathrm{pre}_l\)?

\(\mathrm{pre}_l\) includes \(a_l\), and \(a_l\) is part of the answer. We only cut off what comes before \(l\), which is \(a_1, \dots, a_{l-1}\), and that is exactly \(\mathrm{pre}_{l-1}\).

Why do our templates use 1-indexed arrays?

When \(l = 1\) the formula needs \(\mathrm{pre}_0\). If index \(0\) is a dummy slot with \(a_0 = 0\), then \(\mathrm{pre}_0 = 0\) and the formula works for every \(l\) with no special case. That is why we always write a = [0] + actual_array.

2.3 Cost

	build	one query	\(q\) queries
naive loop	—	\(O(n)\)	\(O(nq)\)
prefix sum	\(O(n)\)	\(O(1)\)	\(O(n + q)\)

For the example problem: \(2 \cdot 10^5 + 2 \cdot 10^5\) steps instead of \(4 \cdot 10^{10}\).

2.4 2D prefix sum

Now the array is a grid \(A\) with \(n\) rows and \(m\) columns, and a query asks for the sum of a rectangle.

Define \(S_{i,j}\) as the sum of the rectangle from the top-left cell \((1,1)\) to \((i,j)\):

\[ S_{i,j} = \sum_{i' \le i} \; \sum_{j' \le j} A_{i',j'} . \]

Building \(S\) (inclusion–exclusion). Take the block above, \(S_{i-1,j}\), and the block to the left, \(S_{i,j-1}\). Together they cover everything except cell \((i,j)\), but their overlap \(S_{i-1,j-1}\) is counted twice. Add the cell and subtract the overlap once:

\[ S_{i,j} = A_{i,j} + S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1} . \]

In this picture \(S_{3,3}\) is the dashed box. The blue block is \(S_{3,2}\) and the red block is \(S_{2,3}\). They overlap in \(S_{2,2}\), so

\[ S_{3,3} = A_{3,3} + S_{2,3} + S_{3,2} - S_{2,2} = 5 + 15 + 18 - 9 = 29 . \]

Querying a rectangle. To get the sum of rows \(x_1..x_2\) and columns \(y_1..y_2\), start from the big block \(S_{x_2,y_2}\) and remove what lies above and to the left:

\[ \text{answer} = S_{x_2,y_2} - S_{x_1-1,\,y_2} - S_{x_2,\,y_1-1} + S_{x_1-1,\,y_1-1} . \]

Check on the grid above with rows \(2..3\) and columns \(2..3\), where the answer is \(1 + 2 + 3 + 5 = 11\): \(S_{3,3} - S_{1,3} - S_{3,1} + S_{1,1} = 29 - 7 - 12 + 1 = 11\). ✓

2.5 Which operations can be "prefixed"?

The trick needs a way to undo the short prefix.

operation	undo	range query \([l, r]\)?
sum \(+\)	subtract	✅ pre[r] - pre[l-1]
xor \(\oplus\)	xor again, because \(x \oplus x = 0\)	✅ pre[r] ^ pre[l-1]
count of elements with a property	subtract	✅ same as sum, add 1 or 0
max / min	no undo	❌ only \([1, r]\) (prefix) or \([l, n]\) (suffix)

For example, knowing \(\max(a_1..a_5) = 9\) and \(\max(a_1..a_1) = 3\) tells you nothing about \(\max(a_2..a_5)\). That is why PrefixMax below only answers query(r).

3. Templates

These are the templates we use in class. Use them exactly as written.

All templates below use a 1-indexed array:

a = [0, ...]

So a[0] is not used.

1. Prefix Sum

Template

class PrefixSum:
    def __init__(self, a):
        n = len(a)
        self.pre = [0] * n

        for i in range(1, n):
            self.pre[i] = self.pre[i - 1] + a[i]

    def query(self, l, r):
        return self.pre[r] - self.pre[l - 1]

Usage

a = [0, 2, 4, 1, 7, 3]

ps = PrefixSum(a)

print(ps.query(2, 5))  # 4 + 1 + 7 + 3 = 15
print(ps.query(3, 4))  # 1 + 7 = 8

Use prefix sum when you need many range sum queries:

sum(a[l], a[l + 1], ..., a[r])

2. Prefix XOR

Template

class PrefixXor:
    def __init__(self, a):
        n = len(a)
        self.pre = [0] * n

        for i in range(1, n):
            self.pre[i] = self.pre[i - 1] ^ a[i]

    def query(self, l, r):
        return self.pre[r] ^ self.pre[l - 1]

Usage

a = [0, 2, 4, 1, 7, 3]

px = PrefixXor(a)

print(px.query(2, 5))  # 4 ^ 1 ^ 7 ^ 3
print(px.query(3, 4))  # 1 ^ 7

Use prefix xor when you need many range xor queries:

a[l] ^ a[l + 1] ^ ... ^ a[r]

3. Suffix Sum

Template

class SuffixSum:
    def __init__(self, a):
        n = len(a)
        self.suf = [0] * (n + 1)

        for i in range(n - 1, 0, -1):
            self.suf[i] = self.suf[i + 1] + a[i]

    def query(self, l, r):
        return self.suf[l] - self.suf[r + 1]

Usage

a = [0, 2, 4, 1, 7, 3]

ss = SuffixSum(a)

print(ss.query(2, 5))  # 4 + 1 + 7 + 3 = 15
print(ss.query(3, 4))  # 1 + 7 = 8

Suffix sum is useful when building answers from right to left.

4. Prefix Max

Template

class PrefixMax:
    def __init__(self, a):
        n = len(a)
        self.pre = [0] * n

        self.pre[1] = a[1]
        for i in range(2, n):
            self.pre[i] = max(self.pre[i - 1], a[i])

    def query(self, r):
        return self.pre[r]

Usage

a = [0, 2, 4, 1, 7, 3]

pm = PrefixMax(a)

print(pm.query(3))  # max(2, 4, 1) = 4
print(pm.query(5))  # max(2, 4, 1, 7, 3) = 7

Query:

max(a[1], a[2], ..., a[r])

5. Suffix Max

Template

class SuffixMax:
    def __init__(self, a):
        n = len(a)
        self.suf = [0] * (n + 1)

        self.suf[n - 1] = a[n - 1]
        for i in range(n - 2, 0, -1):
            self.suf[i] = max(self.suf[i + 1], a[i])

    def query(self, l):
        return self.suf[l]

Usage

a = [0, 2, 4, 1, 7, 3]

sm = SuffixMax(a)

print(sm.query(2))  # max(4, 1, 7, 3) = 7
print(sm.query(5))  # max(3) = 3

Query:

max(a[l], a[l + 1], ..., a[n - 1])

6. Prefix Min

Template

class PrefixMin:
    def __init__(self, a):
        n = len(a)
        self.pre = [0] * n

        self.pre[1] = a[1]
        for i in range(2, n):
            self.pre[i] = min(self.pre[i - 1], a[i])

    def query(self, r):
        return self.pre[r]

Usage

a = [0, 2, 4, 1, 7, 3]

pm = PrefixMin(a)

print(pm.query(3))  # min(2, 4, 1) = 1
print(pm.query(5))  # min(2, 4, 1, 7, 3) = 1

7. Suffix Min

Template

class SuffixMin:
    def __init__(self, a):
        n = len(a)
        self.suf = [0] * (n + 1)

        self.suf[n - 1] = a[n - 1]
        for i in range(n - 2, 0, -1):
            self.suf[i] = min(self.suf[i + 1], a[i])

    def query(self, l):
        return self.suf[l]

Usage

a = [0, 2, 4, 1, 7, 3]

sm = SuffixMin(a)

print(sm.query(2))  # min(4, 1, 7, 3) = 1
print(sm.query(5))  # min(3) = 3

8. Prefix Count

Example: count how many even numbers are in [l, r].

Template

class PrefixCountEven:
    def __init__(self, a):
        n = len(a)
        self.pre = [0] * n

        for i in range(1, n):
            self.pre[i] = self.pre[i - 1] + (1 if a[i] % 2 == 0 else 0)

    def query(self, l, r):
        return self.pre[r] - self.pre[l - 1]

Usage

a = [0, 2, 4, 1, 7, 3]

pc = PrefixCountEven(a)

print(pc.query(1, 3))  # 2, 4 are even -> 2
print(pc.query(3, 5))  # no even numbers -> 0

You can change the condition:

a[i] % 2 == 0

to count other things.

9. 2D Prefix Sum

Use 2D prefix sum to query the sum of a rectangle in a grid.

Template

class PrefixSum2D:
    def __init__(self, grid):
        n = len(grid) - 1
        m = len(grid[1]) - 1

        self.pre = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                self.pre[i][j] = (
                    self.pre[i][j - 1]
                    + self.pre[i - 1][j]
                    - self.pre[i - 1][j - 1]
                    + grid[i][j]
                )

    def query(self, x1, y1, x2, y2):
        left_top = self.pre[x1 - 1][y1 - 1]
        right_down = self.pre[x2][y2]
        left_down = self.pre[x1 - 1][y2]
        right_top = self.pre[x2][y1 - 1]
        return right_down - left_down - right_top + left_top

Usage

grid = [
    [0, 0, 0, 0],
    [0, 1, 2, 3],
    [0, 4, 5, 6],
    [0, 7, 8, 9],
]

ps = PrefixSum2D(grid)

print(ps.query(1, 1, 2, 2))  # 1 + 2 + 4 + 5 = 12
print(ps.query(2, 2, 3, 3))  # 5 + 6 + 8 + 9 = 28

The query means:

sum of grid[x1][y1] to grid[x2][y2]

Input Version

import sys

input = sys.stdin.readline


def solve():
    n, m = map(int, input().split())

    grid = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        grid[i] = [0] + list(map(int, input().split()))

    pre = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + grid[i][j]

    def query(x1, y1, x2, y2):
        left_top = pre[x1 - 1][y1 - 1]
        right_down = pre[x2][y2]
        left_down = pre[x1 - 1][y2]
        right_top = pre[x2][y1 - 1]
        return right_down - left_down - right_top + left_top

10. Notes

• Build time is O(n).
• Each query is O(1).
• These templates are for 1-indexed arrays.
• Always write a = [0] + actual_array.
• For range queries, make sure 1 <= l <= r < len(a).
• For 2D prefix sum, make sure 1 <= x1 <= x2 <= n and 1 <= y1 <= y2 <= m.
• Prefix max/min can only answer queries starting from index 1.
• Suffix max/min can only answer queries ending at the last real element.
• For any general range max/min query [l, r], use another data structure, such as a segment tree or sparse table.

4. Worked solution — Odd Queries

Put a dummy 0 in front, build the PrefixSum template once per test, then answer each query with the formula from §1.

import sys

input = sys.stdin.readline


class PrefixSum:
    def __init__(self, a):
        n = len(a)
        self.pre = [0] * n

        for i in range(1, n):
            self.pre[i] = self.pre[i - 1] + a[i]

    def query(self, l, r):
        return self.pre[r] - self.pre[l - 1]


def solve():
    n, q = map(int, input().split())
    a = [0] + list(map(int, input().split()))

    ps = PrefixSum(a)
    total = ps.query(1, n)

    for _ in range(q):
        l, r, k = map(int, input().split())
        new_sum = total - ps.query(l, r) + k * (r - l + 1)
        if new_sum % 2 == 1:
            print("YES")
        else:
            print("NO")


t = int(input())
for _ in range(t):
    solve()

Trace the first test: a = [0, 2, 2, 1, 3, 2], pre = [0, 2, 4, 5, 8, 10], total \(= 10\).

query	removed pre[r] - pre[l-1]	added \(k(r-l+1)\)	new sum	answer
2 3 3	\(5 - 2 = 3\)	\(3 \cdot 2 = 6\)	\(13\)	YES
2 3 4	\(5 - 2 = 3\)	\(4 \cdot 2 = 8\)	\(15\)	YES
1 5 5	\(10 - 0 = 10\)	\(5 \cdot 5 = 25\)	\(25\)	YES
1 4 9	\(8 - 0 = 8\)	\(9 \cdot 4 = 36\)	\(38\)	NO
2 4 3	\(8 - 2 = 6\)	\(3 \cdot 3 = 9\)	\(13\)	YES

Cost: \(O(n)\) to build, \(O(1)\) per query, so \(O(n + q)\) per test.

5. Common mistakes

Forgetting the dummy 0

ps = PrefixSum(list(map(int, input().split()))) shifts every index by one. The template expects a = [0] + ....

Using pre[l] instead of pre[l - 1]

That drops \(a_l\) from the answer. Test with \(l = r\): the answer must be \(a_l\) itself.

Rebuilding inside the query loop

Building costs \(O(n)\). Build once before the loop, or you are back to \(O(nq)\).

Actually changing the array

Odd Queries says the queries are independent. Never write \(k\) into a; compute the new sum from the formula.

Wrong sign on the corner in 2D

The corner \(S_{x_1-1,\,y_1-1}\) is added, not subtracted. Check with a \(2 \times 2\) grid of all ones.

Range max with a prefix max

PrefixMax cannot answer \(\max(a_l..a_r)\) for \(l > 1\) (see §2.5).

Slow I/O

With \(2 \cdot 10^5\) lines of input, put input = sys.stdin.readline at the top. Plain input() is much slower.

6. Practice

Problems from our gym sets that use this idea. See Problems for your status on each.

Problem	Set	Rating	Which variant
1807D · Odd Queries	1 · A, 4-Misc · A	900	1D sum (this page)
2008E · Alternating String	10-prefixsum · C	1500	prefix counts (26 letters × parity)
1398C · Good Subarrays	10-prefixsum · B	1600	prefix sum + counting equal values
1722E · Counting Rectangles	7-Intervals · G	1600	2D prefix sum
1291D · Irreducible Anagrams	10-prefixsum · A	1800	prefix counts of letters
2026D · Sums of Segments	10-prefixsum · E	1900	prefix sum of prefix sums + binary search

---

Credits & licenses

• 2D prefix-sum figure (§2.4): copied unchanged from OI Wiki — Prefix Sum & Difference by the OI Wiki contributors, licensed CC BY-SA 4.0. The explanation around it is translated and adapted from the same page.
• Section structure follows USACO Guide — Introduction to Prefix Sums by Darren Yao and Dustin Miao, licensed CC BY-NC-SA 4.0.
• Everything else (text, the 1D figure, the query diagram, the worked solution) is ours. The templates in §3 are from our lessons.