四六级考试，线性表的应用

Question

int main()

{

    int n, k, a, b,i, j, x;

    SeqList L;
    scanf("%d %d", &n, &k);
    for (a = 0; a < n; a++)
        scanf("%d", &L.elem[a]);
    L.last = n - 1;
    for (a = 0; a < k; a++)
    {
        scanf("%d %d %d", &i, &j, &x);
        for (b = i - 1;b < j; b++)
            L.elem[b] = L.elem[b] + x;
    }
    print(&L);                //输出顺序表
}```


怎么降低这个算法的时间复杂度啊，运行老是超时

Answer 1

经典的差分算法, 建立差分数组b[i] = a[i]-a[i-1], 题目把原数组a[i]到a[j] (包括两端) 的之间的所有数据都统一加上一个数x, 对应的只需要把b[i]+x, b[j+1]-x就行了, 这样可以省去你里面的for