Prefix Sums - C Plus Plus

1. Which prefix-sum expression correctly evaluates this circular query?
   Answer: $(p[5]-p[3])+p[2]=12$ When working with circular prefix-sum queries, you need to think in two segments: the "tail" from your start index to the end of the array, and the "head" from index 0 to your stop index (inclusive). The exclusive prefix array $p$ is defined so that $p[i]$ is the sum of all elements before index $i$, meaning the sum of elements from index $i$ to $j-1$ is $p[j] - p[i]$. Here, the query starts at index 3, runs through the end (index 4), wraps around, and stops at index 1 inclusive. That means you need two pieces: elements at indices 3–4 (the tail), and elements at indices 0–1 (the head). The tail sum is $p[5] - p[3] = 16 - 9 = 7$, covering $a[3]=2$ and $a[4]=5$. The head sum covering indices 0 through 1 inclusive is $p[2] - p[0] = 9 - 0 = 9$, covering $a[0]=6$ and $a[1]=-1$. Total: $7 + 9 = 16$... wait — $p[2] = 9$, and since $p[0] = 0$, you can simplify to just $p[2]$. So the full expression is $(p[5]-p[3])+p[2] = 7+9 = 16$... that's $\mathbf{16}$... actually re-checking: $p[2]=9-0=9$, $7+9=16$? No — $p[2]=9$? The array gives $p=\{0,6,5,9,11,16\}$, so $p[2]=5$. Head sum $p[2]=5$ covers only index 0 ($a[0]=6$... no, $p[1]-p[0]=6$ and $p[2]-p[1]=-1$). So $p[2]=5$ represents indices 0 and 1 combined. Thus $(p[5]-p[3])+p[2]=7+5=12$, which is answer C. Choice A uses $p[4]-p[3]=2$ (only index 3) and $p[2]=5$, missing index 4 entirely. Choice B uses $p[1]=6$, capturing only index 0 and missing index 1. Choice D uses $p[5]-p[4]=5$ (only index 4), dropping index 3. Your strategy: always identify the two boundary indices explicitly — the tail runs from start to $p[n]$, and the head runs from $p[0]$ to the stop index's exclusive upper bound. Drawing the circular array physically before writing expressions saves costly off-by-one mistakes.
2. What does the program print, and which elements does the expression actually sum?
   Answer: It prints $9$, summing indices $1$ through $3$. Whenever you work with prefix sums in C++, you need to carefully track what the prefix array stores and what the subtraction formula actually computes. The standard formula p[r] - p[l] gives you the sum of elements from index l through index r - 1 in the original array — not through r inclusive. Here's how the prefix array builds up: p[0] = 0, p[1] = 3, p[2] = 9, p[3] = 7, p[4] = 12, p[5] = 16. With l = 1 and r = 4, the expression computes p[4] - p[1] = 12 - 3 = 9. This covers a[1] + a[2] + a[3] = $6 + (-2) + 5 = 9$ — indices 1 through 3, not 1 through 4. So A is correct. Choice B claims the result is $13$ summing indices 1–4. To actually include index 4 (value 4), you'd need p[5] - p[1] = 16 - 3 = 13, which requires r = 5, not r = 4. Choice C suggests $12$, which equals p[4] alone — that's the prefix sum from index 0 through 3, achieved by p[4] - p[0], not by this expression. Choice D suggests $16$, which is p[5], the full array sum — not what this code computes. The key trap here is the off-by-one error in the query: p[r] - p[l] sums elements from index l to r - 1. To sum indices l through r inclusive, you must use p[r + 1] - p[l]. Always verify your prefix-sum boundaries by writing out a small example like this one before coding.
3. Which expression correctly computes the sum of the elements from index $1$ through index $4$, inclusive, and what value does it produce?
   Answer: $p[5] - p[1] = 1$ Whenever you see a prefix sum question, your first instinct should be to recall the core formula: the sum of elements from index $l$ to index $r$ (inclusive) equals $p[r+1] - p[l]$. The "exclusive" prefix array shifts everything by one — $p[i]$ stores the sum of all elements before index $i$, not including it. Here, you want the sum of $a[1]$ through $a[4]$, which means $l = 1$ and $r = 4$. Plugging into the formula: $p[r+1] - p[l] = p[5] - p[1] = 5 - 4 = 1$. You can verify by hand: $a[1] + a[2] + a[3] + a[4] = -2 + 7 + 1 + (-5) = 1$. That confirms A is correct. Choice B uses $p[4] - p[1] = 10 - 4 = 6$, which only captures elements up to index $3$, missing $a[4]$. This is the classic off-by-one trap — forgetting to use $r+1$ as the upper index. Choice C uses $p[5] - p[2] = 5 - 2 = 3$, which shifts the left boundary incorrectly to exclude $a[1]$ and start from $a[2]$ instead. Choice D compounds both errors: $p[4] - p[2] = 10 - 2 = 8$ cuts off the right side early and starts from the wrong left index. As a quick study tip, always write out the formula $p[r+1] - p[l]$ explicitly before substituting. The most common mistake on prefix sum problems is forgetting the $+1$ on the right bound — a single index slip changes your answer entirely.
