Сума на відрізку#682

Сума на відрізку (Розбір)

Аналіз алгоритму

Кожен запит $S_{l, r}$ S_{l,r} можна виконувати за допомогою циклу за час $O (n)$ . Існує $m \leq 1 0^{6}$ m \leq 10^6 запитів, довжина масиву складає $n \leq 1 0^{6}$ n \leq 10^6. При лінійному часі виконання запиту нам потрібно не більше $n \times m \leq 1 0^{12}$ n \times m \leq 10^{12} операцій, що дасть Time Limit.

Розглянемо часткові суми масиву $a$ : $s_{1} = a_{1};$ s_1 = a_1; $s_{2} = a_{1} + a_{2};$ s_2 = a_1 + a_2; $s_{3} = a_{1} + a_{2} + a_{3};$ s_3 = a_1 + a_2 + a_3;. . . $s_{n} = a_{1} + a_{2} + a_{3} + ... + a_{n};$ s_n = a_1 + a_2 + a_3 + . . . + a_n;

Обчислити значення $s_{1}, s_{2}, \dots, s_{n}$ s_1, s_2, …, s_n можна в лінійному масиві $s$ за час $O (n)$ .

Далі помітимо, що $S_{l, r} = a_{l} + a_{l + 1} + \dots + a_{r} = (a_{1} + \dots + a_{l} + a_{l + 1} + \dots + a_{r}) - (a_{1} + \dots + 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}

Таким чином відповісти на запит $S_{l, r}$ S_{l,r} можна за $O (1)$ , тобто за константний час.

Приклад

Обчислимо суму $a_{3} + a_{4} + a_{5}$ a_3 + a_4 + a_5 для наведеного в умові прикладу.

Маємо: $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.

Реалізація алгоритму

Оголосимо два робочих одновимірних масиви.

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

Читаємо вхідний набір чисел у масив a, обчислюємо часткові суми у масиві s.

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

Обробляємо $m$ запитів.

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

Реалізація алгоритму – SQRT декомпозиція - TLE

#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

int i, n, m, len, x, y;
vector<int> a, b;

int q(int l, int r)
{
    int i, sum = 0;
    int c_l = l / len, c_r = r / len;
    if (c_l == c_r)
        for (i = l; i <= r; i++)
            sum += a[i];
    else
    {
        for (i = l; i <= (c_l + 1)*len - 1; i++)
            sum += a[i];
        for (i = c_l + 1; i <= c_r - 1; i++)
            sum += b[i];
        for (i = c_r * len; i <= r; i++)
            sum += a[i];
    }
    return sum;
}

int main(void)
{
    scanf("%d", &n);
    a.resize(n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

    len = sqrt(n) + 1;
    b.resize(len);
    for (i = 0; i < n; i++)
        b[i / len] += a[i];

    scanf("%d", &m);
    for (i = 0; i < m; i++)
    {
        scanf("%d %d", &x, &y);
        printf("%d\n", q(x - 1, y - 1));
    }
    return 0;
}

Реалізація алгоритму – запит за лінійний час - TLE

#include <stdio.h>
#define MAX 1000001

int i, j, n, m, b, c, s;
int a[MAX];

int main(void)
{
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]);

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