[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] pdb를 이용해 파이썬 코드 디버깅하기

> pdb를 이용해 python 코드를 디버깅하는 방법을 알아보자.## 환경- Linux 기반 시스템- Bash shell(/bin/bash)- Python## pdb### pdb란?- ```pdb``` : 파이썬 디버깅 도구로 파인썬 인터프리터...… Continue reading