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

쉘 스크립트에서 파일이나 명령어의 결과를 while문에서 한줄 한줄 받아서 처리해보자.


환경

  • Linux 기반 시스템
  • Bash shell(/bin/bash)


방법 예제

명령어 결과를 한줄씩 처리

  • Pipeline을 이용
ls ./Test | while read line
do
	echo $line
done
ls /tmp | while read line
do
	echo $line
done


파일을 한줄씩 읽어서 처리하기

  • Redirection을 이용
while read line
do
    echo $line
done < test.txt
  • Pipeline을 이용
cat test.txt | while read line
do
    echo $line
done


참고자료

Process file or result of command in while loop line by line in shell script.


Environment and Prerequisite

  • Linux base system
  • Bash shell(/bin/bash)


Method Examples

Process command result line by line in while loop

  • Use Pipeline
ls ./Test | while read line
do
	echo $line
done
ls /tmp | while read line
do
	echo $line
done


Process file line by line in while loop

  • Use Redirection
while read line
do
    echo $line
done < test.txt
  • Use Pipeline
cat test.txt | while read line
do
    echo $line
done


Reference

업데이트(2021.02.27): 원격에 있는 파일이나 디렉토리를 복사해오는 내용 추가

Linux 기반 운영체제에서 rsync 명령어에 대해서 알아보자.


환경 및 선수조건

  • Linux
  • Bash shell(/bin/bash)


rsync 명령어

기본

  • rsync: Remote sync의 줄임말로 여러가지 옵션을 이용해 원격 또는 로컬간에 파일이나 디렉토리를 복사하는 툴입니다.
  • rcp 그리고 scp와 같이 파일이나 디렉토리를 복사할 때 사용하는 기본 내장 명령어입니다. 원격 컴퓨터에 파일이나 디렉토리를 전달할 수 있을뿐만 아니라 로컬로도 복사가 가능합니다. 반대로 원격에 있는 디렉토리나 파일들을 가져올수도 있습니다.
  • 옵션이 정말 다양하게 많으며 많은 옵션들을 이용해 다양한 기능들을 활용할 수 있습니다.(symlink 유지, 권한 유지 그리고 파일 날짜 유지와 같은 기능들)


기본 사용법

  • manual page에 있는 자료
rsync [options ...] [source] [target]

옵션

  • -v: verbosity를 높이는 옵션으로 복사하는 과정을 더 자세하게 보여줍니다.
  • -z: compress를 주는 옵션으로 파일을 복사할 때 압축해서 복사합니다.
  • -h: 사람이 읽기 쉬운 형태로 복사 결과들을 출력해줍니다.
  • -a (same as -rlptgoD): archive 모드로 -rlptgoD 옵션을 적용한것과 같습니다. 해당 옵션들은 아래서 설명하며 symlink, 권한 그리고 timestamp와 같은 속성들을 그대로 복사합는 옵션입니다.
  • -r: 디렉토리를 복사할 때 사용하는 옵션입니다.
  • -l: symlink는 symlink 형태로 복사하는 옵션입니다.
  • -p: 파일과 디렉토리들의 권한을 유지하는 옵션입니다.
  • -t: 수정시간을 유지하는 옵션입니다.
  • -g: 그룹 속성을 유지하는 옵션입니다.
  • -o: 소유자 속성을 유지하는 옵션입니다.
  • -e: 원격에서 사용할 쉘을 명시하는 옵션입니다.
  • -D (same as --devices --specials): --devices --specials의 옵션과 같습니다.
  • --devices: root 권한이 필요하며 Device 관련된 파일들을 복사해서 생성해줍니다.
  • --specials: named socket이나 fifo와 같은 특수한 파일들도 복사하는 옵션입니다.
  • -P (same as --partial --progress): --partial --progress의 옵션과 같습니다.
  • --partial: rsync는 전송중에 인터럽트가 발생하면 전송하던 파일을 삭제하는게 기본값입니다. 이 옵션을 사용하면 전송된 부분파일을 남기고 다음부분부터 재전송 할 수 있게하여 속도를 빠르게 할 수 있습니다.
  • --progress: 전송시 진행상황을 보여줍니다.


예제

  • 로컬로 파일 복사
# rsync [File Name] [Target Path]

rsync -avzhP test.txt /tmp


# 전송시 파일명 변경도 가능

rsync -avzhP test.txt /tmp/test-renamed.txt
  • 로컬로 디렉토리 복사
# rsync [Directory Name] [Target Path]
# 디렉토리 자체가 복사된다.

rsync -avzhP test-directory /tmp


# 디렉토리 내 파일들과 하위 디렉토리들 복사
# rsync [Directory Name]/ [Target Path]

rsync -avzhP test-directory/ /tmp
  • 원격에 파일 복사
# rsync [File Name] [User]@[IP Address]:[Path]

rsync -avzhP test.txt twpower-private-server:~
rsync -avzhP test.txt twpower@192.168.1.2:~


# 전송시 파일명 변경도 가능

rsync -avzhP test.txt twpower-private-server:~/test-renamed.txt
rsync -avzhP test.txt twpower@192.168.1.2:~/test-renamed.txt
  • 원격에 디렉토리 복사
# rsync [Directory Name] [User]@[IP Address]:[Path]
# 디렉토리 자체가 복사된다.

rsync -avzhP test-directory twpower-private-server:~
rsync -avzhP test-directory twpower@192.168.1.2:~


