Sums of Numbers and Digits
National Olympiad — National round (2026 season)
Submission name: sums.cpp
Problem summary
Given an array and K inclusive index intervals, add the sums of the numbers in every interval. Also add the sums of the decimal digits of all numbers in every interval. Repeated appearances in overlapping intervals count repeatedly.
Input
N and K, the N array values, then K pairs left right using 1-based indices.
Output
Two lines: total of interval number sums, then total of interval digit sums.
Constraints
2 ≤ N ≤ 50,000; 2 ≤ K ≤ 16,000; 1 ≤ a[i] < 10,000,000; 1 ≤ left < right ≤ N.
Worked example
An independently prepared example for this explanation.
Input
4 2 10 23 5 40 1 3 2 4
Output
106 25
Solution analysis
- Build numberPrefix[i], the sum of a[1] through a[i]. Compute each a[i]’s digit sum by repeatedly taking value % 10 and dividing value by 10.
- Build a second prefix array digitPrefix for those individual digit sums. The digit sum of a whole interval’s numeric sum is not the same thing.
- Each inclusive interval [left,right] contributes numberPrefix[right] − numberPrefix[left−1], and the analogous difference in digitPrefix. Add these differences to two separate totals.
- For [10,23,5,40], intervals [1,3] and [2,4] contribute 38 and 68 to the first total, giving 106. Individual digit sums are [1,5,5,4]; the intervals contribute 11 and 14, giving 25.
Why it works
Prefix subtraction cancels exactly the entries before left and leaves every entry from left to right once. Applying the same argument to the digit-sum array gives the second answer. Adding query answers naturally counts overlaps as often as specified.
Watch out. Use long long for numeric prefixes and both accumulated answers. Digit prefixes fit int under these bounds, but their total over all K intervals may not. Preserve 1-based interval endpoints and initialize prefix[0] to zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int digitSum(int value) {
int sum = 0;
while (value > 0) {
sum += value % 10;
value /= 10;
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count, queryCount;
cin >> count >> queryCount;
vector<long long> numberPrefix(count + 1, 0);
vector<int> digitPrefix(count + 1, 0);
for (int i = 1; i <= count; i++) {
int value;
cin >> value;
numberPrefix[i] = numberPrefix[i - 1] + value;
digitPrefix[i] = digitPrefix[i - 1] + digitSum(value);
}
long long totalNumbers = 0;
long long totalDigits = 0;
for (int query = 0; query < queryCount; query++) {
int left, right;
cin >> left >> right;
// Every query contributes independently, including overlaps.
totalNumbers += numberPrefix[right] - numberPrefix[left - 1];
totalDigits += digitPrefix[right] - digitPrefix[left - 1];
}
cout << totalNumbers << '\n';
cout << totalDigits << '\n';
}