Transform the question into a sum
Count conditions, evaluate fixed windows, and compare both sides of a pivot.
A condition contributes zero or one
To count positive values in [l, r], conceptually replace each value with 1 if it is positive and 0 otherwise, then build its prefix. The same method counts vowels or any fixed predicate. Zero is not positive; lowercase vowels here mean a, e, i, o, u.
If a range of length len has count c, then c > 0 means any match, c = 0 means no matches, and c = len means all match. Exactly len − c values fail the condition. A single prefix for one predicate does not automatically answer a different threshold supplied by each query.
Every fixed-length window is one range
A length-k window beginning at l ends at l + k − 1. There are n − k + 1 valid starts. With prefix sums, evaluate each in O(1) and scan them all in O(n). Initialize the best from the first actual window; zero is wrong when every window sum is negative.
Scan starts in increasing order and update only on a strict improvement to keep the earliest start on ties. A rolling window that removes the departing element and adds the incoming one is another O(n) solution.
// Complete C++23 program. Input: n k, then n signed values; 1 <= k <= n.
#include <iostream>
#include <vector>
int main() {
int n, k;
std::cin >> n >> k;
std::vector<long long> pref(n + 1, 0);
for (int i = 1; i <= n; ++i) {
long long x;
std::cin >> x;
pref[i] = pref[i - 1] + x;
}
long long best = pref[k];
int start = 1;
for (int l = 2; l + k - 1 <= n; ++l) {
long long sum = pref[l + k - 1] - pref[l - 1];
if (sum > best) { best = sum; start = l; }
}
std::cout << best << ' ' << start << '\n';
}Exclude the pivot from both sides
At one-based position i, the sum strictly to its left is P[i − 1], while the sum strictly to its right is P[n] − P[i]. Equality identifies a balance position. The pivot itself belongs to neither side. For [2, 1, 5, 1, 2], position 3 is balanced because both sides total 3.
Empty sides sum to zero. Therefore a one-element array is balanced at position 1. A suffix array can instead use S[n + 1] = 0 and S[i] = a[i] + S[i + 1], with n + 2 entries; for sums, the total minus a prefix already provides that information without a second summary.
Prefix sum explorer
Query [l, r] is zero-based and inclusive. P[k] stores the total of the first k values; P[0] is zero.
Input array a
Prefix array P
Preprocess once in O(n). Each range sum then takes O(1).
Guided simulation · Change the inputs to test your understanding.
What is the best length-2 window in [−5, −2, −7, −1, −3]?
Turn the idea into code
For [0, 2, −2, 0], is position 1 balanced? Also count the positive values in positions [1, 4].
Give me a hint
Balance compares sums, not side lengths. Positivity is a separate 0/1 transformation.
Show the explained solution
Position 1 is balanced: its empty left side totals 0 and its right side totals 2 − 2 + 0 = 0. Only the value 2 is positive, so the whole-range positive count is 1.
Your notes
Mark complete when you can explain it yourself.