# 디렉토리 내 파일들과 하위 디렉토리들 복사
# rsync [Directory Name]/ [User]@[IP Address]:[Path]

rsync -avzhP test-directory/ twpower-private-server:~
rsync -avzhP test-directory/ twpower@192.168.1.2:~
  • 원격에 있는 파일 로컬로 가져오기
# rsync [User]@[IP Address]:[File Name] [Path]

rsync -avzhP twpower-private-server:~/test.txt .
rsync -avzhP twpower@192.168.1.2:~/test.txt .


# 전송시 파일명 변경도 가능

rsync -avzhP twpower-private-server:~/test.txt ./test-renamed.txt
rsync -avzhP twpower@192.168.1.2:~test.txt ./test-renamed.txt
  • 원격에 있는 디렉토리 로컬로 가져오기
# rsync [User]@[IP Address]:[Directory Name] [Path]
# 디렉토리 자체가 복사된다.

rsync -avzhP twpower-private-server:~/test-directory .
rsync -avzhP twpower@192.168.1.2:~/test-directory .


# 디렉토리 내 파일들과 하위 디렉토리들 복사
# rsync [User]@[IP Address]:[Directory Name]/ [Path]

rsync -avzhP twpower-private-server:~/test-directory/ .
rsync -avzhP twpower@192.168.1.2:~/test-directory/ .


추가 내용들


참고자료

Update(2021.02.27): Add contents of copying remote file or directory to local

Let’s use rsync command in Linux base OS.


Environment and Prerequisite

  • Linux
  • Bash shell(/bin/bash)


rsync command

Basic

  • rsync: It represents remote sync. It is a fast, versatile, remote (and local) file-copying tool which can use with various options.
  • It is similar file-copying tool like rcp and scp. It can copy file or directory to not only remote but also local. Also, remote file or directory can be copied to local.
  • There are so many options that can be combined to many functions.(preserve symlink, preserve permission, preserve timestamp etc)


Basic Usage

  • Contents from manual page
rsync [options ...] [source] [target]

Option

  • -v: Increase verbosity. It give more information about copying process.
  • -z: Compress files when copying.
  • -h: Print human-readable mode.
  • -a (same as -rlptgoD): Archive mode. It is same as -rlptgoD options. Those options explanation are at below of this option. It copies symlink, permission, timestamp and etc properties.
  • -r: Recurse into directories. Use it for directory copy.
  • -l: Copy symlinks as symlinks.
  • -p: Preserve permissions.
  • -t: Preserve modification times.
  • -g: Preserve group.
  • -o: Preserve owner(super-user only).
  • -e: Specify the remote shell to use.
  • -D (same as --devices --specials): Same as --devices --specials.
  • --devices: This option causes rsync to transfer character and block device files to the remote system to recreate these devices.(root only).
  • --specials: This option causes rsync to transfer special files such as named sockets and fifo.
  • -P (same as --partial --progress): Same as --partial --progress.
  • --partial: By default, rsync will delete any partially transferred file if the transfer is interrupted. This option tells rsync to keep the partial file which should make a subsequent transfer of the rest of the file much faster.
  • --progress: Showing the progress of the transfer.


Examples

  • Copy file to local
# rsync [File Name] [Target Path]

rsync -avzhP test.txt /tmp


# Name can be changed during transfer

rsync -avzhP test.txt /tmp/test-renamed.txt
  • Copy directory to local
# rsync [Directory Name] [Target Path]
# Directory itself is copied.

rsync -avzhP test-directory /tmp


# Copy all files and subdirectories in directory
# rsync [Directory Name]/ [Target Path]

rsync -avzhP test-directory/ /tmp
  • Copy file to remote
# rsync [File Name] [User]@[IP Address]:[Path]

rsync -avzhP test.txt twpower-private-server:~
rsync -avzhP test.txt twpower@192.168.1.2:~


# Name can be changed during transfer

rsync -avzhP test.txt twpower-private-server:~/test-renamed.txt
rsync -avzhP test.txt twpower@192.168.1.2:~/test-renamed.txt
  • Copy directory to remote
# rsync [Directory Name] [User]@[IP Address]:[Path]
# Directory itself is copied.

rsync -avzhP test-directory twpower-private-server:~
rsync -avzhP test-directory twpower@192.168.1.2:~


# Copy all files and subdirectories in directory
# rsync [Directory Name]/ [User]@[IP Address]:[Path]

rsync -avzhP test-directory/ twpower-private-server:~
rsync -avzhP test-directory/ twpower@192.168.1.2:~
  • Copy file from remote to local
# rsync [User]@[IP Address]:[File Name] [Path]

rsync -avzhP twpower-private-server:~/test.txt .
rsync -avzhP twpower@192.168.1.2:~/test.txt .


# Name can be changed during transfer

rsync -avzhP twpower-private-server:~/test.txt ./test-renamed.txt
rsync -avzhP twpower@192.168.1.2:~test.txt ./test-renamed.txt
  • Copy directory from remote to local
# rsync [User]@[IP Address]:[Directory Name] [Path]
# Directory itself is copied.

rsync -avzhP twpower-private-server:~/test-directory .
rsync -avzhP twpower@192.168.1.2:~/test-directory .


# Copy all files and subdirectories in directory
# rsync [User]@[IP Address]:[Directory Name]/ [Path]

rsync -avzhP twpower-private-server:~/test-directory/ .
rsync -avzhP twpower@192.168.1.2:~/test-directory/ .


Additional Things


Reference