Конкурсное программирование: «Ошибка превысила время»

Question

Описание проблемы:

Задание A. Количество вычитаний

У вас есть массив a длина n .Существует m запросов ( l _i , r _i ), для каждого из которых необходимо найти сумму чисел sub-array [ l _i , r _i ]

Формат входных данных:

Первая строка содержит два целых числа n и m (1 1 n, m ⩽ 10 ⁵ ) - количество номеров и запросов.Вторая строка содержит n целых чисел a ₁ , a ₂,.,,, a _n (1 ⩽ a _i ⩽ 10 ⁹ ) - номера массива.Каждая из следующих m строк содержит два целых числа l _i и r _i (1 ⩽ l _i ⩽ r _i ⩽ n) - запрос.

Выводформат данных:

Для каждого запроса выделите отдельную строку для ответа.

Мое решение:

#include <stdio.h>

int main(void) {
    long n = 0;
    long m = 0;

    long l = 0;
    long r = 0;

    register long t = 0; // temporary variable, that contains intermediate results

    scanf("%ld%ld", &n, &m);

    long  a[n];
    long  tr[m]; // array, that contains results

    for (register long i = 0; i < n; i++)
        scanf("%ld", &a[i]);

    for (register long i = 0; i < m; i++) {
        scanf("%ld%ld", &l, &r);

        l--;
        r--;

        t = 0;
        if (l != r) {
            for (register long j = l; j <= r; j++)
                t += *(a + j);
        } else t = *(a + l);

        tr[i] = t; 
    }
    for (register long i = 0; i < m; i++)
        printf("%ld\n", tr[i]);


    return 0;
}

Мое решение проходит только6 тестов из 11. Другие 5 всегда возвращают

Ошибка превышения времени

Я действительно новичок в конкурентном программировании. Как мне оптимизировать мой код, чтобы получить сложность big-O меньше, чем O (n ² )? Любая помощь будет принята с благодарностью.

Answer 1

Рассчитать совокупную сумму массива и сохранить ее в другой, то есть accumulated[i] = сумма чисел массива с точностью до i-го индекса.Это может быть вычислено в O (n).

Тогда для запроса ответ будет accumulated[r] - accumulated[l].Это O (1)