Learning pathOriginal reference
Lesson 10 of 12

Optional: different kinds of totals

Use numeric helpers correctly and derive weighted or modular prefix formulas.

Library helpers still have numeric types

<numeric> provides std::partial_sum for running totals, std::adjacent_difference for consecutive differences, and std::accumulate for one final total. Allocate output entries before writing; reserve alone changes capacity, not vector size.

partial_sum accumulates using the input iterator’s value type. A vector<long long> destination does not make vector<int> input accumulation wide. Use long long input or an explicit wide loop. For accumulate, the initial value controls the accumulator type: use 0LL for long long. These helpers do not record interval-update markers for you.

Shift global weights to local weights

For a query a[l] + 2a[l + 1] + ... + (r − l + 1)a[r], store ordinary prefixes P and globally weighted prefixes W[i] = sum of j × a[j] through i. The desired relative weight at position i is i − l + 1.

Therefore answer = (W[r] − W[l − 1]) − (l − 1)(P[r] − P[l − 1]). Build in O(n), answer in O(1), and allocate O(n). The source’s |a[i]| ≤ 10⁶ bound keeps the weighted totals and intermediate products within long long.

C++23
// Complete C++23 program. Input: n q, n values, q inclusive ranges.
// n,q <= 200000; |value| <= 1e6.
#include <iostream>
#include <vector>
int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<long long> pref(n + 1, 0), weighted(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        long long value;
        std::cin >> value;
        pref[i] = pref[i - 1] + value;
        weighted[i] = weighted[i - 1] + i * value;
    }
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        long long sum = pref[r] - pref[l - 1];
        long long global = weighted[r] - weighted[l - 1];
        std::cout << global - (l - 1LL) * sum << '\n';
    }
}

Normalize modular differences

For positive modulus M, normalize each signed input with (value % M + M) % M and keep prefixes in [0, M). Then a range’s nonnegative residue is (P[r] − P[l − 1] + M) % M. C++ remainder can be negative, so the normalization matters.

M must not be zero. When M = 1, every answer is zero. Reducing modulo M does not repair overflow in a multiplication performed before the remainder operation; check intermediate bounds as well as stored residues.

Pause & predict

Why can partial_sum from vector<int> into vector<long long> still overflow?

Choose an answer
Try it yourself

Turn the idea into code

For [4, −2, 7, 0, 3], calculate the relative-weighted sum of [2,5]. Also normalize the integer −1 modulo 5.

Give me a hint

The first value in the queried range must have weight 1, not its global index.

Show the explained solution

The weighted answer is 1×(−2) + 2×7 + 3×0 + 4×3 = 24. The normalized residue of −1 modulo 5 is 4. A global weighted prefix needs the (l − 1) correction to produce these local weights.

Your notes

Ready for the next idea?

Mark complete when you can explain it yourself.

From a problem to a programIdentify the input, output, and constraints, then translate a small plan into C++.Variables, types, and remembered valuesChoose a representation, initialize it, and understand what assignment really changes.Arithmetic without surprisesPredict division and remainder, widen before multiplication, and format decimal answers.Conditions and logical decisionsBuild exclusive categories, combine comparisons, and protect operations with short-circuit logic.Optional: other ways to chooseRecognize switch for exact choices and the conditional operator for choosing a value.For loops: make repetition preciseTrace initialization, condition, body, and update—and avoid an extra iteration.While, do-while, and stopping rulesChoose a loop from its stopping condition and read the exact input format.Break, continue, and early answersDistinguish leaving a loop from skipping one iteration, without losing required input.Five patterns worth understandingUse sums, counts, best-so-far candidates, products, and flags to process a stream.Nested loops: rows and columnsTranslate a shape into two loop roles and count the total work.Take a number apart, one digit at a timeUse remainder and division to process decimal digits, including zero.Multiple cases and a debugging mindsetCombine the patterns, isolate each case, and test the boundaries that can break your idea.Arrays: give every value a placeUnderstand indices, initialization, capacity, active length, and the first safe array loop.Scan, count, search, and compareDistinguish values from positions and preserve the exact tie rule a problem asks for.Change a sequence without losing itUpdate, copy, compare, reverse, and inspect neighbours using the correct bounds.Matrices: think in two coordinatesTraverse tables, total rows and columns, inspect diagonals, and protect grid neighbours.Characters become stringsSeparate characters from numbers, then safely inspect and edit managed text.Read the text the problem actually givesChoose words or full lines, preserve empty cases, and reset only the state that needs it.Scan text: count, filter, transformBuild a result from matching characters without losing leading zeros or skipping shifted text.Join, compare, and find textLearn content comparison, lexicographical order, substring counts, and the not-found sentinel.