[백준] 2042: 구간 합 구하기 - JS (세그먼트 트리)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

  접근 방식

 

세그먼트 트리를 구성하는 3가지 메서드는 initTree, update, sum 메서드이다. 

 

 

initTree 메서드: for문을 사용해서 구현했다. 아직 재귀를 사용하기보다는 for 반복문이 더 편하기 때문이다.

 

트리를 처음에 초기화 하는 메서드이다. 원본 배열을 가져와서 마지막 레벨 트리에 붙여 넣고, 그리고 하나씩 내려가며 자식들을 더한 값을 저장한다.

 

 

update 메서드: 변경 된 리프노드를 시작으로 부모를 타고 올라가며 전체적인 트리를 업데이트한다.

 

세그먼트 트리에서 가장 간단하게 구현할 수 있는 메서드라고 생각한다.

 

 

sum 메서드: 구간 합을 구하는 메서드이다. 재귀를 이용해서 구현한다.

 

sum 메서드를 구현할 때 참고하면 좋은 3가지가 있다.

1. 구해야 하는 값의 구간이 왼쪽or오른쪽 구간에 포함되지 않는다면 바로 0을 반환한다.
2. 재귀 부분에 left <= half, right > half 조건문을 추가하는 것으로 최적화할 수 있다.
3. 재귀 부분에 Math.min, Math.max 메서드가 사용되었는데, 그냥 half를 사용할 경우 구해야 하는 구간이 커지거나 작아질 수 있기 때문이다.

 

 

  세그먼트 트리를 구현하며 배운 것들

세그먼트 트리에 대한 글에서 작성한 것을 캡처하였다.

 

 

 

 

  풀이

 

아래 코드에서는 answer를 출력할 때 배열을 사용했지만, 빈 string 변수로 선언하고 \n을 통해서 할당해 주고 출력하는 게 빠르고 좋다.

 

class SegementTree {
	
	constructor(arr, N, start = 1, end = N){
		this.arr = arr;
		this.width = 2 ** Math.ceil(Math.log2(N))
		this.N = N;
		this.tree = new BigInt64Array(2 * this.width).fill(0n);
		this.start = start;
		this.end = end;
	}

	// 트리 초기화 메서드
	initTree(node = 1, start = this.start, end = this.end){
    for(let i = 0; i < N; i++){	
			this.tree[this.width + i] = this.arr[i + 1];
		};

		for(let i = this.width - 1; i > 0; i--){
			this.tree[i] = this.tree[i * 2] + this.tree[i * 2 + 1]
		};
	}

	// node: 루트노드, start: 현재 노드의 역할 시작 값, end: 현재 노드의 역할 끝 값, left: 구할 값 구간, right: 구할 값 구간
	sum(node, start, end, left, right){
		
		if(start == left && end == right) {
			return this.tree[node]
		} else if(left > right){
			return 0n
		}

		const half = Math.floor((start + end) / 2)
		
		let node_left = node * 2;
		let node_right = node * 2 + 1;
	
		const left_sum = left <= half ? this.sum(node_left, start, half, left, Math.min(right, half)) : 0n;

		const right_sum = right > half ? this.sum(node_right, half+1, end, Math.max(left, half+1), right) : 0n;
		

		return left_sum + right_sum
	}
	

// index 초기값: b, value: c
	update(index, value){
	    let node = this.width + index - 1
		let diff = value - this.tree[node];


        let parent = node
        while(parent > 0){
            
            this.tree[parent] += diff
            parent = Math.floor(parent / 2);
            
        }
	}

	
}

// 입력값
let input = require('fs').readFileSync(
	'/dev/stdin'
	).toString().trim().split('\n');

// 입력값
const [N, M, K] = input[0].split(" ").map(Number);


const arr = new Array(N + 1).fill(0n);

// 입력값
for(let i = 1; i <= N; i++){
	arr[i] = BigInt(input[i]);
}

const tree = new SegementTree(arr, N);
tree.initTree()

let answer = [];

for(let i = N + 1; i < N+M+K+1; i++){

// 입력값
	let [a, b, c] = input[i].split(" "); 


if(a == 1){

	tree.update(Number(b), BigInt(c));

} else {
	const result = `${tree.sum(1, 1, tree.width, Number(b), Number(c))}`;
	answer.push(result)
}

}

for(let i = 0; i < answer.length; i++){
    console.log(Number(answer[i].toString().replace('n', '')));
}