부분 합(구간 합), 누적 합

누적 합

1차원 배열을 예로 들 때, 누적 합은 인덱스 0에서부터 인덱스 i까지의 값들을 모두 더한 값이다.

 

즉 다음과 같은 배열이 존재할 때

{-1, 7, 4, -3, 0, 1, 8, 7}

 

위 배열의 누적 합

{-1, 6, 10, 7, 7, 8, 16, 23}

은 O(n)의 시간복잡도를 통하여 다음과 같이 구할 수 있다.

int[] cumulativaSum(int[] arr){
	int total = 0;
	int[] sum = new int[arr.length];
    for(int i=0; i<arr.length; i++){
    	total += arr[i];
        sum = total;
    }
  	return sum;
}

sum[i] = 인덱스 0부터 i까지의 누적 합

 

부분 합(구간 합, prefix sum)

부분 합은 인덱스 i에서부터 j까지 범위 값들을 모두 더한 값이다.

 

부분 합을 구하는 방식에는 

1) 누적 합을 이용하거나

 

2) 세그먼트 트리를 사용하는 

 

두 가지 방식이 있다.

순서대로 살펴보자 !!!

 

누적 합을 적용한 방식

위에서의 예시를 다시 이용하여 생각해 보면

int[] arr 

-1

7

4

-3

0

1

8

7

 

이의 누적 합

int[] sum 

 

[0 ~ 0] 0

[0 ~ 1] -1

[0 ~ 2] 6

[0 ~ 3] 10

[0 ~ 4] 7

[0 ~ 5] 7

[0 ~ 6] 8

[0 ~ 7] 16

[0 ~ 8] 23

 

구한 누적 합을 계산하여 부분 합을 구할 수 있다 ~~

int prefixSum(int[] sum, int i, int j){
	return sum[j+1] - sum[i]; 
}

 

누적 합을 이용한 부분 합 계산은 위와 같이 배열의 값이 변하지 않을 때에는 만족스러운 시간복잡도 내에서 풀이할 수 있지만,

값이 변경된다면 -> 변경될 때마다 누적 합 재계산(O(n))의 시간복잡도가 소요된다는 단점이 있다.

이러한 약점을 개선한 것이 세그먼트 트리를 이용한 방식임

 

 

 

세그먼트 트리를 이용한 방식

세그먼트 트리( https://www.acmicpc.net/blog/view/9 )

세그먼트 트리는 위처럼 이진 트리 구조를 지니는, 특정 구간에 대한 연산을 효율적으로 수행할 수 있게 하는 자료구조이다.

구간에 대한 연산 값을 각 노드에 저장하고, 데이터의 변경이 일어날 시 leaf부터 수정해나가는 방식으로 O(logN)의 시간복잡도로 처리할 수 있다.

 

static class Node{
	int value;
    Node right;
    Node left;
    
    void update(int value){
    	this.value = value;
    }
}

void updateSegmentTree(Node[] segmentTree, int idx, int value){

	int currIdx = idx;
	segmentTree[currIdx].update(currValue);
	while(currIdx/2 > 0){
    	currIdx /= 2;
        segmentTree[currIdx].update(
        	segmentTree[currIdx*2].value + segmentTree[currIdx*2 + 1]
        );
    }
}