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

Find interval sum by using prefix or cumulative sum

• 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;
}
``````

Updated on