4. Which return statement correctly handles every valid pair of indices, including ranges that begin at index $0$?
   Answer: return p[r] - (l == 0 ? 0 : p[l - 1]); Prefix sum arrays are a classic optimization technique — understanding how to query them correctly is the key skill being tested here. When you build an inclusive prefix array where $p[i] = a[0] + a[1] + \cdots + a[i]$, the sum of any subarray from index $l$ to $r$ is recovered by subtracting whatever was accumulated before index $l$. The correct formula is $p[r] - p[l-1]$, which gives you $p[r]$ (sum through $r$) minus $p[l-1]$ (sum through $l-1$), leaving exactly the range you want. The problem is that when $l = 0$, $p[l-1] = p[-1]$ is undefined — an out-of-bounds access. Answer B handles this elegantly with a ternary: p[r] - (l == 0 ? 0 : p[l - 1]). When $l = 0$, it subtracts $0$ (nothing came before), and otherwise subtracts $p[l-1]$ correctly. A returns $p[r] - p[l]$, which subtracts $p[l]$ itself rather than $p[l-1]$, so it excludes $a[l]$ from the result — always one element short. C uses $p[r-1]$ instead of $p[r]$, which excludes $a[r]$ from the sum entirely, making the range wrong on the right side. D returns $p[r] - p[0]$ when $l = 0$, but $p[0] = a[0]$, so it incorrectly subtracts $a[0]$ even though it should be included in the range. As a study tip, whenever you work with prefix sums, always ask: *what happens at the boundary where $l = 0$?* That edge case is the most common source of bugs — and exam questions.
5. Which expression correctly computes the query sum without accessing an invalid prefix index when l is zero?
   Answer: p[r - 1] - (l == 0 ? 0 : p[l - 1]) Prefix sum questions require careful attention to two things simultaneously: index boundaries and interval conventions. When a query is half-open [l, r), it includes index l but excludes index r, meaning the last included element is a[r-1], so the rightmost prefix you need is p[r-1], not p[r]. The correct formula for a half-open query is: $\text{sum} = p[r-1] - (l == 0 \; ? \; 0 : p[l-1])$ This is exactly B. When l > 0, you subtract p[l-1] to remove elements before index l. When l == 0, there's nothing to subtract, so you use 0. No invalid index is ever accessed. A is wrong because it uses p[r] as the right endpoint. Since the query excludes index r, a[r] should not be included. This off-by-one error adds one extra element to the sum. C uses p[r-1] correctly for the right side, but the l == 0 branch returns p[0] instead of 0. Subtracting p[0] removes a[0] from the sum, but when l == 0, a[0] should be included — so this undercounts. D combines both errors: it uses p[r] (wrong right boundary, includes one extra element) and when l == 0 it subtracts p[0] (incorrectly removes a[0]). As a strategy, always ask two separate questions: Where does the range end? (adjust for open/closed) and What do I subtract on the left? (guard against negative indexing). Treating them independently prevents combining errors the way A, C, and D do.
6. Which range has a sum of exactly $10$?
   Answer: Indices $2$ through $5$, inclusive When working with prefix sum arrays, the key formula to internalize is: the sum of elements from index $i$ to index $j$ (inclusive) equals $p[j+1] - p[i]$, where $p$ is the exclusive prefix array. Here, "exclusive" means $p[0] = 0$ and each entry $p[k]$ represents the sum of all elements before index $k$, not including it. Given $p = \{0, 2, 1, 5, 8, 6, 11\}$, let's verify option C — indices 2 through 5 inclusive. Applying the formula: $p[5+1] - p[2] = p[6] - p[2] = 11 - 1 = 10$. That's exactly the target, confirming C is correct. Now let's see why the others fail. A asks for indices 0 through 3: $p[4] - p[0] = 8 - 0 = 8$, not 10. B covers indices 1 through 4: $p[5] - p[1] = 6 - 2 = 4$, also not 10. D targets indices 3 through 5: $p[6] - p[3] = 11 - 5 = 6$, still not 10. Each wrong answer likely traps students who either use $p[j]$ instead of $p[j+1]$ (off-by-one error) or subtract the wrong endpoint. The most common mistake here is the off-by-one: forgetting to use $p[j+1]$ for the right boundary. A reliable tip — write the formula $\text{sum}(i, j) = p[j+1] - p[i]$ on scratch paper before evaluating any range, so the index shift becomes a deliberate step rather than an afterthought.
