[Algorithm](EN) Find interval sum by using prefix sum

Find interval sum by using prefix or cumulative sum


Environment and Prerequisite

  • C, C++


Problem


Apporach and Solution

(Method1)

  • Save N numbers in array and find sum from i to j every time.
  • Time Complexity : O(n^2)

(Method2)

  • Find sum from i to j by using prefix sum.
  • sum(i)(sum of first to i) - sum(j-1)(sum of first to j-1)
  • Time Complexity : O(n)


Prefix Sum(Cumulative Sum)?

Definition

  • Cumulative Sum or Prefix Sum : prefix sum or cumulative sum is a second sequence of numbers y0, y1, y2, …, the sums of prefixes (running totals) of the input sequence:
y0 = x0
y1 = x0 + x1
y2 = x0 + x1 + x2
...
yN = x0 + x1 + ... + xN

Characteristic of prefix sum

  • Interval sum from i to j can be represented as below
S[j] - S[i-1] = a[i] + a[i+1] + ... + a[j-1] + a[j]


Solutions

Method1 - O(n^2)

  • Find sum every time when there is a query.
#include <cstdio>

#define MAX_N 100001
#define MAX_M 100001

using namespace std;

int value[MAX_N];

int main(){

    int N, M;

    scanf("%d %d", &N, &M);

    for(int i = 1; i <= N; ++i){
        scanf("%d", &value[i]);
    }

    while(M--){
        int from, to;
        scanf("%d %d", &from, &to);

        int sum = 0;

        for(int i = from; i <= to; ++i){
            sum += value[i];
        }
        printf("%d\n", sum);
    }

    return 0;
}

Method2 - O(n)

  • Find sum by using prefix sum(already exist in sum array)
#include <cstdio>

#define MAX_N 100001
#define MAX_M 100001

using namespace std;

int value[MAX_N];
int sum[MAX_N];

int main(){

    int N, M;

    scanf("%d %d", &N, &M);

    for(int i = 1; i <= N; ++i){
        scanf("%d", &value[i]);
        sum[i] = sum[i-1] + value[i];
    }

    while(M--){
        int from, to;
        scanf("%d %d", &from, &to);
        printf("%d\n", sum[to] - sum[from - 1] );
    }


    return 0;
}


Reference

[Python] 파이썬(Python) List Comprehensions

> 파이썬(Python) List Comprehensions에 대해 알아보자.## 환경- Linux- Python 3.X.X## 파이썬(Python) List Comprehensions### List Comprehensions```pythonre...… Continue reading