使程序在C中以线性运行

So based in the following problem from cumulative sum query I created the solution. But is any other way to solve the problem in C with linear complexity O(N)?

因此基于累积和查询的以下问题我创建了解决方案。但是在线性复杂度为O（N）的C中解决问题的其他方法是什么？

Problem description:

问题描述：

William Macfarlane wants to look at an array.

威廉麦克法兰想要看一个阵列。

You are given a list of N numbers and Q queries. Each query is specified by two numbers i and j; the answer to each query is the sum of every number between the range [i, j] (inclusive).

您将获得N个数字和Q查询的列表。每个查询由两个数字i和j指定;每个查询的答案是范围[i，j]（包括）之间的每个数字的总和。

Note: the query ranges are specified using 0-based indexing.

注意：使用基于0的索引指定查询范围。

Input

输入

The first line contains N, the number of integers in our list (N <= 100,000). The next line holds N numbers that are guaranteed to fit inside an integer. Following the list is a number Q (Q <= 10,000). The next Q lines each contain two numbers i and j which specify a query you must answer (0 <= i, j <= N-1). Output

第一行包含N，即列表中的整数数（N <= 100,000）。下一行包含N个数字，这些数字保证适合整数。列表后面是数字Q（Q <= 10,000）。接下来的Q行每行包含两个数字i和j，它们指定您必须回答的查询（0 <= i，j <= N-1）。产量

Output

产量

For each query, output the answer to that query on its own line in the order the queries were made.

对于每个查询，按照查询的顺序在其自己的行上输出该查询的答案。

Here is the solution:

这是解决方案：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct node {
    int first;
    int last;
};

int sum_array(int *array, int first, int last) {
    int sum = 0;
    for (int i = first; i <= last; i++) {
        sum += array[i];
    }

    return sum;
}

int main() {
    FILE* input = fopen("share.in","r");

    int N = 0;
    fscanf(input,"%d",&N);

    int *array = (int*)malloc(N * sizeof(int));

    for (int i = 0; i < N; i++) {
        fscanf(input,"%d",&array[i]);
    }

    int Q = 0;
    fscanf(input,"%d",&Q);

    struct node query[Q];

    for (int i=0; i < Q; i++) {
        fscanf(input,"%d",&query[i].first); 
        fscanf(input,"%d",&query[i].last); 
    }

    fclose(input);

    int sum = 0;
    for ( int i = 0; i < Q ; i++) {
        int first = query[i].first;
        int last = query[i].last;

        sum = sum_array(array,first,last);

        printf("Number of queries : %d , sum is %d\n",i ,sum);
    }

    free(array); 
    return 0;
}

Update:

更新：

The answer given is good. But for some reason I couldn't make it work.

答案是好的。但由于某种原因，我无法使其发挥作用。

So here is the code rewritten and if someone can explain me what I do wrong I will be happy! Keep in mind we want the range to be [first,last]

所以这里是重写的代码，如果有人能解释我做错了什么，我会很高兴！请记住，我们希望范围是[第一个，最后一个]

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct node {
    int first;
    int last;
};

int sum_array(int *array, int first, int last) {
    int sum = 0;
    for (int i = first; i <= last; i++) {
        sum += array[i];
    }

    return sum;
}

int main() {
    FILE* input = fopen("share.in","r");

    int N = 0;
    fscanf(input,"%d",&N);

    int *array = (int*)malloc(N * sizeof(int));
    int *integralArray = (int*)malloc(N * sizeof(int));    

    for (int i = 0; i < N; i++) {
        fscanf(input,"%d",&array[i]);
        integralArray[i] = array[i] + ((i > 0) ? array[i-1] : 0);
    }

    int Q = 0;
    fscanf(input,"%d",&Q);

    struct node query[Q];

    for (int i=0; i < Q; i++) {
        fscanf(input,"%d",&query[i].first); 
        fscanf(input,"%d",&query[i].last); 
    }

    fclose(input);

    int sum = 0;
    for (int i = 0; i < Q ; i++) {
        int first = query[i].first;
        int last = query[i].last;

        sum = integralArray[last] - integralArray[first - 1];

        printf("Number of queries : %d , sum is %d\n",i ,sum);
    }

    free(array); 
    return 0;
}

1 个解决方案

#1

You'd form the integral array. Modify to something like:

你将形成整数数组。修改为：

int *array = (int*)malloc(N * sizeof(int));
int *integralArray = (int*)malloc(N * sizeof(int));

for (int i = 0; i < N; i++) {
    fscanf(input,"%d",&array[i]);
    integralArray[i] = array[i] + ((i > 0) ? integralArray[i-1] : 0);
}

So the element at integralArray[i] is the sum of all elements in array from 0 to i.

所以integralArray [i]中的元素是从0到i的数组中所有元素的总和。

Then, to get the sum from a to b, where a > b, integralArray[b] is the sum from 0 to b and integralArray[a] is the sum from 0 to a so you can just compute integralArray[b] - integralArray[a] to get the total from a to b. Intuitively, integralArray[b] includes the numbers you want but it also includes the numbers up to and including a. You don't want those so you take them off again.

然后，从a到b获得总和，其中a> b，integralArray [b]是0到b之和，integralArray [a]是0到a之和，所以你可以计算integralArray [b] - integralArray [a]从a到b得到总数。直觉上，integralArray [b]包含你想要的数字，但它也包括数字，包括a。你不想要那些让你再次脱掉它们。

Vary appropriately for inclusion or exclusion of the number at a and the number at b. That as given will include the number at b but not that at a. You could adjust your integralArray to be one earlier (so integralArray[b] is the sum from 0 to b-1) or adjust your indices.

适当地改变包含或排除a处的数字和b处的数字。给定的数字将包括b处的数字，但不包括a处的数字。您可以将integralArray调整为更早（因此integralArray [b]是从0到b-1的总和）或调整您的指数。