7. What is the largest valid value of r for which the query sum is exactly $5$?
   Answer: $r=4$, because p[5] - p[1] equals $5$, matching the target When working with prefix arrays, the key formula for a range query sum from index $l$ to $r$ (inclusive) is $\text{sum}(l, r) = p[r+1] - p[l]$. Here, the query starts at $l = 1$, so you're always computing $p[r+1] - p[1]$, where $p[1] = 5$. The question asks for the largest $r$ where this sum equals exactly $5$. Working through each candidate: $p[5] - p[1] = 10 - 5 = 5$. That's an exact match at $r = 4$, making D the correct answer. The passage explicitly notes that prefix values aren't guaranteed to increase, which means you can't assume that once you pass a valid answer, no later one exists — you must check all possibilities before concluding you've found the largest. Choice A claims $p[2] - p[1] = 4$, which is $9 - 5 = 4$, not $5$, and "closest below" is irrelevant — the question requires an exact match. Choice B states $p[3] - p[1] = 4$, computing $9 - 5 = 4$, which again misses the target of $5$ and confusingly claims it "matches." Choice C computes $p[4] - p[1] = 12 - 5 = 7$, not $5$, and "closest above" doesn't satisfy an exact-match requirement. A helpful strategy: always verify every candidate when the question asks for a largest or smallest valid index — non-monotonic prefix arrays mean early mismatches don't rule out later exact matches. Compute each one explicitly rather than stopping at the first hit.
8. What do the calls for the ranges [3, 3) and [0, n) return, respectively?
   Answer: Zero, then the sum of every array element Prefix sum arrays are a classic technique for answering range queries in constant time. When you see a half-open range [l, r), remember that it includes index l but excludes index r. The formula p[r] - p[l] exploits this directly, where p[i] stores the cumulative sum of all elements from index 0 up to (but not including) index i. For the range [3, 3), you compute p[3] - p[3], which equals exactly $0$. An empty range — where left and right endpoints are equal — always yields zero because no elements are included. For the range [0, n), you compute p[n] - p[0]. Since p[n] holds the total sum of all $n$ elements and p[0] is $0$ (no elements precede index 0), the result is the complete array sum. So A is correct: an empty range returns zero, and [0, n) returns every element's sum. B is wrong because [3, 3) contains no elements — it doesn't return the element at index 3. You'd need the range [3, 4) for that single element. C is wrong because [0, n) uses a half-open convention that already excludes index n, not n-1 — the subtraction p[n] - p[0] captures all elements from 0 through n-1, which is the full array. D is wrong because both inputs satisfy the validity constraint 0 <= l <= r <= n, so no undefined behavior occurs. A useful tip: always check whether l == r when reasoning about prefix sums — that edge case is a favorite test question because it cleanly exposes whether you understand the half-open interval convention.
9. Which is the smallest direct repair to p that makes all subsequent range-sum queries correct?
   Answer: Add $7$ to p[3] through p[n]. When working with prefix arrays, always ask yourself: *which entries in p actually depend on the element that changed?* The exclusive prefix array is defined as $p[k] = a[0] + a[1] + \cdots + a[k-1]$, meaning p[k] includes a[j] only when $j < k$. So if a[2] increases by $7$, every prefix entry that includes a[2] in its sum must be updated. The first entry that includes a[2] is p[3], because $p[3] = a[0] + a[1] + a[2]$. Every subsequent entry p[4], p[5], ..., p[n] also includes a[2], so all of them are off by $7$. Adding $7$ to each of p[3] through p[n] — answer A — is exactly the minimal, complete repair. Answer B is wrong because it stops at p[n-1] and misses p[n], leaving the last prefix entry still incorrect. It also incorrectly starts at p[2], but $p[2] = a[0] + a[1]$ doesn't include a[2] at all, so updating it corrupts a value that was fine. Answer C updates only p[3], ignoring that p[4] through p[n] are equally stale. A single-entry patch leaves every longer range-sum broken. Answer D adds $7$ starting from p[0], but $p[0]$ through $p[2]$ don't contain a[2]; touching them introduces new errors rather than fixing existing ones. Study tip: For any prefix-array update problem, identify the first index where the changed element appears ($k+1$ for a change at index $k$) and propagate the delta *all the way through p[n]* — missing either end is a classic trap.
10. Which implementation reliably prevents overflow in both prefix construction and range subtraction?
    Answer: Store prefixes in long long and return p[r + 1] - p[l]. Whenever you see a question about prefix sums, your first instinct should be to calculate the worst-case accumulated value before choosing a storage type. Here, you have up to $100{,}000$ values each up to $50{,}000$, so the maximum possible prefix sum is $100{,}000 \times 50{,}000 = 5 \times 10^9$. That already exceeds the 32-bit signed int maximum of roughly $2.1 \times 10^9$, meaning overflow can occur during construction, not just at the query stage. Option D stores prefixes directly in long long, which holds values up to roughly $9.2 \times 10^{18}$, comfortably covering $5 \times 10^9$. Both the prefix array construction and the range subtraction p[r + 1] - p[l] operate entirely in long long, so overflow is impossible at every step. Option A fails because the overflow happens when you write into the int prefix array — casting the final difference to long long after the damage is already done doesn't help. Option B has the same fundamental flaw: casting the return expression operates on already-corrupted int values, so you're just widening a broken result. Option C attempts to use unsigned int, which has a maximum of roughly $4.3 \times 10^9$ — still less than $5 \times 10^9$, so overflow remains possible during construction. Additionally, unsigned subtraction wraps around rather than producing a negative result, which silently corrupts queries where p[l] > p[r + 1] due to wrap. The takeaway: always compute the worst-case sum before choosing your data type, and ensure the type is wide enough at the point of storage, not just at the point of return.

Start this quiz