Seqmentdə cəmi (#682)

Alqoritm Analizi

Hər bir sorğu $S_{l, r}$ $O (n)$ vaxtında bir döngü vasitəsilə icra edilə bilər. $m \leq 1 0^{6}$ sorğu var və massivin uzunluğu $n \leq 1 0^{6}$ -dır. Bir sorğunun xətti vaxtda icrası ilə, bizə ən çox $n \times m \leq 1 0^{12}$ əməliyyat lazımdır ki, bu da Vaxt Limitinə səbəb olacaq.

Massiv $a$ -nın qismən cəmlərini nəzərə alaq: $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};$

Dəyərlər $s_{1}, s_{2}, \dots, s_{n}$ $O (n)$ vaxtında xətti bir massiv $s$ -də hesablana bilər.

Daha sonra, nəzərə alın ki $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}$

Beləliklə, biz bir sorğu $S_{l, r}$ -ı $O (1)$ , yəni, sabit vaxtda cavablaya bilərik.

Nümunə

Görevdə verilmiş nümunə üçün $a_{3} + a_{4} + a_{5}$ cəmini hesablayaq.

Bizim üçün: $a_{3} + a_{4} + a_{5} = s_{5} - s_{2} = 15-3 = 12.$

Alqoritm Tətbiqi

İki işlək bir ölçülü massiv elan edin.

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

Girişdəki rəqəmlər toplusunu a massivinə oxuyun, s massivində qismən cəmləri hesablayın.

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

$m$ sorğunu işləyin.

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

Alqoritm Tətbiqi – SQRT Dekompozisiya - 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;
}

Alqoritm Tətbiqi – Sorğunu Xətti Vaxtda İşləmək - 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;
}