Skip to Content

Range sums

Level A. Teaches domains, cuts and prefix sums.

You are given n integers a₁ … aₙ (1 ≤ n ≤ 2·10⁵, 1 ≤ aᵢ ≤ 10⁹) and q queries (1 ≤ q ≤ 2·10⁵). Each query is two positions l ≤ r, 1-based and inclusive. For each query print aₗ + … + aᵣ.

Input: n, the n integers, q, then q lines l r. Output: one line per query.

InputOutput
5
3 1 4 1 5
2
1 3
2 5
8
11
4 tests · Ctrl+Enter