Prefix sums that go negative

A range-sum service precomputes prefix sums over up to 10^5 sensor readings, each up to 10^9. Small test files pass, but on production data rangeSum(0, n - 1) returns a *negative* number, and the binary search that locates the first prefix >= target occasionally reads out of bounds. Find every bug.

1#include <iostream>
2#include <vector>
3using namespace std;
4 
5vector<int> buildPrefix(const vector<int>& a) {
6  vector<int> pre(a.size() + 1, 0);
7  for (size_t i = 0; i < a.size(); ++i)
8    pre[i + 1] = pre[i] + a[i];
9  return pre;
10}
11 
12int rangeSum(const vector<int>& pre, int l, int r) {
13  return pre[r + 1] - pre[l];
14}
15 
16// first index i with pre[i] >= target, or pre.size() if none
17int firstAtLeast(const vector<int>& pre, int target) {
18  int lo = 0, hi = static_cast<int>(pre.size());
19  while (lo < hi) {
20    int mid = (lo + hi) / 2;
21    if (pre[mid] >= target) hi = mid;
22    else lo = mid + 1;
23  }
24  return lo;
25}
26 
27int main() {
28  vector<int> a(100000, 1000000000);
29  vector<int> pre = buildPrefix(a);
30  cout << rangeSum(pre, 0, 99999) << "\n";   // prints a negative number
31  cout << firstAtLeast(pre, 2000000000) << "\n";
32}

1. Compute the largest value a prefix sum can reach with the given constraints. Does it fit in a 32-bit int?
2. Explain why the answer is negative rather than an exception or a crash.
3. Look at int mid = (lo + hi) / 2 and at the target parameter. Which other overflows are hiding here?
4. Write the corrected code using appropriately sized integer types.
5. State the complexity of buildPrefix, rangeSum and firstAtLeast.