Sum on a segment#682

Sum on a segment (Editorial)

Each query $S_{l, r}$ S_{l,r} can be performed using a loop with a complexity of $O (n)$ . We have $m \leq 1 0^{6}$ m \le 10^6 queries and the length of the array is $n \leq 1 0^{6}$ n \le 10^6. If each query runs in linear time, we would need no more than $n \times m \leq 1 0^{12}$ n \times m \le 10^{12} operations, which will exceed the Time Limit.

Consider the partial sums of array $a$ :

s_{1} = a_{1}; s_{2} = a_{1} + a_{2}; s_{3} = a_{1} + a_{2} + a_{3}; ... s_{n} = a_{1} + a_{2} + a_{3} + ... + a_{n};

s_1 = a_1; \\ s_2 = a_1 + a_2; \\ s_3 = a_1 + a_2 + a_3; \\ . . . \\ s_n = a_1 + a_2 + a_3 + . . . + a_n;

It is possible to compute the values $s_{1}, s_{2}, ..., s_{n}$ s_1, s_2, ..., s_n in a linear array $s$ in $O (n)$ time.

Further note that

S_{l, r} = a_{l} + a_{l + 1} + ... + a_{r} = (a_{1} + ... + a_{l} + a_{l + 1} + ... + a_{r}) - (a_{1} + ... + a_{l - 1}) = s_{r} - s_{l - 1}

S_{l,r} = a_l + a_{l + 1} + ... + a_r = \\ (a_1 + ... + a_l + a_{l + 1} + ... + a_r) - (a_1 + ... + a_{l-1}) = s_r - s_{l-1}

So we can answer the query $S_{l, r}$ S_{l,r} in constant time.

Example

Let's compute the sum $a_{3} + a_{4} + a_{5}$ a_3 + a_4 + a_5 for the input example.

We have: $a_{3} + a_{4} + a_{5} = s_{5} - s_{2} = 15 - 3 = 12.$ a_3 + a_4 + a_5 = s_5 - s_2 = 15 - 3 = 12.

Algorithm realization

Declare two working two-dimensional arrays.

#define MAX 1000001
int a[MAX], s[MAX];

Read the input set of numbers into array $a$ , and calculate the partial sums in array $s$ .

scanf("%d",&n); 
s[0] = 0;
for(i = 1; i <= n; i++)
{
  scanf("%d",&a[i]);
  s[i] = s[i-1] + a[i];
}

C++

Process $m$ queries.

scanf("%d",&m);
for(i = 0; i < m; i++)
{
  scanf("%d %d",&b,&c);
  printf("%d\n",s[c] - s[b-1]);
}

Python realization

Read the input data.

n = int(input())
a = [0] + list(map(int, input().split()))

Calculate the partial sums of list $a$ in list $s$ .

s = [0] * (n + 1)
for i in range(1, n + 1):
  s[i] = s[i - 1] + a[i]

Process $m$ queries.

m = int(input())
for _ in range(m):
  b, c = map(int, input().split())
  print(s[c] - s[b - 1])