[Algorithm](EN) Find interval sum by using prefix sum
Find interval sum by using prefix or cumulative sum
Environment and Prerequisite
- C, C++
Problem
Problem Link
- Baekjoon Online Judge 11659
- Link: https://www.acmicpc.net/problem/11659
- Problem: Find interval sum from i to j in given N numbers.
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;
}