Sums of Segments
Contest: Educational Codeforces Round 171 (Rated for Div. 2)
Difficulty rating: 1900
Tags: binary search, data structures, dp, implementation, math

You are given a sequence of integers $$$[a_1, a_2, \dots, a_n]$$$. Let $$$s(l,r)$$$ be the sum of elements from $$$a_l$$$ to $$$a_r$$$ (i. e. $$$s(l,r) = \sum\limits_{i=l}^{r} a_i$$$).

Let's construct another sequence $$$b$$$ of size $$$\frac{n(n+1)}{2}$$$ as follows: $$$b = [s(1,1), s(1,2), \dots, s(1,n), s(2,2), s(2,3), \dots, s(2,n), s(3,3), \dots, s(n,n)]$$$.

For example, if $$$a = [1, 2, 5, 10]$$$, then $$$b = [1, 3, 8, 18, 2, 7, 17, 5, 15, 10]$$$.

You are given $$$q$$$ queries. During the $$$i$$$-th query, you are given two integers $$$l_i$$$ and $$$r_i$$$, and you have to calculate $$$\sum \limits_{j=l_i}^{r_i} b_j$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10 \le a_i \le 10$$$).

The third line contains one integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$).

Then $$$q$$$ lines follow, the $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le \frac{n(n+1)}{2}$$$).

Output format:
Print $$$q$$$ integers, the $$$i$$$-th of which should be equal to $$$\sum \limits_{j=l_i}^{r_i} b_j$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
4
1 2 5 10
15
1 1
1 2
1 3
1 4
1 5
1 10
5 10
6 10
2 8
3 4
3 10
3 8
5 6
5 5
1 8

Example output:
1
4
12
30
32
86
56
54
60
26
82
57
9
2
61

Editorial:
In the editorial, we will treat all elements as $$$0$$$-indexed.
The array $$$b$$$ consists of $$$n$$$ "blocks", the first block has the elements $$$[s(0,0), s(0,1), \dots, s(0,n-1)]$$$, the second block contains $$$[s(1,1), s(1,2), \dots, s(1,n-1)]$$$, and so on. Each position of element in $$$b$$$ can be converted into a pair of the form "index of the block, index of element in the block" using either a formula or binary search.
Let's analyze a query of the form "get the sum from the $$$i_1$$$-th element in the $$$j_1$$$-th block to the $$$i_2$$$-th element in the $$$j_2$$$-th block". Let's initialize the result with the sum of all blocks from $$$j_1$$$ to $$$j_2$$$ (inclusive), then drop some first elements from the block $$$j_1$$$, and then drop some last elements from the block $$$j_2$$$.
We have to be able to calculate the following values:
• given an index of the block $$$b$$$ and the indices of elements $$$l$$$ and $$$r$$$ from this block, calculate the sum from the $$$l$$$-th element to the $$$r$$$-th element in that block;
• given two indices of blocks $$$l$$$ and $$$r$$$, calculate the sum from block $$$l$$$ to block $$$r$$$.
In the first case, we need to calculate $$$s(b,l+b) + s(b,l+b+1) + \dots + s(b,r+b)$$$. Let $$$p_i$$$ be the sum of the first $$$i$$$ elements from the given array. The sum can be rewritten as $$$(p_{l+b+1} - p_b) + (p_{l+b+2} - p_b) + \dots + (p_{r+b+1}-p_b)$$$. This is equal to $$$\sum\limits_{i=l+b+1}^{r+b+1} p_i - (r-l+1) \cdot p_l$$$; the first value can be calculated in $$$O(1)$$$ by building prefix sums over the array $$$p$$$.
The easiest way to calculate the sum over several blocks is the following one:
• for each block, calculate the sum in it the same way as we calculate the sum over part of the block;
• build prefix sums over sums in blocks.
Depending on the implementation, the resulting complexity will be either $$$O(n)$$$ or $$$O(n \log n)$$$.