Sum over All Subarrays — Solution & Editorial

Back to the Problem

Count each element's contribution: a_i (1-based i) appears in i · (N−i+1) subarrays. Sum a_i times that count — no enumeration needed.

Complexity: O(N)

Watch out: The total reaches ~10¹⁸; 64-bit integers are required (Python is safe, C++ needs long long).