Prefix Sum

In one sentence

Spend \(O(n)\) once to store running totals pre[i]; after that, the sum of any range \([l, r]\) is one subtraction, pre[r] - pre[l - 1].

1. What problem does it solve?

Example — 1873F · Money Trees (5-BinarySearch · I, rating 1300)

\(n\) trees stand in a row; tree \(i\) has \(a_i\) fruits and height \(h_i\). Choose a contiguous group of trees \([l, r]\) such that

• every tree's height is divisible by the next one's: \(h_i\) is divisible by \(h_{i+1}\) for all \(l \le i < r\), and
• the total number of fruits \(a_l + \dots + a_r\) is at most \(k\).

Print the largest possible number of trees \(r - l + 1\) (or \(0\) if no single tree works).

Limits: \(t \le 1000\), \(n \le 2\cdot10^5\) (sum over tests), \(a_i, h_i \le 10^9\), \(k \le 10^9\).

Input            Output
5
5 12
3 2 4 1 8
4 4 2 4 1        3
4 8
5 4 1 2
6 2 3 1          2
3 12
7 9 10
2 2 4            1
1 10
11
1                0
7 10
2 6 3 1 5 10 6
72 24 24 12 4 4 2   3

This is exactly the question from our 12 April lesson: for each left end \(l\), find the largest right end \(r\) whose range sum is still within the limit. Two things must be fast:

1. "Is the sum of \([l, r]\) at most \(k\)?": adding up \(a_l \dots a_r\) each time costs \(O(n)\). A prefix sum answers it in \(O(1)\).
2. "Which \(r\) is the largest?": trying every \(r\) costs \(O(n)\) per \(l\). Since all \(a_i \ge 1\), the sum only grows as \(r\) grows, so binary search finds it in \(O(\log n)\).

The divisibility rule only limits how far right \(r\) may go.

2. The math

2.1 Definition

With the array 1-indexed and \(\texttt{pre}[0] = 0\):

\[ \texttt{pre}[i] = a_1 + a_2 + \dots + a_i = \texttt{pre}[i-1] + a_i . \]

2.2 The query formula

\[ \texttt{pre}[r] = \underbrace{a_1 + \dots + a_{l-1}}_{\texttt{pre}[l-1]} + \underbrace{a_l + \dots + a_r}_{\text{what we want}} \quad\Longrightarrow\quad a_l + \dots + a_r = \texttt{pre}[r] - \texttt{pre}[l-1]. \]

Because pre[0] = 0, the formula also works for \(l = 1\) without a special case.

2.3 Trace on sample 1

\(k = 12\), \(a = (3, 2, 4, 1, 8)\), \(h = (4, 4, 2, 4, 1)\).

\(i\)	0	1	2	3	4	5
\(a_i\)		3	2	4	1	8
pre[i]	0	3	5	9	10	18
\(h_i\) divisible by \(h_{i+1}\)?		yes (4,4)	yes (4,2)	no (2,4)	yes (4,1)	—
far[i]		3	3	3	5	5

far[i] is the farthest index we may reach from \(i\) without breaking the divisibility chain. It is filled from right to left: far[n] = n, and far[i] = far[i + 1] if \(h_i\) is divisible by \(h_{i+1}\), otherwise far[i] = i.

For \(l = 1\) we may use \(r \in [1, 3]\): sums pre[r] - pre[0] are \(3, 5, 9\), all \(\le 12\), so \(r = 3\) and the length is 3. For \(l = 4\): \(r \in [4, 5]\), sums \(1\) and \(9\), length \(2\). The answer is \(3\).

2.4 Cost

\(O(n)\) for pre and far, then \(O(\log n)\) binary search per \(l\): \(O(n \log n)\) in total. (A two-pointer window can even do it in \(O(n)\); writing both versions once is good practice, as our Search & Ranges recap says.)

3. Lesson notes

1. Prefix Sum

Idea

If you need the sum of many different ranges of a fixed array, do not add the numbers again for each query. Add them once, from left to right, and store the running total.

pre[i] = a[1] + a[2] + ... + a[i]

Then the sum of any range [l, r] is one subtraction:

sum(l, r) = pre[r] - pre[l - 1]

Build it once in O(n). Every query after that is O(1).

Template

vector<ll> pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] + a[i];
}

ll sum = pre[r] - pre[l - 1];

Things to be careful about

• Index the array from 1, and make pre of size n + 1. Then pre[l - 1] is safe when l == 1.
• pre should be long long. The individual numbers may be small, but the total is often not.
• Prefix sum only works when the array does not change. If values are updated between queries, this is the wrong tool.

When to reach for it

You see repeated questions of the form "what is the sum / count between these two positions". Counting also works: store 0 and 1 in the array, and the prefix sum tells you how many 1s are in a range.

4. Worked solution — Money Trees

Prefix sum from §3, and "Binary Search Template 1" (largest valid value) from the binary search page, with a check lambda just like on 12 April.

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> a(n + 1), h(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    vector<ll> pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + a[i];
    }

    // far[i]: the farthest r such that h[i..r] keeps the divisibility chain
    vector<int> far(n + 1);
    far[n] = n;
    for (int i = n - 1; i >= 1; i--) {
        if (h[i] % h[i + 1] == 0) {
            far[i] = far[i + 1];
        } else {
            far[i] = i;
        }
    }

    int ans = 0;
    for (int l = 1; l <= n; l++) {
        auto check = [&](int r) -> bool {
            return pre[r] - pre[l - 1] <= k;
        };

        int lo = l, hi = far[l], best = -1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (check(mid)) {
                best = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        if (best != -1) {
            ans = max(ans, best - l + 1);
        }
    }

    cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

5. What can be "prefixed"?

Store in pre[i]	Query	Needs
sum \(a_1 + \dots + a_i\)	range sum = pre[r] - pre[l-1]	subtraction undoes addition
count of "good" positions (store 1 or 0)	how many good ones in \([l, r]\)	same
XOR \(a_1 \oplus \dots \oplus a_i\)	range XOR = pre[r] ^ pre[l-1]	XOR undoes itself
maximum \(\max(a_1, \dots, a_i)\)	only prefixes \([1, r]\)	max cannot be undone, so no general ranges

6. Common mistakes

pre as int

With \(n = 2\cdot10^5\) and \(a_i = 10^9\) the total is \(2\cdot10^{14}\). Use long long.

0-indexed array with pre[l - 1]

If a starts at index 0, pre[l - 1] with \(l = 0\) reads pre[-1]. Index from 1 and make pre size n + 1.

The array changes between queries

A prefix sum is a snapshot. If values are updated after it is built, every later pre[i] is stale.

Binary search when values can be negative

The "largest \(r\)" search only works because every \(a_i \ge 1\) makes the range sum increase with \(r\). With negative values that monotonicity is gone.

7. Practice

Problem	Set	Rating	Idea
1873F · Money Trees	5-BinarySearch · I	1300	prefix sum + binary search per \(l\) (this page)
AIO 2018 · Cloud Coverage	AIO 2018 Q3	—	positions are prefix sums of the gaps; minimum window
AIO 2022 · Spaceship Shuffle	AIO 2022 Q6	—	prefix sums are the flow on each edge
OJ · PYEXAMN	homework 12 Apr	—	longest range with sum \(\le s\), two ways

---

Credits & licenses

• §3 joins the Prefix Sum notes of 12 April and section 1 of our Search & Ranges recap (August), unchanged apart from heading levels.
• Example, derivations, trace, worked solution, table and mistakes are ours.